脳log[20230429]

2023年04月29日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2023 春 (ABC300)があった。自分のすべての提出。コンテスト成績証。ABCDE の５完水パフォ。C 問題からふりかえり。■C 問題「Cross」。ばってんの大きさを計って集計する。問題文がちょっと難しかった。✖印の判定条件の３つ目が「X 字の先端４点の延長にある４点のうち少なくとも１つは . である」という内容だった。理由はわかる。さもなければそれはより大きいばってんとして数えられるべきだからだ。でも本文中に「バツ印を構成するマス以外に # は書かれていません」「異なるバツ印を構成するマス同士は頂点を共有しません」という条件が書かれている。そうすると結局判定条件としては「少なくとも１つは .」だけど、実際に入力されるものは「４つとも . になっている」ということだ。別にそれで問題はない。ないんだけど、全体として過不足なく丁度になっていないことで考え漏らしがあるかと疑念が生じて考えてしまった。あとは「頂点」ってなんだ？とか。具体例を読めばグリッドの十字部分らしいとはわかるけど、推測ですよ。解答は X 字の右上がりでも右下がりでもいいので端点を見つけて長さを計る。ちなみに最初に考えた解法は UnionFind を使うもので、問題文を読むときも UnionFind が使えるかどうかを確かめながら読んでいた。でも判定が簡単そうだったので UnionFind は書かないで済ませた。■D 問題「AABCC」。来たよ、苦手な苦手な D 問題、数学(素数)、緑 diff(予想)。数字と友達になれないと TLE になるやつ。解けなかった ABC296-D「M<=ab」の反省から N の平方根の範囲で何かする制約だとはすぐに読み取った(この前はそれすらできなかった)。あとはやや長めの３秒制限を信じて打ち切りながら全列挙した。自分の提出は Ruby の中でも一番遅い部類。苦手なんだよ。■E 問題「Dice Product 3」。確率の問題。Ruby による他の提出を見ると一番早い提出がたぶんメモ化再帰で自分のと全然違っていた。自分の解法。まず、N が２と３と５の積に分解できなければいけないので因数を数える。４と６の目はひとまず無視して２と３を数える。１の目は最初からないものとして５面ダイスで問題を解く。その場足踏みはサイコロを振らなかったのと同じことなので。N が２と３と５に分解できたら６の目と４の目の数を決め打つ総当たりで、ダイスの目の並べ方を組み合わせで求めて確率を出す。解答の C 関数の定義がやや不自然だった。引数を n と rs から rs だけにして n は rs.sum で求めることにすると無駄がなかった。■F 問題「More Holidays」。解けなかったのでこれは精進。方針は、１つの x で区切られた長さ 0 以上の o の連続を、K 回連結することを考える。K はべらぼうに大きな数になりうるけど、仮に入力 S に含まれる x の個数が X 個だとしたら K/X と K%X を使ってうまく数える。罠がいくつかある。どの o の連続から数え始めるかを全探索するのだけど、後ろの方から数え始めて K 回連結したときにうっかり T の長さ NM を超えてしまわないこと。まだある。入力の先頭と末尾が o の文字で、操作回数 K が x の個数の倍数で、繰り返し回数 M が十分に大きいとき、末尾と先頭にある o の連続を一体で扱わなければいけない。