脳log[20230930]

2023年09月30日 (土) [AtCoder] 今日は ABC322 があった。コンテスト成績証。自分のすべての提出。例によって ABCDE の５完。まあまあ早め。つまり 30 分余らせて F 問題が解けなかったと。持っていないデータ構造が必要な気がしたんだけどどうかな。ではふりかえり。■A 問題「First ABC 2」。strstr が使えますかという問題。■B 問題「Prefix and Suffix」。if 文が嫌いなので場合分けではない方法で出力値を得たいけど、両方とも該当するときにゼロを、両方とも非該当のときに３を、というのがもう面倒くさくて考えることをやめたくなる。せめて逆なら。■C 問題「Festival」。A 数列の先頭を適当に弾いていきながら１から N 日目までループを回す。A 数列の末尾が必ず N だということで番兵も添字の範囲チェックもいらなくて助かる。■D 問題「Polyomino」。E 問題と diff が逆転して水色だった問題。自分も E 問題より長い 37 分の時間をかけている。とても面倒くさい問題だった。面倒だけど愚直にやるだけ。嫌いではないよ。箱入り娘(20210121)とかカレンダーパズル(20210527)のソルバーを書いたりしてる。でもこういうのはじっくり時間をかけて整理して書きたい。■E 問題「Product Development」。この DP が緑 diff って怖い。AtCoder の参加者が怖い。DP 配列を用意しようとして困ってしまった。K の上限は高々５だけど、５次元配列はなかなかにつらい。「DP だったんだけど、人類が扱うには次元が高すぎるのではないかな？ 自分には無理」と書いたときの次元数は３だった。さらに次元数(K)が入力により可変なのが輪をかけてつらい。添字を K 桁の P+1 進数にエンコードして１次元化することでなんとか扱えるようになったけど、それは人間の理解を助けるための余計な処理であって、460 ms の提出 #46108878 (konayuki さん) より 1.5 倍くらい遅くなってしまった。