ABCFの4完。
F問題まじで神。
各問題
A - Tires
最後の一文字が'r'か't'かで判定すればよいです。
B - Mongeness
4重ループの全探索を書けばよいです。
C - Triangle?
3点の座標から面積を導出する公式（の一部）を使って面積を実際に計算し、0かどうかを判定すればよいです。
（が、しかし、それに気づくまでに20分以上かけてしまいました・・・）
D - 8 Puzzle on Graph
しばらくこれを考えていましたが、可能性の判定も確たる方法はわからず、移動回数の判定に至ってはまったくわからず・・・。
E - Integers on Grid
全然見当もつかず・・・。グラフに落とす系？とか思ってましたが、解説をチラ見したらDPとか書いてあって全く見当はずれでした。
F - Problem where +s Separate Digits
例えば1234の場合、1は1000の位で1回、100の位で1回、10の位で2回、1の位で4回登場します。 2は100の位で2回、10の位で2回、1の位で4回登場します。 3は10の位で4回、1の位で4回登場します。 4は1の位で8回登場します。
これには規則性があることはわかりますが、上から順に処理してもO(n2)かかるのでだめです。（たぶん）
そこで、位毎に見ていくと、1の位では1234が4+4+4+8回、10の位では123が2+2+4回、100の位では12が1+2回、1000の位では1が1回登場します。これにも規則性があることがわかります。
各桁の数の累積和をあらかじめ取っておくことで、各桁ごとにO(1)で計算することができ、合計でO(|S|)で計算することが可能となります。
まとめ
解けそうな問題をきっちり見極めて解き切れたのは久しぶりかも。
