脳log[20250531]

2025年05月31日 (土) [AtCoder] 今日は AtCoder Beginner Contest 408 があった。D 問題に全部持って行かれた。全部ではないな。E と F の点数 950 点と D の点数 400 点を持って行かれた。難易度が F<E<D の順で逆転していた。■A 問題 Timeout。今日は A 問題から不調を感じていた。+0.5 秒がまじで嫌い。長老が寝る瞬間に長老は起きているのか寝ているのかという問題が生じないためであるのはわかる。目的はわかるけどそれを処理する頭がない。だから嫌い。今日はごちゃごちゃ細かいことが考えられない。■B 問題 Compression。uniq、sort. ■C 問題 Not All Covered。端から順に見ていってそこをカバーしている砲台の数を数える。■E 問題 Minimum OR Path。単純パスというのは考えなくてもいい。寄り道をして得をすることがないので。ラベルのビットには明確な序列がある。1<<k を含むラベルを使わないで済むなら、1<<k 未満のラベルはすべて使ってしまって構わない。この論法で最上位ビットから決めていく。UnionFind で 1 と N の連結非連結を確かめながら。TLE を１回出した。マスクしたウェイトに基づいて辺をソートしてから UnionFind をしたのが原因。ソートがいけない。ソートするより一辺一辺使用するかしないかを判断する線形時間の処理の方が軽い。■F 問題 Athletic。セグメント木が使えますかという問題。高橋君のいる高さは狭義単調減少なので、高さの低い方からあと何回ジャンプできるかを求めてセグメント木に乗せていく。高さが近すぎるとジャンプできないので、求めた回数をすぐにはセグメント木にセットせず、キューに入れて遅延させる。それだけ。■D 問題 Flip to Gather。ある１の島を、残す１の左端にすると決める。そうするとそこより左にある１の数だけ操作が必要。同じことを右側についても求める。左端と右端を決めたら左右の消すべき１の数と真ん中の消すべき０の数がわかる。２乗の解法は許されないからどうする。尺取り？ あのですね、人間のワーキングメモリには個人差があって、自分は頭が働くときでも３段４段の処理は脳内スタックからあふれてしまう。DP をするときだって in-place で書き換えたり保持するものを前後の２系列に限ったりすることで添え字が３つ以上にならないように工夫している。というかそうする方が楽だし解きやすいので自然そうなる。1+1+1+1 = 4 ではないんです。３までは線形に増えていってもその次はスタックオーバーフローで実行が完了しないんです。こういう限界の低さをふまえて出題してもらいたい。D 問題に解けない問題を置かないでほしい。■■■A 問題。嫌いな嫌いな +0.5 秒問題。自分について理解した。たとえば問題文が「最後に肩を叩かれてから S 秒後まで長老は起きています。(最後に肩を叩かれてから) S+1 秒後には寝ています」だったらすんなり頭に入ってくる。次からこう読めばいいと理解した。S と S+1 という２つのパラメータを S というひとつの値で表すために +0.5 秒というやっかいものを導入して、「あとはわかるな」で済ませるから話がややこしくなるのだ。きっちり文章にしてくれないとわかりません。