AGC033

ぼんやりした回。D以降が解けない前提だと早解き回。あまり体温も上がらず。自分は3問遅解きした。ハマったりせず3完できたのが大きい。

A - Darker and Darker

逆に黒いマスから見れば、だんだん広がっていくやつ。解法は1分くらいでわかったが、実装に10分近くかかる。BFSはしっかりライブラリにしとかんとな(あまり使う機会もないし解く速度が要求されることも少ないからライブラリにしづらい)。今気づいたが実行時間制限1秒か。

B - LRUD Game

問題の性質を地道に書きだしていく。そして、縦と横のゲームがあり、高橋君はその片方に勝てばいいと気づいた。左右のゲームだとして、左に脱出するゲームなら簡単だ。しかし、左ばかり気にして右に逃げられたりするからややこしい。後ろから見ていくアイデアはあったが、まとめて最後の何個かを累積和で見るとか、最終手はわかるがその前は?とか色々あるのでまとまらない。解ける気がしない。後ろから見るのと順方向に見るのの本質的な違いもわからない。結局、色々やった挙句、青木君が勝つ範囲を後ろから更新していけることに気づいた。

C - Removing Coins

誤読してて問題を読むのに苦労したが、サンプルの様子を見てシュッとコインが吸い込まれるのを思い浮かべそのイメージで読んだらわかった。だんだんグラフが小さくなっていく。頂点に複数のコインがあっても関係ない。まず、減る頂点数に注目した。ただ、木の様子が指し手によって全然変わってくるので何もできそうにない。とりあえずもう少し性質を調べると、選んだ頂点を根として見たときの葉ノードが消えるんだ。つまり、葉ノードを選ばなかったときはどこを選んでも同じことになる。葉ノードを選ぶとそこを残せる。解き始めのころ「グラフ 木 重心 中心」でググっていたのだが、それと併せて「直径」が浮かぶ。この操作で木の直径は1か2小さくなる(0や3以上はないという意味)。葉以外を選べば直径の両端が消えるので2小さくなるし、直径の端であるような葉を選べばもう片方の端が消えるので1小さくなる。直径が1以下の葉しかないケースは簡単なので場合分けすればいい。直径一発で行けるこの問題ヤバいし、直径を思いついた自分もヤバい。ほんとにそんな保存される性質あるのと疑ったけど、確認すると確かにそうなっている。不思議。

D - Complexity

色々やったけどできなかった。残り10分のとき「あと10分で1000点が解けるわけない」と時間を無駄にしてしまうのが何とかならんかなあ。実行時間制限とメモリ制限を見て、4乗DPみたいのがあってそれは通さないということなんだろうなあと思ったが。それを定数倍高速化していけないかなとか。1次元の場合を解いて、それを含むようないい感じの2次元を。境界線の数とか。DPはあまり考えたくなかったが、それ以外が無理なのでわりとDPばかり考えてた。市松模様でもけっこう小さい「複雑さ」で済むので(1byteに収まって)省メモリできるけど、そもそも4乗DPもわからんしなあ。