okimochi ICPC2019 模擬国内予選 参加記
参加資格ありのチーム内で5位!チームとしての上限に近いパフォーマンスだったと思う。
Aをまず通す。その間にBは01bfsやるだけですと言われたので受け取り、難なく通す。少しバグらせたのでここまで15分くらいかかってしまったが、そこそこ早かったようだ。
一方Cが怪しいながらもこるとんが書き始める。その間にDとEを読み、EがすぐにはわからないのでDがわからないというrisujirohにEを投げる。数分でEの解法が分かり(早い…)、Cが通らないらしいのでrisujirohがEを書き始め、僕がC、こるとんがDを見る。EがバグったがこるとんがDがいけるというので交代する。その後DとEを交代しながら連続で通しきる。なんかEはbitsetの宣言がよくなかったらしい。
その後、Cが注意力だけどいけそうという気持ちになる。1回WAを貰ったあと(ごめん)テストケースを見られることを思い出し、落ちているケースを探す。(0,奇数)みたいなケースが考慮できていないとわかり、実装して通す。ここまで90分で、8位くらいだった気がする。
ここから苦しい時間が続いた。Fは誰もわからないので捨て気味に。Hをこるとんが考えて、Gを僕とrisujirohで検討する。凸包から始めて、何らかの探索をするという方針まではrisujirohが立てていた。risujirohが幾何テンプレを書いている間に、詳細な方針を考える。凸包のアルゴリズムが動いていそうなことを確認した後、再度方針を立て直す。ここはかなり苦悶したが、「上位K番以下は持たなくてよい」ことに気づき、bfsを提案する。よく考えると「探索の深さはKまででよさそう」ということもわかり、計算量解析は怪しかったがrisujirohが不可能実装ではないと言うので実装に入ってもらう。僕は隣で見ていた。実装方針に悩んでいたので、priority_queueを用いた方針を提案。受理されるが比較関数を渡すのがうまくいかず(僕はそういうときは構造体を書いているのでそうじゃないときにどうするのかわからなかった、だめ)、risujirohがsetならわかるというのでsetでやることに(なにこれ)(重複除去を勝手にやってくれるので結果的にはよかった)。この辺からHを諦めたこるとんも加わり、3人体制で実装に入る。bfsパートはbfsだったのだが、探索を打ち切る実装が思いつかなかった。ここでこるとんが探索の深さを明示的に管理することを思いつき、書ききる。サンプルを試すと-1の処理を忘れていたので追加し、再度サンプルを試すと合う。やるしかないのでテストをダウンロードして実行すると爆速で終わり投げるとテスト1が通る。「これ通ったらやばい、マジ…?」とか言いながら興奮気味でテスト2を投げる。通る。さすがに嬉しくて3人で肩を組んだ。
残り10分とかだったので終わりムード。順位表を見たら6位(上に参加資格なしのチームがいた)でよかったのではという話をしつつ反省会した。
今日はチームとしてとても良く動けたと思う。CDEは誰かができないというものを他の人が1問ずつしっかり通した。Gは誰かが欠けていたら通らなかったと思う。これなぜか全くバグらなくて1発で通ったのかなりすごいと思う。Gは2チームしか通っておらず、FAもとることができた。2チームしか通ってないので作戦ミスにも見えるが、あの状況でGに振ったのはチームとしては正解の選択肢を取れたと思う。一人ひとりが力を発揮できるセットで、チーム戦ならではの瞬間が多くあり、充実した3時間だった。
個人としてはABを比較的すんなり通せた(Bはもっと早く書けたはずだが)。Cをしっかり通せたのもよかった。Gの解法にも貢献できて、自分としては十分仕事ができたかなと思う。あと2週間で少しでもできることを増やしたい。
結果的な順位はよかったが、模擬国内予選に参加していなかったり、人が揃っていない有力チームが複数あるので全く油断できない。でも、このタイミングで良い感触を得ることができて本当によかった。本番はせめて、「これでだめなら諦めがつく」くらいのパフォーマンスを出したい。
okimochi練(6/29)
3時間2セット。
RUPC2017Day3
こるとんがAを通す。僕がBをやろうとするがうーんとなり、DがいつものDijkstraらしいのでBをこるとんに渡してDを受け取る。risujirohがCを通したあとDを僕が書く。問題を誤読していて(え…)焦るがまあ通る。その後Eが遅延セグ木を使いたいらしいので、遅延セグ木を写経するが、僕がiと1を見間違えていたので大変なことになった(え…)。Eが通りFをこるとんやるが、木のハッシュに問題があったらしくそのまま終了。Gもやろうとしていたが、短時間でやるには場合分けが厳しかった。
国内予選2014
Aをこるとんが通す。B余裕じゃんと僕がやるが何故かバグる。こるとんに見てもらって通る。Cが通る。この時点でこるとんがDもEもわかったらしいので実装の早さも考慮して丸投げして通る。その間に他の2人でFとGを見るが、まあわからない。DEが終わったこるとんがvalidationさえできればあとは貪欲とわかり、その条件を考える。誰かが必要条件を見つけ、十分性は怪しいけどこれしかないので実装が始まる。TLEが解消されなかったが、AOJからテストを引っ張ってきて手元実行してdiffを取ったら大丈夫だったのでACと判断。Gはいろいろ案が出たが結局だめだった。
Fが通せたのが偉く、成績としては4位相当だった。Fは通すだけならそんなに難しくないと言われさすがだなあと思った。ところで1位はあのチームで、ぶっちぎりの1位だった。こわい。
個人の反省としてさすがに自分の実装でバグらせすぎ…。本当にまともにかけるのがDijkstraしかなくないですか?チームとしては全体的に今後のムーヴの判断が早く適切になっていると思った。
AGC023-D:Go Home
こういう問題を解いていると競プロ楽しいなと思う(やはりパズルが好きなのでは?)。
問題
解法
すべてのマンションが地点から見て同じ方向にあるときは自明なので、そうでない場合を考える。
初期状態から考えるとつらい気持ちになるので、終了状態から近い方から考えてみる。から見て最も座標の小さい側にあるマンションの住人と、最も大きい側にあるマンションの住人だけが残った状態のバスは、今までのバスの軌跡によらずとの大小だけでバスの動きが決まる。仮にだとすると、マンションの住人はマンションの住人がバスを降りるまで、つまり一番最後までバス取り残されることになる(かわいそう)。そうなると、マンションの住人の目標は、マンションの住人にできるだけ早くバスを降りてもらうになるので、彼らの目標はマンションの住人と同じだと考えてよい。するとマンションのことはもう考えなくてよいから、マンションからまでだと思って同様に考えればよい。このことを最初に述べた自明な形になるまで繰り返すことで、逆順でバスがどのように動くかを決めることができるので、この問題が解ける。時間計算量はになる。
実装
Submission #6134992 - AtCoder Grand Contest 023
実装が一番難しかった。実装で明示的にバスの動きを追わなくてもできそうだけど、そうしてしまった方が実装が楽だった。
diverta 2019 Programming Contest 2-D:Squirrel Merchant
方針立ってから時間かけ過ぎた...。
解法
まず1つの金属について考える。例えばなら、Aでどんぐりを金にして、Bで金をどんぐりにするという行為以外ありえない。このように不等号の向きを見れば、ある程度取るべき行動が確定する。金属の種類の違いを無視すれば、3つの不等号の向きの組み合わせは4通りなので、これで場合分けをし、全探索をすることを考えよう。の3種類の金属をまとめてを書くことにする。
- 3種類すべてのとき、取引所Aで金を個、銀を個買うと決めると、銅を買う個数も勝手に決まる。よって、について全探索してとなる。
- 3種類すべてのとき、1の場合と同様にすればよい。
- となる金属が2種類のとき、取引所Aでその2種類の金属をいくつか買い、取引所Bでどんぐりにした後、である金属を買えるだけ買い、取引所Aでその金属をすべてどんぐりにするという行動を考えればよい。したがって、最初に取引所Aでとなる2種類の金属をそれぞれいくつ買うかを決めることでの全探索が可能となる。
- となる金属が1種類のとき、取引所Aでその金属を買えるだけ買い、取引所Bでその金属をどんぐりにしてから、である2種類の金属をうまく買って、取引所Aですべてどんぐりにするという行動を考えればよい。全探索すべきは、取引所Bでの金属の買い方だが、これは片方を何個買うかを決めればよいので、取引所Bについた時点でのドングリの個数がネックになる。これはであり、全探索して間に合う。
これで問題を解くことができた。
実装
Submission #5936228 - diverta 2019 Programming Contest 2
算数パートが注意が必要で6WA...。この実装は「ある金属を買うのに使うどんぐりの数」をとしているので参考にする場合は注意を...。
ナップサックdpでできるらしい。類題を解いたことがあったのに見えなくて悲しかった。
CODEFESTIVAL2018 Final G:Chicks and Cages
う
解法
dpっぽい雰囲気はあるが、何の整理もなしにはうまくいかない。まず、ある鳥かごに振り分けられたひよこの集合をとする。この鳥かごで発生するストレスの値はである。つまりストレスの値の総和は、ひよこの大きさに、そのひよこが入っている鳥かごのひよこの数を係数としてかけた値の総和ということになる。これがわかると、小さいひよこにできるだけ大きい係数を、大きいひよこにはできるだけ小さい係数をかけたくなる。実際、2つのある鳥かごに振り分けられたひよこの集合をとし、とする。このとき、かつがなりたつの組があるとき、ひよことひよこを入れかえることで、ストレスの総和を小さくできる。このことは、の小さい順にひよこを鳥かごに振り分けることで得られる最適解が存在することを意味する。
ここまでくると、を昇順にsortして、:番目のひよこを個の鳥かごを用いて振り分けたときの最小値 というdpができそうという気分になる。更新式は、の累積和をとして
である。しかしこれでは)となり間に合わない。この遷移を高速化できないだろうか?
「大きいひよこにはできるだけ小さい係数をかけたい」という気持ちを思い出そう。この気持ちに立ち返ると、が大きくなるにしたがって、調べるべきは小さくなっていくのではないか?という予想が立つ。実際、sortした後であれば、番目の鳥かごのに入ってるひよこの数をとすると、最適解においてはが成り立たなければならない。これを勘案すると、を更新する際には、の値としてまで考えれば十分であることがわかる(みたいな状況がが最大となるときに考えられる振り分け方だから)。従って更新式は
となる。このときの計算量は、計算量に調和級数が現れる形になるのでであり、十分間に合う。
実装
Submission #5713037 - CODE FESTIVAL 2018 Final
dpそのものは基本的だと思う。
ABC128-F:Frog Jump
コンテスト中に解き切りたかったけど、細かいところも少し要求されるので厳しかったかな...。
解法
蓮以外の点に行かないようにしないといけないので、まずという条件が得られる。この下で、を決めたときの動きを観察すると、以下のように書ける。
ここで、とおけば、
と書ける。つまり、さえ決めれば動きが定まり、より、あり得るの組を全部試しても、各組をで調べることができれば全体でで間に合う(計算量が調和級数になるやつ)。実際、を固定してを1増やすと、新たにに訪れることができるようになるから、各に対しての小さい順に探索を進めればよい。
問題は、一度訪れた蓮の上には再度訪れることができないという条件だ。再度訪れることがあり得るについては探索してはいけない。このようなことが起こるの条件を考えよう。動き方から、このようなことがあるとしたら、非負整数の組が存在して、という等式が成り立つはずである。これはと変形できるので、まずがで割り切れると危険だということがわかる。さらに、この等式を満たし、かつが最小になるようなの組は当然である。このことより、であれば、がで割り切れても、蓮を再度訪れるということが起こる前にの蓮にたどりついてゲームが終了する。したがって、条件を満たすの組の条件は以下のとが同時に成り立つことである。
- がで割り切れない。または、がで割り切れるが、
実装
Submission #5662288 - AtCoder Beginner Contest 128
実装的には「条件が満たされないときに答えを更新しない」という書き方をした方が楽。
実装はたったこれだけ....。考察力が試される良問。
Educational Codeforces 65-E:Range Deleting
これが解けて紫になった。
解法
をsortした列を考える。この列を眺めていると、区間を消去できることの必要条件は
- 上で述べた列について、の値が未満のところまでは昇順である」かつ「がより大きいところからは昇順である」
が成り立つことである。をであるの最大値、をであるの最小値とする。すると、とが昇順に並ぶかどうかは、かどうかを見ればよく、容易に判定できる。
このことをもとに、を固定したときに条件を満たすがいくつあるかを数えよう。例えばのとき、条件を満たすの値の最小値はかつを満たす最大のである。だとしてのとき、条件を満たすの値の最小値は、のとき以上であるか、存在しないかのどちらかである。これは、であることから容易にわかる。このようにして、の値を小さい順に調べ、その都度あり得るの値の最小値を尺取り法の要領で更新することで、組の個数を数えることができる。計算量はであり、十分高速である。
実装
Submission #54221712 - Codeforces
問題を見てこれは解けないといけなさそうだと思ったので、解けて嬉しかった。こどふぉのレートが上がるのは自力がついてきた実感があって良い。