脳log[20230114]

2023年01月14日 (土) [AtCoder] 精進。今日あった ARC153-C「± Increasing Sequence」(青 diff)。コンテスト中は場合分けをして簡単なケースから答えを作っていた。たとえば、N=1 なら答えは 0 しかない。A 数列が 1 のみまたは -1 のみだった場合は、１個だけ符号を反転させて項数 N-1 の等差級数と打ち消し合わせればいい。幸い N の２乗より大きい値を使うことが許されている。他には 1 の列と -1 の列が混じり合わず隣り合っているケースの答えなどを作った。そんな具合に特殊ケースを捌いていって、最後に残ったのがサンプル１のケース。つまり、２個以上の 1 と -1 が混じり合ったごく一般的なケース。ここで手が止まって時間を迎えてしまった。■提出 #38021545 (AC / 673 Byte / 194 ms)。最後に残ったケースを考えた結果、そのケースの解法がその他の場合をすべてカバーしてしまっていた。なんじゃそら。考える前に書き始めるからこういうことになる。いみじくも１番目に示されていたサンプルを１番に考えるべきだったのだ。解法はこう。いったん A 数列に 0,1,2,...,N-1 の重みを割り当てて合計を計算する。合計が０ならそのままそれが答え。合計が正なら、重みの後半を後ろにずらしたり、前半を前にずらしたりしてバランスを取る。そのためには A 数列の後半部の累積和が負だったり前半部の累積和が正だったりしなければいけない。合計が負の場合も同様に。■(80 分も残していたのだから)時間内に解けたはずだよ。くやちい。■書ける対象が少ないんだから A と B についても書く。A 問題「AABCDDEFE」(灰 diff)。とりあえずメモに書き出してみた。11、22、33、...、99。そして３桁目からは数字を使うと紛らわしいので 11abccded という感じ。じゃあ 0 を除くという例外規定はあるけども１桁目もアルファベットを使って aabcddefe と表せるな。スクリプトの１行目にコメントとして書き込んでそれを見ながら考えよう。提出 #38005488 (AC / 174 Byte / 64 ms)。提出して WJ のときに問題名が目に入った。最後にタイトルに回帰する見事な伏線回収では。それかお前の目が節穴か。末尾が EFE であることに何か罠があるかと疑ったけど何もなく。灰 diff でした。Ruby で２番目に早く提出されたこちら #38003727 があざやか。自分はこうしたら１桁目が求まるな、次にこうしたら２桁目が求まるなという手探りの手続きを書いて提出したけど、この提出は完全に見切ってから書かれている、しかも時間をかけずに。正直なところ 99999 を足すとどうなるのか自分はわかっていない。■B 問題「Grid Rotations」(水 diff)。慎重に問題文を読んでからサンプルの図解と照らし合わせて誤読がないように努めた。ありがたい図解を眺めていれば、１度の操作で abcde 行がどのように並べ変わるかわかるし、２度の操作でも並び順が入り乱れることがないことが確認できる。行と列の並べ替えが独立していることも容易に推測できる。提出 #38009253 (AC / 378 Byte / 711 ms)。緊張してるのかしらないけど、括弧の対応を間違えたり + を * とタイプミスしたり、まあまあサンプルを合わせるのに苦労した。添字配列を作って Array#values_at を呼び出すのは効率が悪いみたいで、他の人の提出よりいくらか余分に時間がかかっている。Array#rotate を完全に失念していた。