脳log[20220116]

2022年01月16日 (日) [AtCoder] 精進。キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)-E「Swap」(黄 diff)。「D 問題ダメでした」の回の ABC なので E 問題は読んでいなかった。考えたのはどうやって状態をまとめることができるか。並び順を区別してしまうと、たとえば K,E,Y がそれぞれ 10 個ずつ使われている場合に 30!÷10!÷10!÷10! > 5.5 兆通り(本当？)の文字列を考えないといけなくなって間に合わない。並びではなくて、それぞれの文字をいくつ使ったかと、それだけ使うのに何回の操作を要したかの組み合わせを考えることにした。たとえば K と E と Y を１回ずつ使って長さ３の文字列を構成することを考えると、KEY,KYE,EKY,EYK,YKE,YEK のそれぞれを作るのに要する操作回数は同じになる場合も異なる場合もあるので、操作回数ごとにまとめて場合の数を記録する。それら操作回数と場合の数のペアが (K×1;E×1;Y×1) という(長さ３の文字列がとる１つの)状態に対応する。これを長さ０の文字列から始めて１文字、２文字と遷移していく DP で。■提出 #28591194 (AC / 1008 Byte / 92 ms)。1007 Byte を書き下して実行してみれば文字列が閉じていないというシンタックスエラーを除いてバグ無しでびっくりした。入力される文字列長が最大で 30 だから内側のループで線形時間の愚直スキャンをしても許されるのが優しい。だからこその ABC-E だったのかもしれないけど……(E 問題はおろか D 問題も解けなかった)。■こちらの提出(#27283710)によると公式解説動画でメモ化再帰を紹介していたもよう。すっごく短く書けるっぽい。長くはなったけど 92 ms は Python と比べても速いみたいなので良しとしよう。■ダメだった D 問題は「実は……」と解説に書かれている内容を鵜呑みにして AC をとっただけなので日記にはなりませんでした。提出 #28342280 (AC)。■ところで、E-Swap に提出した AC スクリプトにおける I 変数は、昨日あった HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）-C「The Kth Time Query」のためのデータと同じ構造をしている。C 問題が E 問題を解く道具になっていることが確認できるのはいいね。