HUPC2020-Day2&Day3 - クマーの競プロ精進日記

昨日のDay2を書き忘れていました。両方書いていきます。

Day2

チームメンバー：クマー、zkou

時間：5時間

問題：13問（A~Cは難易度順、D以降ランダム）

つちのこが健康診断で参加できなかったのでzkouと2人で挑みました。

考察：クマー

実装：クマー

5000兆円って久しぶりに聞いて笑っちゃった。サクッと書いて次。

考察：クマー

実装：クマー

この前のABCが頭をよぎってしまい、普通の漸化式にしばらく気付かず。zkouがBでPEを出したのでそれの原因究明をしている中、これをサッと書いてAC。行列ライブラリあってよかった。

考察：zkou

実装：zkou

PEに対しzkou「人生で初めてこんなエラー見た」

pythonの出力仕様を調べるなどしてなんとかAC。まだ序盤なので心臓に悪い。

考察：zkou

実装：zkou

私はほぼ関与してない。zkouは貪欲の方針が早々に分かったものの実装で苦労していたようだ。なんとかノーペナAC。

この4問の時点で40分が経過。2人でやっているせいか、昨日の北大セットよりも難しく感じた。

ここでしばらく次の問題が解けない時間帯に入る。E以降で1チーム以上に解かれている問題がほとんどなく、次に解くべき問題の当たりがつけられない。まあ暫定順位が高いのは嬉しいけど。

とりあえず若干解いてる人数が多いGとM考えてみるか？ということになり、zkouはG、私はMを考えることに。

考察：zkou

実装：zkou

私は何もしてない。何ならこれを書いている今初めて問題を読んだ。頑張ってノーペナで通してくれたぽい。

考察：zkou

実装：zkou

私はMの進捗が得られないまま、続々と増加するMの正解者数を見て焦っていた。そんな中Gを解き終わったzkouがこのIをあっさり通す。私は良く分からなかったが平方完成して普通に解くだけだったらしい。

考察：zkou、クマー

実装：クマー

Iまで通したところで、やっぱりこれを2人で確実に解こうという話に。頂点ごとに見ればNimのように別のGrundy数をもつゲームが並列しているだけだから、Grundy数さえわかれば勝利条件はxorで判定できると気付く。

ではそのGrundy数をどう求めるのか？これにしばらく悩み続けた。色々考えた後、結局Grundy数はO(logN)だろうから各頂点に対して200程度のboolテーブルを保持していれば十分という話になった。しかしこの計算量はO(200N)でやや大きいし、Grundy数がO(logN)で抑えられることも自信が持てなかったのでACしたときは本当に驚いた。競プロをやっていて自分のACにこれだけ驚いたのも初めてかもしれない。

この時点で残り77分。しかしここから新たに問題が解かれることはなかった…。

解けなかった問題たち

解けなさすぎてキリがないので、主に考察したものだけ。

考察：クマー

実装：クマー

日本語をよく読めばやるだけなのは分かる、分かるが…。

ステージ全体が回転することに実装途中で気付き、やる気がなくなった。

考察：zkou

実装：zkou

解けそうな見た目をしてる。zkouが自前の遅延セグ木で殴ろうとしたが、結局それは嘘解法だったらしい。しかし半端にサンプルが合ってしまうせいでそのことに気付かず、大量のペナを吐いているうちにコンテストは終わった。

結果：7完23位

f:id:kumakumatime:20200916224750p:plain

全体的に解けなさ過ぎて辛いセットでした。さすがAOJを作った会津大学だなあ、2人でこれに突っ込むなら橙くらいになってからのほうが楽しめたのかなあ、と思ったり。青2人チームにしては頑張った、ということで。

2人でやってみて分かりましたが、3人の時に比べて1問に掛けられる考察がどうしても浅くなっちゃいますね。結局まともに相談したのはMだけだったので、チーム戦の良さを生かせなかったのかなあと思いました。

Day3

チームメンバー：クマー、zkou、つちのこ

時間：5時間

問題：13問（A~Cは難易度順、D以降ランダム）

有志セット。つちのこ復活で、昨日よりは戦いやすくなるかな？と期待していました。

考察：つちのこ

実装：つちのこ

サッと書いてAC。

考察：クマー

実装：クマー

なんか既出臭いな～と思ってたらもうあったみたいですね。投げたら謎のMLEとか出てきてキレそうになりましたが、普通に自分のコードが間違えていました。

考察：つちのこ

実装：つちのこ

Bが詰まっている間につちのこがこれをすぐに閃いて実装したところサンプルが合わず、あれれ？あれこれ考えているうちにかなりの時間が過ぎてしまった。私は結局最後まで分からずだったが、最終的につちのこが「え～これ簡単じゃん、もっとあっさり解くべきだったごめんなさい～」って言いながらAC。

考察：zkou

実装：zkou

難易度順とは？zkouが延々コーナーに引っかかってペナを出してた。「もうそろそろ飽きてきたんだけど」と言いつつ4回目に出したコードでAC。コードを書いている本人よりこちらの心臓に悪い。

考察：zkou

実装：zkou

Mの方針で悩んでいたらzkouが「F書いていい？」。なんか数分でパッと書いてサッとACしてた。終わってからコード見たけどめっちゃあっさり終わってて、何が何だか良く分からず。

考察：つちのこ、クマー、zkou

実装：クマー

難易度の割に苦戦した問題。想定解のDFSでならし計算量O(3^M)は早々に分かったのだが、「3^15って10^7やぞ？これTLE食らうやつでは？」と思い実装しなかった。そしてその間に嘘解法を思いつき、投げてみるとTLE。サンプル39/46まで通ったからあとは定数倍かと思って定数倍を高速化しようとしたが、あえなく撃沈。そこへFを終えたzkouがやってきて最初の解法を再び指摘され、やっぱそれしかないか～と言いながら私が書いた。ところでこれなんでこんなにTLキツくしたんですか？

考察：つちのこ、zkou

実装：つちのこ

私は関与してない。落ちてるカツは汚いよ。

通話を横で聞く感じでは割とあっさり方針が立ってたのにもかかわらず、dpの遷移が複雑で添字をバグらせまくったらしい。デバッグだけで数十分吸われたがなんとかAC。

チーム戦やってみて思ったんですが自分が関与してない問題でチームメイトがACするとめちゃくちゃ嬉しいですね。なぜか自分のACより嬉しいです。

考察：クマー、zkou

実装：クマー

他の2人がGを解いている間に何となくできそうなこれを眺めていた。求める値は

1 + (2番が1番に勝つ確率) + (3番が1番に勝つ確率) + ... + (n番が1番に勝つ確率)

になることがすぐに分かったのであとは2次元dpと累積和で…と思ったがこのままではdpの遷移がO(L^2)になってしまいそうで困り果てた。

頭を抱えていたところにzkouがやってきて、冪級数の係数として表されるのでは？という指摘をしてくれた。さらにNTTはどうかと言われ、なるほどと思ったがそれでも計算量がO(L^2)から落ちない。さらに考えた末に私がpriority_queueで上手くマージすることで計算量をO(L log(L))くらいに落とせることに気付き、考察が終わった。

NTTもマージテクも初使用だったので不安だったが意外にも大してバグらず、サンプルが合った！！と感激して提出するもテストケース1でWA。サンプルは合ってるやろ！おい！と言いながら連投するも、WAが重なっていく。どうやらテストケースの1つ目はサンプルとは限らないらしい（？？？）。途方に暮れていたところ、つちのこがヤケクソで#define int long longを付けて提出したところ、AC。#define int long long教に入信します…。

（当時はどこがオーバーフローの原因が分からなかったが、どうやら簡単な掛け算で１つだけlong longのキャストを忘れていたらしいことに今気付いた。8ペナもったいねえ…）

その後Eの問題文がこっそり訂正されていて、訂正前の問題文のせいで解けていなかったのでおい！！！と叫びながら実装しようとするも、間に合わず。コンテスト後に通しておきました。1時間くらいかかったけど。