脳log[20240720]

2024年07月20日 (土) [AtCoder] 今日は AtCoder Beginner Contest 363 があった。Ruby にとっては C 問題が難しすぎて解けなかったが AC を出している人もいる。精進が足りない。Ruby で通している人が１人でもいるなら自分も通せなければいけない。なんなら自分が最初で唯一の AC でありたい。E まで解いてから F と C を見比べて F の方に見込みがあると思って F に専念していた。その見込みは間違っていなかったが、TLE を出したあと誤った解法の実装にのめり込んでいる内に時間切れになった。実は関数に引数を１つ付け加えるだけで AC になったのだが、30 分ちかく時間を残していてそれに気がつけなかった。くやちい。■A 問題「Piling Up」。全パターンの差分を並べてもっともふさわしいものを選んだ。短い解答を見てみると、すべての基準値が 100 の倍数だということを利用していた。そういう法則がすぐに見抜けないし、見抜けるまで問題を読んでもいない。■B 問題「Japanese Cursed Doll」。ソートして P 番目なんだけど、昇順ソートして前から P 番目ではない。それを間違えていてもサンプル３を試すまでは答えが合うのが怖い。■C 問題「Avoid K Palindrome 2」。順列全列挙では間に合わなかった。どうやるの？ C 問題で順列全列挙以外はやる気がないよ。■D 問題「Palindromic Number」。これぞ ABC の D 問題、緑 diff って感じの問題。実際の難易度が何色かはまだ知らないけども。順番に生成して 10^{18} 番目まで数えることはできないので、まずは桁数を決めて、桁数が決まったら先頭の桁から確定していった。■E 問題「Sinking Land」。UnionFind です。最大６桁の数字が 100 万個という入力はそれだけでけっこう重い処理。正確さを重視して富豪的に書くと AC と TLE のボーダーを超える可能性があるので、全体を通して最初から書き方を選んでいく……余裕があるといいね！ グリッドの各マス＋海用に１個の頂点を用意して、海抜の低い順に、自分より低い頂点とのあいだで結合する。海のマスを数えたら陸のマスが求まる。■F 問題「Palindromic Expression」。やるだけの問題だと思うんですよ。解けたはずだと思えばこそ悔しい。まず中心に N を置きます。これが最初から条件を満たしているならこれが答え。さもなければ、N を L*M*R で置き換える。L と R は左右対称でなければならず、M に対しては再帰的に同じことを繰り返す。２数の積で N を割っていくので、N≦10^{12} だから、L,R として列挙する数は 10^6 個程度に収まって許されそう。終了条件を N<[L,R].min**2 として愚直にやったら TLE だった。N や M に関して結果をメモしたら数は減ったけどまだ TLE だった。AC になった鍵は、A*B*C*D*E という状況で A<=B でなければならないと定めたこと。こういう方針自体は TLE が出た直後に考えて実装に取りかかってるんだけど、なぜか実装の途中で L が回文数でなければいけないという条件が加わっていて、その実装に忙殺されてしまっていた。なんでだよー。■自分のすべての提出。■F 問題。日記を読み返すと「なんでだよー」の答えが見つかるんだよなあ。L*M*R の L と R に関して、「L と R は左右対称でなければならず」と表現しているところに誤りの種がある。左右対称なのは L*M*R 全体なのであって、L と R について書くなら表現を改めて、「L と R は反転して一致しなければならず」とする方がよりふさわしいと思う。雰囲気で理解して細部がぼんやりだから途中ですりかわるんだよ。コンテキストが遠ざかったときに左右対称という断片に引っぱられて勘違いをする。■精進。C 問題。Array#permutation で N の階乗通りを列挙する代わりに、再帰関数で同じ文字を区別しないで列挙するようにしてもまだ TLE だった(#55827067)。X で読んだ通りに、１度しか出現しない文字を統合する前処理を施すことでさらに列挙数を減らすことができて AC になった。提出 #55827317 (AC / 536 Byte / 584 ms)。300 点問題にかけていいコストではない。同じ時間で D と E と F を解いたあとで初めてペイする。■■■D 問題。「N=19999のとき、正解が99999999(8桁)だけどコードが出す解が9999999(7桁)になっちゃうみたいですが通りはしました」と投稿している人がいて、試しに自分の AC 提出(#55797000)を実行してみたら 100000001 (９桁) になって、どちらでもなかった。投稿主の提出(#55831310)をコードテストで実行してみたら、たしかに書いてある通り７桁の９が出力された。正しい答えはなんなんです？ Ruby の AC 提出２、３個で多数決をとったら、正しい答えは 99999999 (８桁) らしい。入力と出力の見た目には桁数が違っても維持されるパターンが見られるのだけど、自分の提出は N=100000 型とか N=999999 型では他と一致していても、N=19999 みたいな型の入力に対してはずれている。だって N=199 と N=200 の答えが同じなんだもん。サンプルの３を合わせるために ≦ を < に修正してから提出したのだけど、たぶん修正すべき場所が間違っていた。ザルなジャッジにお目こぼしされてしまったか。提出 #55833437 (AC)。after_contest はまだないみたいだけど修正版を提出。N=19...9 と N=20...0 っていうのは、出力の桁数が変化するという点でのコーナーケースみたい。テストケースにコーナーケースがなかったんだね。■E 問題。別解。提出 #55860799 (AC / 523 Byte / 707 ms)。UnionFind 解が #55800705 (AC / 524 Byte / 1629 ms) だったので、長さはほぼ同じなものの、時間は倍以上早くなった。別解は BFS。プライオリティキューすら必要ではなかった。■精進。「砂の城 (Sandcastle)」。E 問題と似た問題だと名前が挙がっていたので。提出 #55862476 (AC / 354 Byte / 578 ms)。たしかに、これも BFS だった。かなりシンプルに書けたと思う。