脳log[20260215]

2026年02月15日 (日) [AtCoder] 昨日は AtCoder Beginner Contest 445。愚痴と嘆息しか出ないので長くは書くまい。■A 問題 Strong Word。先頭と末尾の文字が一致することと Strong がどう結びつくのか、わかりません。■B 問題 Center Alignment。問題文を３度読んでも４度読んでも何を言っているのかさっぱりわからなかった。サンプル入出力をチラ見して雰囲気を掴んでからまた読んでみて、それでもなかなかわからなかった。脳みその盲点をつくようなフォーマットで書かれていたとしか思えない。奇数長の文字列の左右に同数のパディング文字を補って、すべての入力を同じ奇数長の文字列に整形する。Python をメインにしている人の提出で知ったんだけど String#center というまさにこのためのメソッドが Ruby に存在していた。いつからの新参なのかとリファレンスを遡ってみたら、Ruby-1.8 時点ですでに存在していた(☞)。1999年発売の『オブジェクト指向スクリプト言語 Ruby』のリファレンスを見てもやっぱり載ってる。完全に J(ava)Script における String.prototype.strike メソッドや String.prototype.anchor メソッドの類いだとみなして無視していたな。全く存在を認知していなかった。■C 問題 Sugoroku Destination。今回の問題児。解けなかった。10 の 100 乗回移動するという。いわゆる「非常に大きな数」であり具体的な数値に意味はないのが通例だけど、この問題ではどうか。ループがあるならループのどこで停止するかは１、２の差が影響する。ループがないように値の範囲に制限があるかなと制約を見直したけど、特に制限はなかった(←間違い！)。問題文を読み返しても特記事項はなかった。10 の 100 乗のビット長を出力してみたら 300 とちょっとで、意外に少ないと思ってしまった。でも TLE だった (#73298781)。300*N≦１億５千万だから、Ruby には桁が１つ多い。日が改まってから他所で i (アイ) と 1 (イチ) だと読んでもう一度問題を開いたけど、最初はやっぱりわからなかった。目をこらしてやっと Ai の下限が i だとわかった。決して老眼ではないんです。室内用の眼鏡は 15 年以上前に作って５年以上前に一線を退いた度の合っていない眼鏡なんです。視力検定、注意力検定はやめてね。AC (#73346461) と TLE との差分はステップ数が 10**100 か N かという違いだけ。いち早く AC を出していた人の提出によると、より最適な解法は数列を逆順に一度なめるだけらしいです。UnionFind の Find 関数を根に近いところから呼び出していくから再帰が必要ない、みたいな流れ。鮮やか！ そうだよな、C 問題だもんな。■D 問題 Reconstruct Chocolate。貪欲です。候補となるピースをソートしたけど、実はソートはいらない気がしてきたな。どうだろ。■E 問題 Many LCMs。答えは合います。時間が間に合いません。TLE×18、TLE×16。要素を１個省いたとき、その要素が全体の LCM にどれだけ寄与しているかを計って取り除く(割る)。そのために素因数ごとに最大の指数と２番目の指数を記録した(１位２位が同値の場合は同じ値を記録する)。最大の指数をまとめあげたものが LCM になる。取り除く要素が最大の指数より小さい指数を持っているならその素数に関して LCM への寄与はゼロ。最大の指数と同じ指数を持っているなら２番目の指数を参照してその差分だけが LCM に寄与している。緑 diff で最後の最後まで解けなかった Coprime もそうだったんだけど、とにかく時間が厳しい。やり方はいろいろあるけど間に合うものがほぼない。Ruby におまかせの require 'prime'、Integer#prime_division とか、約数列挙とか、素数を列挙してからの試し割りとか、だいたい通らない。だけど絶対に通らない問題というのは数えるほどしかないし(少ないけどあります)、うまいやり方で余裕で通す人もいたりするものだから、結局は己の至らなさにはね返ってくるのであって、不満のはけ口はありません。残念。精進しような。■D 問題。Ruby で一番最初の AC であるこちらの提出 #73307835。答えの座標が X と Y のどちらか一方が１に固定されている。なんでそれでいいのかわからなくてスクリプトに手を加えてピース番号をグリッドにプロットしてみたけど、番号に重なりはなかった。全然わからない。……。お風呂でイメージしてきた。(1,1) から遠いところから切り落としては全体のサイズを縮めていく、という過程を考えれば、どのピースも (1,1) から右または下にどれだけ離れているかという尺度で特定できる……らしいですよ。■E 問題。Ruby で最初の AC がこちら (#73334218)。require 'prime' しないで素数の倍数に素因数をメモすることで素数を列挙している。自分は素数を判定する方法としてこのやり方を知っているけど、素因数を列挙するための情報源としての利用法は知らなかった。素数ではない(合成数である)数のスロットには素数のひとつが記録されていて、それにより自身が素数ではないことが知れる。それだけではなかった。ここで合成数を n、記録されていた素因数を p として、n = n/p を繰り返して n が 1 に至るまでには素因数の指数の和と同じ数のステップが存在し、その過程ですべての素因数を指数個分ずつ拾い集めることができる、ということらしい。すご。■まねしたのに通らへん。提出 #73350310 (TLE×2)。書き方か。step メソッドを while ループに書き換えたら通った。提出 #73350361 (AC / 1830 ms)。やはり while。while 文は(ブロック付き)メソッドより速い。■F 問題 Exactly K Steps 2。何重にも重なったループを書こうとして書き切れなかったけど、行列の文字が見えたら行列の掛け算をイメージしてループを書く助けにできる。提出 #73353560 (TLE×22/AC×21)。ダメです。行列計算は N の３乗だったような気がしますが、log(K)N^3≦3000万で通りませんか。F 問題で行列計算やるだけは考えが甘いですか。■E 問題の高速素因数分解に関連して ABC177-E の解説が挙げられており、それがまさしくさっき言及した Coprime の問題だったんだけど、えっと、自分はまだこの緑 diff の問題を通しておりませんでした。緑埋めをしているときに埋め切れず、水埋めをしているときにも何度もふりかえってははね返され、そして現在に至る。もう諦めて忘れてしまったみたい。■精進。ABC177-E「Coprime」。Coprime と名の付く類題に至るまで苦手意識を植え付けられたいわくつきの問題。Coprime 恐怖症の元凶。今日最初に書いた解答は ABC445-E にならって素因数分解をしてからそれを使って判定をするものだったが、これは全く望みがなかった。なぜって pairwise coprime を判定するのに全組み合わせを考えると O(N^2) になるから。N の上限が 100 万だというのにそれは無理。５年前の自分ですらそんな馬鹿はやっていなかった (#19442249)。あらためて考えると、各素数について、それを因数とする A 数列の要素がいくつあるかを数えて、その最大値がいくつかを見れば良い。最大値が 0 なら A 数列はどの要素も素因数を持たない(すべて１)ということ。最大値が１なら、どのペアをとっても共通の素数を因数に持つことがないということなので pairwise coprime。最大値が N なら全要素に共通の素因数が存在するということなので not coprime。残る２以上 N 未満の場合が setwise coprime になる。提出 #73355090 (AC / 560 ms)。たしかに実装内容だけ見れば緑 diff だけど、書き方がひと通りでなく、他のどの書き方をしても Ruby では通らないということで、見た目以上の難易度になっていたと思う。■他の人の提出を見ると、素数列挙は require 'prime' でも良いらしい。pairwise coprime を判定するのに全組み合わせを考えるのではなくセグメント木のようなピラミッドを考えると Bignum を頼ることになりそうだけど log(N) ステップで判定ができて間に合うらしい。なんだ AC をとるのに色々やり方があるじゃないか。お前があほなだけやったか。だって今日初めてある１つの値が 0 から N の範囲のどこに位置しているかによって分類できるという問題の構造に気がついたわけなので、ぼけなのは間違いない。