【AtCoder】 基礎が大事ですね…ABC363

　どうもRustを本格的に採用し始めた緑抄と申します。一応今回は勝ったには勝ったのですが反省点しかないので、反省会をしていきます。

A問題 - Piling Up

A - Piling Up

　とりあえずmod100を引けば良さそうですが100の倍数の時だけは100あげないと上がらないのでそこだけ注意。
実装例

B問題 - Japanese Cursed Doll

B - Japanese Cursed Doll

　制約が全て100以下なので毎日愚直にシミュレートして問題ないのでfor文を回して判定します。
実装例

C問題 - Avoid K Palindrome 2

C - Avoid K Palindrome 2

　順列全てについて長さKの回文を含むかを判定するとき計算量は$${O(N^{2}N!)}$$とかになりますが$${N\leq10}$$なので最大でも$${9.1×10^{8}}$$未満なので十分間に合います。なので全探索します。時間がかなりきついのでPythonから乗り換えててよかったです。Pythonなどでやる場合はうまく枝刈りしないといけなさそうです。
実装例

D問題 - Palindromic Number

D - Palindromic Number

　体感難易度がバグレベルに高かったです。回文数自体を攻めるより回文数を生成する方法に着目してみたほうが法則が見出せそうなのでその方針で考えます。すると回文数は1以上の場合桁数が一つの数字に対して全く同じものを反転させてつけたものと一の位を重ねたものの2パターンがあり同じ桁の数字に対してはその順番に作られ、重ねたもの→重ねないものの順に出てくることがわかります。なので最初の0だけ除いた時その数字が何番目に位置するかからその数字の元が何桁で重ねる場合か否かが特定し、生成すればいいです。ただバグらせやすいので理詰めの計算は慎重に行いましょう。
実装例

E問題 - Sinking Land

E - Sinking Land

　突然のグリッド問題。どうやら周囲が海面から水が流れ込んでいくイメージのようです。重複なくシミュレートすれば$${O(HW)}$$に収まるのでそのまま実装できそうです。ただ周囲に海水が流れ込んでいないマスには海面がそのマスを超えていても流れ込まないので、周囲に海面があり、その海面以下であるということを判定することを考えればいいです。なので海面に接するマスはその高さの添え字のVecに入れて年毎に新しくそのマスを追加し、そこからBFSなどで判定していけばいいでしょう。Dより簡単な気がします。
実装例

F問題 - Palindromic Expression

F - Palindromic Expression

　D問題に時間を使いすぎたため時間がなく考察が詰められませんでした…。積の形に分解して回文になるってどういう場合だよと思っていましたがそもそもが回文ならそのまま、回文でないなら対称になる二つの約数を作れるか探索して、そうでないなら不可能という条件にすればよかったのですね。因数を作っていって偶数個になったとしても*1*が真ん中にあっても関係ないですから。再帰がうまく組めたかは微妙ですが…

　ということで振り返ってきましたがとにかく典型は高速にできるように訓練して考察も典型化、立式をするのに慣れるのが大事そうですね。やはり物量の練習しかなさそうです。 ADTも出られるだけ出てみることにします。