脳log[20240323]

2024年03月23日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）があった。くやちい。F 問題を通すのに２分13秒足りなかった。こんなに悔しいことはない。ではふりかえり。■A 問題「Adjacent Product」。Array#each_cons を使います。■B 問題「Piano」。数が重要なのであって、W=5/B=2 のとき wwwwwbb が見つからなければいけないわけではない。wwbwwbw でもいい。なんで問題を繰り返してるかって？ わからなかったからだよ。問題文のせいじゃなく思い込みのせいだよ。累積和でやるの？ ややこしくない？ とか思って先に CD 問題をやった。そのうちに愚直解法が許されると気がついたので愚直に文字列を連結して、愚直に文字の数を数えた。愚直といっても、初期文字列のサイズ(12)×(B+W)≦2400 だけどね。他の提出を見るともっと豪快なのがいっぱいあった。■C 問題「Σ」。1 から K の総和は K*(K+1)/2。A のうち K 以下であるものを選び重複を取り除いたものの総和を引く。■D 問題「Gomamayo Sequence」。まず、00 もしくは 11 にする場所を決めます。そうすれば、左に向かって 010101...を作るコストと右に向かって 010101...を作るコストの和、もしくは、左に 10101...、右に 10101...を作るコストの和が答えの候補になる。N-1 個の位置のペアに対して、答えの候補が２つずつ。そのうちの最小が答え。やりたいこと知りたいことが明らかになれば、うまいこと累積和を作って単位時間で答えの候補を求める。■E 問題「Paint」。逆順に考えれば上書きされずに塗れる数がわかる。あとは数えて記録するだけ。■F 問題「SSttrriinngg in StringString」。f(S,N) に対してどういう操作がしたいだろうか。ある文字について、あるインデックス以降で最初に現れる位置が知りたい。そして、そこから同じ文字がある個数現れるまでにインデックスがいくつになるかが知りたい。そのインデックスが f(S,N) に収まっているかどうか。これを k に対する二分探索の中で T に沿って判定する。罠がいっぱいあったんだよ。N は S のサイズではない。N はサイズではない(２回目)。二分探索の中で二分探索を行うことに警戒感があって、最初は対策をしていた。このとき参考にしたものと同じ(「261 ms の提出を読んだ。A 数列の値から添字を得る逆引きインデックスを事前に作成するのがキモであるようだった。A の値の範囲は 10000 以下なので、それが配列のサイズとなったところで大した大きさではない。 言われてみれば、そうだね、という感じ(だけど思いつかなかった)。313 ms の提出も 328 ms の提出も 329 ms の提出も、同じ下拵えをしていた」)。でもなんだかいらない気がして途中で消したんだよね。そして TLE (#51604101)。案の定だよ。対策は知っているのですぐに出し直したけど、TLE に混じっていた WA×8 が手つかずだった (#51606089)。25、26行目が機能していないのが明らかなんだよね。二分探索をやめたから is_j が nil になることはない。終了後２分13秒で通ったんだけど (#51610081)、何に時間がかかっていたかと言えば、サンプル３の答えが１ずれていた。その原因が 26 行目の条件式 if is[is_j]<i%Sz に等号が付いていたこと。時間に追われる中でその微妙な差違に気が付くのは無理でしょう。なまじ解けただけに時間不足が残念でならない。■コンテスト成績証。青パフォでプラスではある。しかしものたりないなあ。このチャンスを逃した今、明日の ARC からまたもう何度目にもなる落ち目が始まる可能性だってあるのに。