進捗
625問 → 629問
[560] [594] [677] [499]しばらく出題がおやすみのようです。未解決問題数を減らしていくチャンス？（正解数は増やしにくくなる）
感想など
・[560] 典型手法が詰まったような問題で、競プロに詳しい人ならすぐ解けそうですね。
勝敗の判定自体は易しくて、かなり前に解けていた。小さい数で計算していればすぐに分かる。そこから先の計算が、普通にやると$O(n^2)$ くらいになってしまうように思っていた。改めて考えると、有名手法そのまんまだった。扱うデータの特性を上手く扱って次元を落とす別手法もあったようだ。
・[594] 1ヶ月くらい前に解こうとして失敗していたのをやり直し。結局のところ、解かなければいけないサイズが小さいので、図形をきちんと扱える形に直せば何とかなる。以前は内角の順序対を持って計算しようとしていたが、辺に自己交差が出来て無限再帰になってはまっていた。
・[677] ここ数ヶ月の出題の中では、1週間時点での正解者数が最も少ないように思う。そこまで厳しい難易度ではないが、Eulerではいかにもグラフ理論のあれこれという問題は少ないせい？こういうのはEuler育ちの人よりも、AtCoder等で育った人の方が得意なのではないだろうか？
ぱっと見て難しそうなのは、同型類を数えなければいけないというところ。そもそも木グラフの同型類を上手に扱うにはどうするのか。木グラフの判定について軽く勉強して、そこから自然と方針が立った。とりあえず $O(n^4)$ とかでもいいから実装して検算しようとしていたら、何度も同じ計算を書いている気分になって、そこをまとめたら自然と計算量が落ちた。
・[499] 難易度 100% を撃破！
偏ったランダムウォークが与えられていて、希少側への到達確率を問う問題。左右1歩ずつの場合など有名問題であるんじゃないのかと思って調べたが、意外と見つからず。Forumでもそのような指摘は特になかったように思う。
とはいえ、方針はそれほど難しくない。計算誤差の対策はある程度必要。
