日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

F costが小さい方から見る。[L,R,C]が来たら、その後は、Lの後Rまで飛ばして良い。RIGHT[x]を管理し、RIGHT[L]=max(RIGHT[L],R)と更新していく。
G ダイクストラで全頂点から全頂点への最短距離を求めて色々するかと思ったが、全然違ったらしい。

— titia (@titia_til) July 27, 2024

G - Last Major City

　解説AC。（解説放送も見た）

　最小シュタイナー木を履修した。分かってしまえば難しくない。Kが高々10というところから3^NのDPと気付ければ自力で思いつくことも可能だったか？

Educational Codeforces Round 168 (Rated for Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

E どのindexでレベルアップするかをkごとに記録。SortedSetを使ったらTLEしてしまったけれど、SortedSetを使ってACしている人もいるようなので、実装が下手。まあ、調和級数のlogとSortedSetのルートがつくので計算量的にも結構厳しそうではあるんだよね。

— titia (@titia_til) July 30, 2024

E. Level Up

　SortedSetをセグ木上の二分探索に直してAC。

　自分のセグ木二分探索のライブラリの書き方が変だったので、修正に時間を要したけど、どう書くのが良いのだろう？

　とりあえず、セグ木の演算が足し算で、

・sum(0, index)がある値以上になる最初のindexを返す

　というセグ木二分探索は実装した。

　一般的には何を二分探索で求めるようにすれば良いんだろう？

　

AtCoder Beginner Contest 322

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 322 Eまで。Fの方針は分かっても実装が間に合わない。
C 尺取り。
D 実装がんばる。
E DP。Pを5で固定で解いてしまい2ペナ。
F 左側の連続個数, 右側の連続個数,連続する0の最大長さ,連続する1の最大長さを持てば遅延セグ木/平方分割でいけるとは思ったが実装終わらず。

— titia (@titia_til) September 30, 2023

F - Vacation Query

　コンテスト後、Pythonで遅延セグ木を使った実装だとTLEになる……という話を聞いて避けていたのをようやく実装。

　普通に遅延セグ木で通りました。（ただし、二重配列にしないという工夫はしている）

　なお、ツイートで書いている解法だと、遅延セグ木に乗せるものが足りていないですね（多分、実際に実装したら気付いたでしょう）。

　演算が多要素×多要素の場合も簡単に書けるように、遅延セグ木をライブラリ化しておくべきですね。

Codeforces Round 962 (Div. 3)

　全完。

コンテストへのリンク

コンテスト後のツイート

（Eの続き）右からのindexの累積和を持っておいて、左から足していく。
F いくつの数字以上を使うかを二分探索→等差数列の和で計算し、余った個数を引く。
G https://t.co/JMooQptkIG　これ知らないと難しいと思うんだけど、結構解かれているね。

— titia (@titia_til) July 26, 2024

yukicoder contest 438

　A、Cの二完。Aが難しくて困ったけど、解けて良かった。（それと比べるとCは簡単だった）

コンテストへのリンク

No.2820 Non-Preferred IUPAC Nomenclature

　色々参考にしてAC。

　どうやって解を構成するかは分かったのだけど、木DPとかマージテクとか考えてひどいことに。

　行きがけ、帰りがけを考えればDFSで構成することができた。やっぱりDFS系は苦手なのかなぁ。

　

Codeforces Round 961 (Div. 2)

　B2もDも解けず。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 961 (Div. 2) B2が分からず、D高速化できず。
A [n,n-1,n-1,...,2,2,1,1]の累積和。
B1 xとx+1を使う合計回数を全探索
B2 回数はm/xの周囲だけで良さそう→WA
C 前回の操作回数が30回を超えていたら、前回-30回は少なくとも行う、としたら通ったが誤差とか自信ない（logで処理）。

— titia (@titia_til) July 23, 2024

B2. Bouquet (Hard Version)

　こたつがめさんの放送の振り返りを見てAC。

　x,x+1が使う候補のとき、

・xをできるだけ使う　→　x+1をできるだけ使う　→　xのものをx+1に変換する

　で良いのではないか、というのはコンテスト中にも考えていた。（それで本当に良いのかは分かっていなかったが）

　ただ、ツイートの方法で良いと思ったため方針転換できなかった。

　x,x+1を使う個数の和をm/x個とすると、その個数がxの個数より大きかったとき、最低でも、求める数より大きくなってしまう。それでダメだった。

　（簡単に反例が見つかるかと思ったが、そう簡単でもなかった。ランダムテスト書くしかなかったか）

ユニークビジョンプログラミングコンテスト2024 夏（AtCoder Beginner Contest 359）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

ユニークビジョンプログラミングコンテスト2024 夏（AtCoder Beginner Contest 359） Fまで。
C 斜めに移動してから横に移動
D bit DPなのはすぐ分かったが実装に苦戦。
E stackを使って、単調減少な板を残しておく。
F heapqを二個用意して受け渡す。

— titia (@titia_til) June 22, 2024

G - Sum of Tree Distance

　解説AC。

　マージテクで解けると聞き、マージテクで通そうと思った後も自力で解けなかったのは情けない。「ある頂点から根の方向へ何歩進んだか？　の総和」を持たなければいけない気がし、それだと一歩一歩全ての色について更新しなくてはいけないと思ってしまった。

　が、根からの距離の総和さえ持てば代用できるため、マージテクが適用できる。