ABC113

また間があいてしまった。

出るつもりはあるんだけど幸か不幸か週末に用事がある事が多く、平日に問題だけ解くパターンが中心になっていた。

ABCの400問題はだいたい解けそうな感じになってきたので、ARCの600+に手を付けられるようにしていきたい。

問題はABCばかり出ていてratingが上がるのかという話ですが。

A - Discount Fare

X + Y/2（ほぼ自明）

B - Palace

正解の値とAとの差の絶対値の両方を保存する必要があるのでB問題にしては面倒だなあと思いつつ普通にn回のループさせて終わり。

C - ID

ソートしてそのまま出せば良いわけではないのがやや面倒だなあという印象

年度が同じものが、県をまたいでも存在しないというのがありがたく、年度の情報をキーとした辞書型にインデックスを格納していく。それと別に、答えを格納するための初期化された配列も用意しておく。

その後、県ごとに市のリストを作ってソートし、中に格納されている年度情報からインデックスを呼び出して、答えを格納するための配列の該当するインデックスに格納していく。

ここまで書いてから走らせたら普通にサンプルが通ったのでそのまま提出してAC

D - Number of Amidakuji

全探索すると2^800なのでまあ無理。それを実装することすら面倒。

経路ごとに見ていこうかと思ったが、あまった枝の処理の数え上げが難しいのではと感じて少し悩む。

しかし、よく見るとW<=8という条件がついているため、あまった横棒の候補地は、最大でも7区画分である（1本目からそのまま直上する場合、2~8本目の間は、2個連続しなければどのように横棒を付与してもよい）。

ということでX区画分についてX-1から順に手で計算していると、3>4にするあたりで、これは3-4間に棒を置かなければX=3通り、置いたならばX=2通りとなり、フィボナッチ数列となることがわかった。（Wが小さいため手でベタ書きすることにした）

それがわかればDPを作るのは簡単。

dp[i][j] = dp[i-1][j] * X + dp[i-1][j-1] * Y + dp[i-1][j+1] * Z

X .. 左右1区間を除く領域に存在しうる横棒のパターン

Y .. 左1区間と右2区間を除く領域に存在しうる横棒のパターン

Z .. 左2区間と右1区間を除く領域に存在しうる横棒のパターン

これらX, Y, Zはさきほどのフィボナッチ数列の要素の積である。

ただし、W>=3を前提としないと左右を考えたときにつきぬけてしまう可能性があったため、W=1が自明に1であることのほか、W=2についても調べる必要があった。

無駄にDPを書いていて、これ2^(h-1)じゃない？ってなったので1~3くらいまで試したらまあそうだろうなという感じになったのでそのように書き直してサンプル問題をテスト。

そのまま提出したら一発でACでノーミス完解