/ 最近 .rdf 追記 編集 設定 本棚

log[20240720]



20240720() [AtCoder] 今日は AtCoder Beginner Contest 363 があったRuby にとっては C 問題が難しすぎて解けなかったが AC を出している人もいる精進が足りないRuby で通している人が1人でもいるなら自分も通せなければいけないなんなら自分が最初で唯一の AC でありたいE まで解いてから FC を見比べて F の方に見込みがあると思って F に専念していたその見込みは間違っていなかったがTLE を出したあと誤った解法の実装にのめり込んでいる内に時間切れになった実は関数に引数を1つ付け加えるだけで AC になったのだが30 分ちかく時間を残していてそれに気がつけなかったくやちいAPiling Up全パターンの差分を並べてもっともふさわしいものを選んだ短い解答を見てみるとすべての基準値が 100 の倍数だということを利用していたそういう法則がすぐに見抜けないし見抜けるまで問題を読んでもいないBJapanese Cursed Dollトして P 番目なんだけど昇順ソトして前から P 番目ではないそれを間違えていてもサンプル3を試すまでは答えが合うのが怖いCAvoid K Palindrome 2順列全列挙では間に合わなかったどうやるの? C 問題で順列全列挙以外はやる気がないよDPalindromic Numberこれぞ ABCD 問題diff って感じの問題実際の難易度が何色かはまだ知らないけども順番に生成して 10^{18} 番目まで数えることはできないのでまずは桁数を決めて桁数が決まったら先頭の桁から確定していったESinking LandUnionFindす。最大6桁の数字が 100 万個という入力はそれだけでけっこう重い処理正確さを重視して富豪的に書くと ACTLE のボーダーを超える可能性があるので全体を通して最初から書き方を選んでいく……余裕があるといいね! グリドの各マス+海用に1個の頂点を用意して海抜の低い順に自分より低い頂点とのあいだで結合する海のマスを数えたら陸のマスが求まるFPalindromic Expressionやるだけの問題だと思うんですよ解けたはずだと思えばこそ悔しいまず中心に N を置きます。これが最初から条件を満たしているならこれが答えさもなければNL*M*R で置き換えるLR は左右対称でなければならずM に対しては再帰的に同じことを繰り返す。2数の積で N を割っていくのでN10^{12} だからL,R として列挙する数は 10^6 個程度に収まって許されそう終了条件を N<[L,R].min**2 として愚直にやったら TLEったNM に関して結果をメモしたら数は減ったけどまだ TLEったAC になった鍵はA*B*C*D*E という状況で A<=B でなければならないと定めたことこういう方針自体は TLE が出た直後に考えて実装に取りかかってるんだけどなぜか実装の途中で L が回文数でなければいけないという条件が加わっていてその実装に忙殺されてしまっていたなんでだよ自分のすべての提出F 問題日記を読み返す「なんでだよの答えが見つかるんだよなあL*M*RLR に関してLR は左右対称でなければならずと表現しているところに誤りの種がある左右対称なのは L*M*R 全体なのであってLR について書くなら表現を改めてLR は反転して一致しなければならずとする方がよりふさわしいと思う雰囲気で理解して細部がぼんやりだから途中ですりかわるんだよコンテキトが遠ざかったときに左右対称という断片に引っぱられて勘違いをする■精進C 問題Array#permutationN の階乗通りを列挙する代わりに再帰関数で同じ文字を区別しないで列挙するようにしてもまだ TLEった(#55827067)X で読んだ通りに1度しか出現しない文字を統合する前処理を施すことでさらに列挙数を減らすことができて AC になった。提出 #55827317 (AC / 536 Byte / 584 ms)300 点問題にかけていいコトではない同じ時間で DEF を解いたあとで初めてペイするD 問題N=19999のとき正解が99999999(8)だけどコドが出す解が9999999(7)になっちゃうみたいですが通りはしましたと投稿している人がいて試しに自分の AC 提出(#55797000)を実行してみたら 100000001 () になってどちらでもなかった投稿主の提出(#55831310)をコドテトで実行してみたらたしかに書いてある通り7桁の9が出力された正しい答えはなんなんです? RubyAC 提出23個で多数決をとったら正しい答えは 99999999 () らしい入力と出力の見た目には桁数が違っても維持されるパターンが見られるのだけど自分の提出は N=100000 型とか N=999999 型では他と一致していてもN=19999 みたいな型の入力に対してはずれているって N=199N=200 の答えが同じなんだもんサンプルの3を合わせるために ≦ を < に修正してから提出したのだけどたぶん修正すべき場所が間違っていたザルなジッジにお目こぼしされてしまった提出 #55833437 (AC)after_contest はまだないみたいだけど修正版を提出N=19...9N=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ったかなりシンプルに書けたと思う