脳log[20230513]

2023年05月13日 (土) [AtCoder] 精進。今日あったパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）-E「Pac-Takahashi」(青 diff)。最初はメモ化再帰だと思った。「順列総当たりが許されない制約(N≦16)だけど、A<B、A>B を区別せずに２回目以降の数え上げがサボれるなら許される」制約だったから。でも実装を始めるとパラメータが多くてうまくメモできなかった。そのうちに TSP とかワーシャルフロイド法が見えてきた。■最初の提出 #41382752 (WA×19)。無効値が -1 と T+1 の２種類あって、-1 がうまく扱えていなかった。■２番目の提出 #41386679 (WA×5)。パックマンの餌が１個もない場合に答えが nil になってしまっていた。■３番目の提出 #41392115 (AC / 3117 ms)。無効値を T+1 に統一したり多重ループの一番深い部分を効率化するなど清書しているうちに WA×5 の原因がひらめいて、制約を確かめたら間違いなさそうだった。終了から５分３秒後の AC。一番悔しいやつ。■コンテスト成績証。上がるんだ……。喜べないかな。■■■ABCD のふりかえり。A 問題「Overall Winner」。Array#tally で集計して出現数を比較する。同数なら最後の文字を見れば答えられる。Array#tally を使うとき出現数が 0 のときに nil が返るのが予想外で実行時エラーを起こしがち。■B 問題「Fill the Gaps」。隣接２項を見てあいだを補完する。Gateway Timeout のせいで最初の提出は虚空に消えた。その後も E 問題で提出が消えたり、消えたと思わせてちゃんと WA になっていたりした。だから再提出前には提出一覧を確認したんだよ、ペナルティを重ねないために。■C 問題「AtCoder Cards」。これも Array#tally で集計した。'atcoder' の各文字に対してはオールマイティ(@)が使えるが、それ以外の文字は出現数が正確に一致していなければいけない。数の一致とオールマイティの数が足りているかを確かめた。■D 問題「Bitmask」。すべての ? が 0 だったとして可能な最小値を求めて N と比較する。あとは最上位の ? から順番に 1 に変えてみて、N を超えない限りはさっきの最小値に加えていく。こういう数の扱いは BIT#lb メソッドの実装でなじみがある>#38427641。典型力について書かれた「chokudaiのブログ」にも言及があるよ(「この一連の操作のコストは（書き換えた要素の数によらず）2^k である。」「kを使った場合のコストは、k-1以下のすべてを使ったコストより高い」)。自分は「わかる」のではなく「知っている」だけなのだ。最小値を求めるときに String#to_i を無引数で呼び出してしまって１ペナ。