AGC043

今週は珍しくStreakをつないでいた。だからわかるけど、頭の回転がいい日はなかった。どうせダメなんだろうなという思いがあった。結果としては、想像以上に難しくて何もできず「もう競プロやめるか」と冗談で思った。最後の15分だけ楽しかった(間に合わなかったけど)。のはよかったけどその前の1時間何もできてないのは悲しい。

A - Range Flip Find Route

最初の5分で何もわからないのさすがにビビる。1次元の場合で考えるまでにも時間がかかった。Bを読んだりもしながら、何か思いつくのを待つ。1*nの細長い長方形で進んでいくのも考えて、そこから細長い2つの長方形はでかい長方形にできると気づく。つまりずっと黒いところを進むならノーコスト、白から黒に切り替わる回数だけ見ればいい。これはよくあるDP。サンプルが通らないが、最初のマスに降り立つ前に白マスにいる扱いにしないといけなかった(知ってたけど忘れてた)(最近ほんとWAが多いんだよね(今回はサンプルに助けられたけど))。

(解説放送を聞いて)パスを固定するという考え方かあ。

B - 123 Triangle

すぐに実験を始めて、きれいな絵が出てくるのを見ていた。1,2,3は全体から定数を引いて0,1,2としていいのはすぐ気づいた。逆から考えると2からは0と2しか生えないということになぜかなかなか気づかなかった。色々頑張ったけど何も出てこず。2時間近くあったのに、もう15分しかないというところで、(端だけでなく)各要素について答えへの寄与を調べてみた。するとシェルピンスキーのギャスケットが出てきて声が出た。どうにかして指定座標の値がわからんかと思っていたが、けっこう経ってパスカルの三角形の偶奇なことを思いつく(思い出す)。全力で実装するがサンプル合わず。最後の5分でめっちゃ疲れたし感情も大きく変化した(にぶいつらさが激しいつらさになった)(この楽しい15分間がなぜ1時間前に来ないのか(いつもそう(誰か対策教えてくれ)))。終了後、自力ACはできたけど、実装にはかなり時間がかかった。