脳log[20231007]

2023年10月07日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)があった。結果は見てない。自分のすべての提出。ABCD の４完。E 問題で撃沈。終了後に読んだ F 問題が簡単であまりに残念。崖であってほしかった。ではふりかえり。■A 問題「Weak Beats」。２進数として解釈して特定の値と比較すればいいかと考えてみたけど、偶数桁だけを見ろと言っているのでしかたなく愚直に書いた。■B 問題「Round-Robin Tournament」。添字を含めたペアでソートする。既定では昇順にソートされるので勝利数のマイナスを比較のキーにしてもいいけど、敗北数を数えるとひと手間がなくていい。■C 問題「World Tour Finals」。この前あった World Tour Finals 2022 にちなんだ問題。制約は小さいし愚直にやるだけなんだけど、意外に難しかった。何がって、すでにトップの人の扱いが。でもボーナス点が最低得点未満だということで、総合得点はそれぞれのプレイヤーに固有のユニークな値になる。何も難しいことはなかった、けど 18 分かけた。■D 問題「Merge Slimes」。サイズが倍々で、数は半分半分。貪欲に可能な限り合成を繰り返すことでスライムの数は最小になる。それを効率的に数えられますかという問題。数が半分半分になっていくから操作回数は対数のオーダーになる。愚直に操作をシミュレートして良さそう。操作した結果が既存のサイズのスライムになることがあるから、操作はサイズの昇順に行いたい。プライオリティキューを使いますか？ 「キューを２本持つことでプライオリティキューを使わないでもソート済みの状態を保ちながらキューを伸ばせる場合があるというのは、AtCoder について書いた２番目の日記に書いてある」のでそのように。■E 問題「Playlist」。期待値。サンプルの１を頼りに愚直解は求まった。曲を３曲再生するパターンが N^3 通りで、そのうち X+0.5 秒後に曲１が再生されているのは 1+3+3 通り。だけど O(XXN) は通りませんよ。■F 問題「Push and Carry」。非常に拍子抜けする問題。倉庫番。ただし壁はなし障害もなし。位置関係を整理してささっと数えるだけ。最初の提出は変数名の１文字タイポで WA×2 だったけど、３分で修正できた。F 問題が崖でないと救われないなあ。E 問題がうらめしい。でも Ruby の提出を見ると F 問題を解いてる人は E 問題も解いてるみたいなので、E 問題を解けないのが悪いのだな。E と F を両方とも解けてないのが悪い。■■■翌朝。E 問題。最初に考えた解法は O(XN) で間に合う感じだった。でもサンプルの１で 1+1+1 通りは数えられても 1+3+3 が数えられなかった。どうやって ×N するか考える過程で O(XXN) になって TLE が避けられなくなった。ところでね、スタート地点を N^X にして遷移１回につき ÷N のペナルティを払うというのはどうか。あとで答えが合うかたしかめる。■D 問題。みなさんプライオリティキューなど使わずに答えを出している(使うと log が２乗で TLE になるというのはある)。その中でも提出が早めで一番実行時間が短いもの(tinsep19 さんの)を雰囲気だけ読んだけど、その解釈らしきものに翌日になって思い至った。考えなくても湧いてくるなんてお得だ。スライムのサイズの trailing zeroes を処理することで途中で合流するスライムを予め１つにまとめられるのではないか。操作の巻き戻し。操作回数は答えの一部ではないから巻き戻しはタダで行える。あとはソートもいらず初期サイズごとにカウントするだけ。これもあとで答えが合うかたしかめる。■E 問題。どの日記を読んでも特別どうということなく答えを出している様子。最初の O(XN) 解法で分母が１つだと考えたのが間違いだったのかも。つまり、サンプルの１で 1+1+1 通りを数えたと書いたけど、それは (1+1+1)/(何か) ではなくて、1/27+1/9+1/9 だったのではないか。これを解法２としてあとでたしかめよう。以前も書いたけど、確率・期待値の問題って、こうすれば答えが出るという筋道がさっぱり読めないところが弱い。あれこれやってみて正解を導き出す解法にぶつかるのを待っている。当てもんをしている。初心にかえれというのは簡単だよ。全通りを並べてみて、そのうちのいくつが該当するかを数える。その割合。実に簡単。■順番に３つ。□提出 #46376658 (AC / 273 Byte / 393 ms)。F 問題。最初に N^X 通りを計上しておいて、遷移ごとに ÷N のペナルティを払う。□提出 #46376189 (AC / 156 Byte / 193 ms)。D 問題。最初に逆操作をしてスライムをグループごとに統合してから個数の１のビットを数えて合計する。□提出 #46376313 (AC / 233 Byte / 465 ms)。E 問題。ふつーの期待値 DP だった。1/N の可能性を足し上げていく。X を超える遷移については曲１の場合だけ記録するようにして、その他の曲に関しては X 未満までしか遷移させなかった。そうすると DP 配列の X を超える部分に答えが入っている。いやー、これが解けないならどんな期待値の問題も解けないよ。イチからやり直した方がいいよ。早め６完の問題セットだったよ(だが４完)。■■■いま気がついたんだけど、E 問題は期待値の問題ではないよね。確率を問われている。何回期待値と書いただろう。気がつかなかった。一応概念は知っているつもり。リスクに相当するものだよね。(脅威の大きさ)×(発生確率)。(賞金額)×(当選確率)。でも確率と期待値を区別せずに問題を解いているってありえることなの？ しかも解けてなかったし。