ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

HUPC2020Day3 G Katsusando

動的計画法(DP)

問題
提出コード

解法

まず、二人が出会う地点は必ずカツが置いてある座標になります。途中で挟むとしても、左右どちらかのカツで出会うように適切に調整することで損をすることはありません。

  • dp[i] = 左からi番目のカツまで食べ終えた状態のときに経過した時間の最小値

としてこれを解こうとします。
今、j番目のカツの座標で次のカツサンドを作成するとします。また、

  • d_{(i,j)} = i番目のカツに誰かを配置して、j番目のカツに移動させたときにかかる時間

とします。これはO(N^{2})で計算できます。i,jはどちらが大きくても問題ないです。

そのとき、左側における行動の最適解はmin\left(dp[p] + d_{(p+1,j)}\right)になります。この時間をTとします。これが求まると、
dp[i] = min\left(dp[i], T + d_{(i,j)} + K + 1\right)
という計算をしていくことで、dpの計算ができます。
あとは、dp[N]を答えれば終了です。
コストを求める前計算、dpの計算共にO(N^{2})になります。

感想

カツを挟む部分を決め打った場合に更新が楽にできるようになり、これはあまり普段使わない考え方だったので面白かったです。

HUPC2020 3日目

番外編

1日目はこちら、2日目はこちら
3日目は、とまとさんるぎうさんとのチームです。
例によって問題は解いた順です。

内容

A

ここはサクッと。全体3番目だったので良かったかと思います。

C

るぎうさんがサクッと考察していたのですが、少しバグって僕がコードを見たりしました。
遅すぎはしなかったのでまぁこれから、という感覚でした。

I

るぎうさんに通ってる(けどパッとはわからない)から見てみてと言われたので僕が見たところ、2,3分で最小全域木→倍数→調和級数、という考察フローを辿れたので即座に実装、ACしました。この問題を軽く通せたのは良かった気がします。

M

僕が考えたりるぎうさんが考えたりしましたが、るぎうさんが最終的に考察を出し、僕が実装するという流れに。

  1. 3進数を描きたくなくてmap + stringでごまかす→TLE

  2. 基本strnigでmapの部分だけ3進変換→TLE

  3. stringを一切使わず全て3進数で実装→2.82sでAC(TLは3s)

という流れでした。結構オーダーギリギリだから気を付けてとるぎうさんに言われたのにいう事を聞かなかった僕が完全に戦犯でした。
ところで、よくよくこの問題を見直すと、同じ頂点からの辺は高々1度しかみないという、WUPCのJ問題そっくりの問題だったので最初に見た時点で気づけず反省…

B

最初、とまとさんと僕で解法をくみ上げ、たかだかマンハッタン + 2で抑えられますね、という解法(縦横どっちかを先に終わらせた後、残りを計算)を連打してペナを蓄積しました。
結局、るぎうさん一人で考察しなおしてAC…

E

僕とるぎうさんで考察を行い、考察はいいが自分が実装があんまり思いつかないからどうしよう、と話していたところでとまとさんが参戦。とまとさんとるぎうさんの話を聞いていたところで僕が実装イメージをくみ上げ実装していましたが、まず偏角ソートが幾何ライブラリに入っていませんでした。
yosupo judgeで適当にコードを漁り(かつっぱさんのものを参考にしました、ありがとうございます)、それを自分のライブラリに組み込むことで実装を行いました。
が、なぜか偏角ソートの確認でバグって動かず、よくよく見たらお手製サンプルの方が間違っていて時間を溶かしました(つд⊂)ｴｰﾝ
その後実装を終えますが、なぜかサンプルの答えがグラフ全体の面積に。
手元で確認したところ、辺の向きが逆になっていたので書き直すとサンプルが通り、無事AC。
この時点ではまだあまり通っていなかったので、ここをさっさと処理できたのはよかったです。

この時点で、あと通せそうな問題がG(るぎうさん)、F(とまとさん)に加えて +1問(J,Kのいずれか)になり、これが全部通れば結構いいのではないか、と思っていました。

G

カツサンドの問題ということ以外何も知りません。気づいたら通っていましたシリーズです。ありがとうございます。

F

問題を見終えて割とはやい段階で、swapが定義できること、 GYYというものがあったときに GRR もしくは GBB に変換できること、がわかり、後は細かい部分を詰めればいけそう、という話をとまとさんと二人でしていました。
が、そこから嘘解法にひたすら走ってしまうことになり、結局最後まで通せず…
最後にるぎうさんが駆けつけてくださりましたが、間に合いませんでした。

結果

もう一声欲しいですね(2回目)
f:id:emtubasa:20200916211601p:plain

反省

BやFで、とまとさんと僕が2人で嘘解法を投げまくっていました。
とまとさんの実装スピードがせっかくはやいのに、僕が嘘に気づけず修正ができないのが弱点な気がします…
今後は、るぎうさんが考察のかなめになり、嘘っぽい解法で炎上しかけた際はかならずるぎうさんに見てもらおう、という話になりました。
そのためにも、るぎうさんの考察は僕ととまとさんが実装(実際、僕は変な実装でなければ基本的にスピードがそこそこで、とまとさんはスピード + 安定感があります)することになるので、練習しておこうと思います。

おしまい

3日間はやっぱり多少疲れました…
楽しかったです、運営してくださった皆様ありがとうございました！
弊学チームはACPCでまたボコボコにしたいと思います。

HUPC2020 2日目

番外編

一日目はこちら
yamadさん、とまとさんと yamad as a Serviceで出場しました。
yamadさんが助っ人サービスになる時代…
通した順に書いていきます。

内容

A

3秒くらいオーバーフローどうするんだろう…って悩んでいました。素直に0を出力するだけでした。

B

とまとさんがやりたくないーって少しバグらせつつもしっかり通してくださりました。問題文をチラ見しましたが、本当にやりたくない見た目をしていたのでスルーしました。ごめんなさい。

C

yamadさんが解けないーって言っていたので参戦しました。
二項係数っぽいとかいろいろいいながら、手計算でN=10のケースまで計算し、OEISに投げた結果を見て「ただのDPじゃん！行列累乗じゃん…」と二人で反省しつつyamadさんが通しました。

G

気づいたら通っていました。とまとさんがダブリングとか言っていて、それをyamadさんが通したっぽい？これもB同様問題をチラ見だけしましたが、内容が頭に入ってこなかったのでそっとじしていました。

M

それぞれの頂点にあるグランディ数を求めるのに、O(NK^{2})かかるんですがbitsetで高速化できると思います、と考察をyamadさんに話したら通るはず、と言われたので書きますがWA。
内容を再び細かく説明するお、グランディ数はKには収まらずO(\sqrt{N})くらいなので、bitsetの長さを100から1000にしたら今度はMLEしました。きちんと\sqrt{10^{5}}を計算しなおして317にセットし、ようやくACしました。通れば正義

J

とまとさんに面白そうですと紹介されたので読んでみると、セグ木でDPしたくてたまらなくなりました。
考察を少しすると、この問題にほとんど似ている形に帰着できます。
この問題は、WUPCでも似た問題を作問していて、その既出判定の際にピックアップされた問題だったので記憶に新しく、あとはサクサクと実装できました。ひゃどみん、あの問題を作問してくれてありがとう！

D

yamadさんととまとさんがずっと考えていましたが全然わからず、ただ気づいたら通っていました。内容は知っていましたが、自分が解いたら解ける自信はないです…

I

最初、三分探索という話があがりそれをとまとさんが実装しましたが、30ケース目と31ケース目でずっとWAが出ていました。
その後、想定解をyamadさんととまとさんが思いついたらしく書いていましたが、5ケースしか通りませんでした…
と、残り10分前後で、実は逆行列を求めるパートが間違っているのでは？という話になり、僕がkoprickyさんのライブラリを見つけ、それを使ってみるとなんとAC…
ちなみに解法はなんとなくしか理解しておらず、いまだにふわふわしているので線形代数を勉強する必要がありそうです。koprickyさんありがとうございました。

My Algorithm : kopricky アルゴリズムライブラリ

結果

もう一声欲しいですね。

f:id:emtubasa:20200916211455p:plain

反省

C問題等、変なところでつまるのが多かったです。yamadさんのICPC力をフルに生かすには、僕がもう少し簡単枠をサクサク倒していかないといけないかなと感じました。
ライバル視している後輩チームの1つにペナ差で負けたので悔しいです(途中まで2完差ついていたので、さすがに負けないだろうと思っていました)。

おしまい

明日はまたるぎうさんが復帰するので、 Give us sociabilityをボコボコにしようと思います！

HUPC2020Day1 F: n 角錐グラフ

問題
提出コード

解法

頂点0と別の頂点を結ぶ辺の集合を中心の辺、pとp+1を結ぶ辺の集合を円周上の辺と呼ぶことにします。
i回頂点0に戻る、と仮定したときの数え方が高速に求まれば、これを全部のiについて試せばよいです。
このとき、頂点0を1回だけ通る閉路はi個あるはずです。よって、今回見ているサーキットは、中心の辺がN本の中からi本、円周上の辺はN本からk-2i本選ばれていることになります。
これらの閉路を通る順番はなんでもよく、また、閉路を時計回りに進むか、反時計回りに進むかはそれぞれの閉路ごとに独立に考えられます。よって、最後にi! \times 2^{i}をかける必要があります。
次に、上記の閉路で使う辺のパターンを数えます。
同じ辺を2回以上通れないことから、
(辺を通る区間)(辺を通らない区間)(辺を通る区間)...(辺を通らない区間)
となっているはずです。辺を通る区間、通らない区間は丁度i個になっています。
辺を通る区間の1つが、1,2,...kであると固定します。そうすると、このときの区間の決め方を数えたときに、\frac{N}{i}をかければ、全体での辺の決め方を数えられたことになります(先頭を固定したので、その先頭をN頂点全てに経験させる必要がありますが、先頭のそれぞれの閉路パターンで、先頭の選び方はi通りあります。よってこの値をかければよいです)。
このとき、辺を通る区間、通らない区間それぞれ独立に考えると、
辺を通る区間:_{i}H_{k - 3i}通り
辺を通らない区間:_{i}H_{n - (k-2i) - i}通り
で数えられます。
選ばなければいけない辺の本数がそれぞれ決まっていて、i個の区間に最低1本ずつ割り振る必要があるので、まず1本ずつ割り振った後に、重複組み合わせを考えればよいです。
さて、これにより辺k本を通るサーキットの個数が

  • i! \times 2^{i} \times _{i}H_{k - 3i} \times _{i}H_{n - (k-2i) - i} \times \frac{N}{i}

で求められることがわかりました。
あとは重みの総和ですが、中心の辺が選ばれる確率は\frac{k-2i}{N}、円周上の辺が選ばれる確率は\frac{2i}{N}なので、これをb_i,a_iにかけてあげた後、上記の通り数をかければ答えが求まります。

感想

悩みましたが、実際に数え上げてみると求める解は想像以上に綺麗になるので面白かったです。

HUPC2020 1日目

番外編

僕、とまとさん、るぎうさんで組みました。
コンテスト開始直前に、チーム名が変わって Ramen as a Serviceになりました。

f:id:emtubasa:20200914162432p:plain
捨てられてしまったアカウント(ごめんなさい)

ICPCのチームはこの三人で行く予定でしたが、チーム練習は初めてでした。果たして…

流れ

開始直後

僕がAをさっさと通し、Bをとまとさんが通します(A→0:03、B→0:13)。
その間はるぎうさんがCを読んでいました。僕がDを読み終えた段階でるぎうさんがCわからないと言っていたので、Dの考察をるぎうさんに投げて僕はCに行きました。とまとさんがBを通した頃にるぎうさんからDの考察が返ってきたので自分が実装、とまとさんとるぎうさんでCを解く、という形になります。
コピペOKだったので、自分の幾何ライブラリ(400行)をバン！と貼り、サクサク書いて全体2番目にDをACしました(0:24)。
この間にCの考察が終わっていたようなので、とまとさんにバトンタッチしCもAC(0:30)。

中盤

るぎうさんがEを読み、僕がFを読みます。とまとさんがCを通した後はEに合流していただきました。
Fの考察は、まず0に戻る回数を決め打った際、1以上の頂点について使う辺の並べ方をあとは数えればいい、という部分まで解けていて、その部分がうまくハマらずにうんうんうなっていました。
この隙にEが解けていたらしく、提出→WA。
ここで、自分もFを詰め切った(つもり)ので、Eのデバッグをしていただきながら自分はFの実装を開始しました。
その後、すぐに解法が違うことに気づき修正したらしく、無事AC(1:27)。

とまとさん「二部マッチングのライブラリ2つあるんだけど、片方壊れていた記憶あるんだよね…」  
僕、るぎうさん「両方投げましょう！」    
1回目 → WA(37ケースAC)  
とまとさん「やっぱり嘘解法なのかな…」    
僕、るぎうさん「とりあえずもう一つもだしましょう！」   
2回目 → AC


ライブラリ整備はきちんと行いましょう。

このやりとりのあと、自分はFのサンプルが合わず苦戦。
ところが、今出ている答えから逆算した結果、0に戻る回数で値を割るとサンプルがあってしまうことがわかり、わけがわからない状態に。
半信半疑だったので、るぎうさんととまとさんに考察を聞いてもらうと、それでサンプルが合う理由がようやくわかり、提出、AC(1:59)。ラバーダッキング最強！(素振り)

HUPC2020Day1 F: n 角錐グラフ - ツバサの備忘録

終盤

G、Hは僕が解ける問題に見えず、お二人を応援していました。
Hは双対かな、というところでるぎうさんが詰めていましたが、結局誰もかける人がいなかったので最後の5分は順位表を眺めてお祈りしていました(るぎうさんはメールを書いていました…)。

結果

6完10位でした！同大学の中では多分1位なので、結構うまくいったと思います。
f:id:emtubasa:20200914165015p:plain

反省点

序盤、少しどの問題を読むか？でもたついてしまったので、もう少しスムーズに行けると良いかなと思いました。
G, Hは今の実力では通せないのでペナを少なく、そしてよりはやく解く必要がありますが、D問題あたりは結構理想ムーブをした気がするのでわからず…
F問題で結構もたついたので、ここはもう少しはやくしたいです(おそらく自分がそこそこ得意な枠なので…)。

おしまい

明後日と、ACPCはこのチームでまた出る予定なので、対戦(?)お願いします！

WUPC4th を開催しました

番外編

2020/9/12に行われた、WUPC4thの運営側目線の感想です！
コンテストサイト

運営陣について

早稲田大学の競プロコミュニティは、現B2が今一番ホットになっています。彼らが今回主催となってWUPCを開催しようとしているところにのっかる形で参加することになりました。AOJや告知はadminのHyadoくんや、同じく現B2のかっつくんに任せて、僕は高学年なことをいいことに、いろいろ口出しをしたり邪魔していました。 これが理由で、実はWUPC3とはメンバーが大幅に変わっていて、yamadさんと自分以外は新規メンバーです(WUPC3のお話はこちら)。 以下、writer&tester陣の紹介です:
yamadさん
しろくん
sutaくん
Senくん
かっつくん
Hyadoくん(admin)
ばやしこくん
hotmanくん
オウコウくん
suzukenくん
よぴぱくん

問題セットについて

今回は、5時間で13問という形になりました。

A: Prime Number Sum 2

簡単枠です。昨年のWUPC3rdよりは簡単になったかと思います。
基本区間の幅の偶奇を見ればいいのですが、A = 1、すなわち素数の"2"が含まれている場合だけ、答えが逆になります。
他の問題だけだと序盤から解けなくて詰まる人がいるのではないか、ということから最後に生えた問題です。

B: Canceling Sequence

少し簡単めの構築枠で、当初はこれがAに置かれていました。
[1,N)とN番目の要素に分割し、それぞれの係数をうまく組み合わせて0にすればOKです。緩めの制約にしてあるため、適当につくっても問題の条件を満たします。
僕は構築が苦手なので、この問題を解くのに少し時間がかかりました...

C: Flip Difference Sequence

奇数列目を最大化、偶数列目を最小化すればOKです。あとはどれだけ答えに寄与するか、を計算できればいいのですが、実は二項係数になっています。
問題ができた当初、割と最近のAGCでこれ(ネタバレ注意)が出題されていたので意外と解かれるかも…？と思っていました。

D: Treasure Mountains

自分の問題1つめです。
指数部分について、区間積を計算し、\mod{N}の逆元を計算すれば、xを累乗するだけで簡単にtが求まる、という問題です。
これは、自分が参加したCTFで似たようなことをする問題があり、それが面白いと感じたことから作問しました(元ネタを知りたい方は、 cryptctf three ravens で検索してみてください)。
この問題を作成した時点では作問が閉め切られていたのですが、追加枠が発生したのでそこに滑り込ませました。
数学系の問題を作るのは初めてで、証明をなんども反復して行ったりと不安要素が多かったです。

E: LCM Count

問題を見ると約数包除をしてください、と書いてあるので約数包除をします。
考え方は蟻本のとほぼ同じで、あとは数列の並べ方を気合で数えます。
問題や入力がシンプルかでかつ解法が面白いので、結構好きです。

F: Abyss and Coins

2で割れる回数を固定したとき、その中で取れる最大の数が答えの候補になります。あとは全探索です。
結構アドホック要素多めですが実は素直に見ればいいという問題でした。(僕らの想定では)C以降で一番簡単枠、でした。

G: Fitness

01ナップサックと、個数制限ナップサック両方をやるという問題です。帰着できればすごいサクサク解けてシンプルですがハマると…？
もちろん元ネタはこれです。少し前は諸事情でできなくて、最近再開したのでのんびり頑張ります。
典型 + 典型 で解法も実装もシンプルなので、結構好みです。

H: RGBtree

木の直径が奇数かつ3の倍数 + 一定の条件を満たしたときのみ、他と比べて少しペナルティが大きくなる、それ以外は適切に構築すると最高効率で構築できる、という問題です(簡単に説明するのは難しいので解説を見てください)。
個人的に圧倒的ボス問でした。こういうの解けるようになりたいですね…
yamadさんがすごい不安がりながら何回もこの問題を証明し直してるのを横目に、自分もD問題の証明を必死になって反復していました。

I: Magical Matrix

桁ごとに見て、マスの行と列の差の絶対値が1以内の部分に立っているビットがあるかどうかを見ればよい、という問題です。気づいたり証明したりするのは難しいかもしれませんが、気づけばそこまで数えるのは難しくないです。
これ結構すごいと感じました。作問スキルいいな～。

J: Meet on the Island

一度クエリでYESとなった島は、それ以降常にYESなので、そこを探索しないようにうまく見ていきます。
今いる頂点も、既に探索済みであれば探索しない、ということをしないとコーナーケースにハマってしまうのでご注意を！！

K: Rectangle Game

ミラー戦法をベースにやると、あとは細かい場合分けです。
リアクティブ問題にして実際に構築、等々いろいろ考えましたが難しくて断念しました。
割と最近、こんな問題があり、ビクビクしていました。

L: Count Pow Sum

蟻本239ページを一般化すればよいです。全然しらなかった、面白いです。

M: Star Gazer

suta-Gazerってね。 気合で全方位木DPが最初の想定でしたが、より軽い実装もあります。
木の問題が作りたいなーと言ってるときに生やしました。距離が計算式にあるのに距離を全く使用しなくても解ける、というのが当時のポイントです。

準備について

B2が主体となって進めてくださったので、あとはただその流れに乗るだけでした。
既出等が見つかっても、代理問題を準備できたのでよかったですね。
テストケースが弱くなってしまいがちな問題が今回も多かったので、全員で協力していろいろ作成できたので安心でした。
今回、作問陣だけでは不安が残るということで、外部テスターとして物理好きさん、SSRSさんのお二人に参加していただきました。内容は、完成したセットをバチャ形式で一通り解いていただく、というものです。
お二人とも得意分野が違っていて、解く順序やスピードが異なっていて面白かったです(内部では順位表を見てワイワイしていました)。
特に物理好きさんは、解くたびに問題面白い、とコメントをくださっていて、内部で喜んでいました。

本番

途中、ジャッジが一時期詰まるという事態が発生しましたが、それ以外は特にトラブルなく進みました。
問題文の訂正が一つだけありましたが、後はなんとかなったのでよかったです(B2陣、すごい)。
自分達が用意した問題で詰まったりケースで落ちるのを見るのは最高ですね！！！

終わりに

改めて、参加してくださった皆様、主催してくれたひゃどみん、一緒に準備した皆、サイトを提供してくださったAOJの方々、外部テスターとして参加してくださったSSRSさん、物理好きさん、その他大勢の皆様、本当にありがとうございました！

DDCC2020本戦 C - 特別講演「括弧列と塗り分け」

動的計画法(DP) 二乗の木DP

問題
提出コード

解法

dp[i][j] = [i,j)という区間の塗り分け方、みたいなものを考えたいですが、上手いこと工夫しなければ計算量が大きくなってしまいそうです。
ここで、括弧列が木に対応することを思い出すと、二乗の木DPができそうになってきます。

  • dp[i][j] = i番目の文字(開き括弧)とそれに対応する閉じ括弧までの区間で、R-B = jとなるような塗り方

を考えます。
子にあたる部分についての上記の値が求まっていると、それらを組み合わせてR-B = jとなるような塗り方は簡単に計算ができます。
なので、再帰をしていって、子から計算をしていけばよいです。
このDPは、まさに二乗の木DPの形をしているので、計算量的にも問題ありません。
\sum dp[0][j] \ (|j| \leq K)が答えです。