AtCoder Beginner Contest 460

　Eまで五完。このFは思いつけない。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 460 Eまで。
B abs(r1-r2)<=d<=r1+r2
C 大きい方から貪欲
D とりあえず二回操作を行う。その後、"#"から偶数距離にあるもの。
E yの桁を決めると、k*x+y=x+y(mod M)という形になる。yが消える、l*x=0となるようなN以下のxを数える問題になる。gcd(l,M)を考えると計算できる。

— titia (@titia_til) May 30, 2026

F - Farthest Pair Query

　解説放送を見てAC。

　セグ木と言われても、何を乗せるか分からず、解説放送を二回見て（解説も読んで）ようやく理解。

　分かってしまえば当たり前に思えるが、全く発想になかった。

　「その頂点集合のみを見たときの、直径の端点」を乗せれば良い。

AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）

　Eまで解いたが、Eは分からず、時間をかけて無理矢理嘘解法を通した。レートが1800を割ってしまった。

コンテストへのリンク

コンテスト後のツイート

E N*W頂点のグラフにした後、サイクルの検出方法が分からなかった。WAが三つ出る嘘解法とTLEが三つ出る嘘解法を思い付き、組み合わせたらACはできたが明らかに嘘。
F 二つ連続で使わないことはありえないので、平方分割で解くことを考えていた。

— titia (@titia_til) May 2, 2026

E - Endless Holidays

　結局敗因はよく分からないけど、多分、サイクル検出すれば良い、と言われていたら解けた気がする。dfsしても良いし、SCCを使っても良いし、出次数が正の辺を消していっても良い。

　曜日の概念があったせいで、一般的な有向グラフのサイクル検出問題とは別の問題に見えていたことが敗因だった気がする。曜日1から始める……みたいなところをコードから消せると気付けていなかった。

　自分がどんな問題を考えているのか、もっと一般化した問題はないか、一般化したら問題は解けなくなくなるのか、といったあたりを意識したい。

F - Plan Holidays

　セグ木で解けると知ってAC。

　公式解説では、min-plus 代数などと難しいことを言っているけど、左右の端を使っているか、使っていないか、で4通り場合分けしてセグ木に乗せればOK。

　これも、セグ木で解けると気付かなかったことが敗因。

　多分、クエリが与えられて、[l,r]の範囲での答えを求めよ、と言われていたら解けていた気がする。

　その問題が解けるならこの問題も解ける、と気付くのが大事。

Hello 2025

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

D B=[A[i]+1 for i in range(n)]みたいなのを用意すると、平面走査みたいなので最初の答えは分かる。あとはクエリで差分計算したいのだが上手くいかない。
E1 答え二分探索で毎回BFSするとTLEする。

— titia (@titia_til) January 4, 2025

D. Gifts Order

　けんちょんさんの記事を参考にAC。

　セグ木を使うのは第一候補だったのにこれを思いつかなかったのは良くない。可換性が成り立たないとセグ木が使えそうという判断が鈍ってしまうようだ。気を付けよう。

E2. Another Exercise on Graphs (hard version)

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

　ワーシャルフロイド法で、一辺を変更するときは辺の二乗の計算量でできることは覚えておきたい。

　妙に制約が厳しい気がするけど、クエリ問題だから仕方ないのかな。（と思ったら、公式解説の方法はもっと速いらしい）

G. Secret Message

　証明は難しいが、「十字のマスのうち一マスを塗れば良さそう」というところから発想することは可能だったか。

　ただ、制約が厳しく、二次元配列を一次元に直さないと通らなかったので、コンテスト中にACするのは厳しかったかもしれない。

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 356

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 356 Eまで。F分からず困った。
C bit全探索
D 各桁ごとに
E 頑張ると調和級数の計算量へ帰着できる。
F 平方分割とかを疑っていたが分からず終了。

— titia (@titia_til) June 1, 2024

F - Distance Component Size Query

　解説AC。特にevimaさんの動画を参考にした。

　セグメント木とSortedSetを使い、二分探索で頑張れば解ける。「ある数と右隣の数が繋がっているか？」という配列をもとう、と思えるかがポイントか。

Educational Codeforces Round 146 (Rated for Div. 2)

　Cまで三完。unratedになったものの、普通にDもEも分かっていない。

コンテストへのリンク

E. Chain Chips

　コンテスト中、こういう問題はセグ木だよね……と思ったが何をセグ木に乗せれば良いか分からなかった。が、セグ木を使えばできるというツイートを見て、落ち着いて考えたら分かった。方針はあっていたのに、きちんと詰められないのはダメ。

　ただ、非可換のものをセグ木に乗せる実装が良く分からなくなったのは反省。非可換のときに対応できるライブラリになっていなかったのはまずい。セグ木に非可換のものを乗せたことはあったはずなのだけど、以前はどうやっていたのだろう？

　

Educational Codeforces Round 110 (Rated for Div. 2)

　数分遅刻してDまで四完。今回のえでゅふぉC～Eは教育的な出題だったと思う。Cは尺取り法の、Dはセグ木の、Eはダブリングの、本質的な理解を問うている感じがします。

　普段のえでゅふぉは、educationalという名前の割に教育的とは思えない問題が多い気がするけど、今回は良かった。

コンテストへのリンク

コンテスト後のツイート

C. Unstable String

　尺取り法で良いのだが、左端を動かすときの条件がやや書きにくい。

　dequeを使うと尺取り法を書きやすい、というのを目にしていたのを思い出し、この問題で試してみたのだけど、「左端の条件の書きにくさ」はこの方法では緩和されず、時間がかかってしまった。

　でも、普通に（whileとかで）書くよりはちょっと楽だったかも？

D. Playoff Tournament

　図の通り、セグメント木みたいなことをするのだけど、普段多くの人が書いているセグメント木とは添え字の順番が違うことに注意。

　そこを補正するため、普段の順番と今回の順番で、添え字の対応表を作れば良い。

　私は、対応表を作るときのfor文の範囲を間違えて、対応表に-1を残してしまったためTLEが出てしまった。原因特定に苦労した。

E. Gold Transfer

　コンテスト中は、$C_i>C_{p_i}$を見落としていたのでどうしようもなかったが、この条件をちゃんと理解すれば、一番祖先から貪欲にとっていけば良い。

　なら、ダブリングするのかな、というのは思いつく。

　ということは、金がなくなっていない祖先のノードを見つけて、そこから自分の方へ降りていけば良いのだけど、降りるときどうすれば良いの？　というところで詰まった。

　LayCurseさんのツイートで理解。

　落ち着いて計算量解析をすれば分かりますね。

　なお、実装したけどPyPyだとTLEだったのでKotlinでACしました。ただ、今見ると何人かPyPyで通していますね。

マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）

 　Dまで四完。直後にGCJがあるため、あまり疲れないように取り組もうと思っていた。さらに、問題を開くと、やや眠くて頭が働いていないことが判明。そのため、GCJへのウォーミングアップのつもりでゆっくり問題に向かうことにした。

　そのおかげ（？）か、このコンテストの順位はイマイチだったがGCJ Round2は通過できたので、作戦は成功。

コンテストへのリンク

D - Game in Momotetsu World

　コンテスト中にACできたものの、かなり苦労した。

　「ゴールからDP」という方針自体は結構早い段階で考えたのだけど、どういうDPをすれば良いか分からなくなってしまった。

・$DP[i][j]=(i, j)$からスタートしたときの自分$-$相手の最大値

　とすれば上手くいく。

　こういう「自分は利得を最大化し、相手は利得を最小化する」をミニマックス法というらしい。

E - Xor Distances

　「木DP」「各bitごとに見る」といったキーワードが思い浮かぶが、実際に解くのはなかなか難しい。コンテスト中に大体の方針は立ったつもりでいたが、実際の解法とはややギャップがあった。

　とはいえ、その二つのキーワードを思い付いたら、後は詰めていくだけ、という気もする。木DPの問題はいつも結構時間がかかってしまうのだけど、まあ慣れるしかないのかなぁ。

F - Insertion Sort

　すぬけさんの解説放送を聞いてAC。

　難しい。

・まず、一度も移動させない人たちを決める

　というのが重要だけど、それを思い付くことすらなかなか難しいと思う。

　その後は、

・平面にプロットして平面走査を考える

・DPをセグメント木を用いて高速化（セグメント木を使える形に変形するところも結構難しい）

　という流れ。

　こっちも難しくて、解説放送で方針を理解した後なのに大分実装に苦戦してしまった。

　後半パートは確かに典型なんだけど、この典型をささっと処理するのは容易ではないと思う。

　Codeforcesで何度か解いているはずだけど、毎回そこそこの時間がかかってしまっている。

OUPC β

　Fが解けずの五完でした。writerさんの解説記事まとめはここ。

コンテストへのリンク
コンテスト後のツイート

Product Grid

　KがLCMになるのは分かるけど、その後の計算量削減部分は難しい。

　Kの素因数はすごく多い（かもしれない）けど、各$A_{1, i}$は小さく素因数も少ないことを利用する。コンテスト中よく思いつけたな……。

Increasing Path

　Pathの長さが短い辺から処理していくと良さそうなのはそうで、それを実現するため、（最後に通った辺の長さ, 今までの総距離, 点の番号）を持ってダイクストラしました。

　ただ、今、解説を読んで後で考えるとこの解法は怪しそう。「ある点での最短距離が何度も更新される」「その点からたくさんの辺が出ている」ようなグラフだとTLEになりそう。

　この問題だと、「通る辺の距離が真に大きくならなくてはいけない」ので、そういうグラフでも計算量はある程度抑えられる気がします（ちゃんと考えていないけど）が、広義単調増加でOKだったらこの解法は完全にダメでしたね。

ビブンケイスウ

・二字以上の項は必要ない→セグ木に乗る

　という問題。

　コンテスト後、writerさんはギャグだとツイートしていて、当時自分もそう思ったけど、「こういうのがセグ木に乗る」というところはなかなか本質的ですね。

　二字以上の項が必要ないと分かっても、セグ木に乗せる部分を自力で思いつけたかは疑問です。

AtCoder Beginner Contest 158

　時間ギリギリで全完。

コンテストへのリンク

D - String Formation

一々文字列を反転させていたら時間がかかってしまうので、反転は最後にまとめて行い、文字列追加の際、反転の回数が偶数なら後ろに、奇数なら前に追加する。
　先頭への文字の追加は、Pythonならcollections.dequeを使う。

E - Divisible Substring

　各桁に注目して、たとえば1234という四桁の数字を

4+3*10+2*10^2+1*10^3

　に分けて考える、というのはよくあるテクニック。

　この要領で、1桁目～各桁までの値をPに関する剰余で分類し、それが一致している範囲を求める。

　ただし、P=2や5のときに気を付けなくてはいけないことに注意。これらは10と互いに素でないので、この方法では上手くいかないため、例外処理しなくてはいけない。

　コンテスト中はこれに気付かずWAを出した後、全探索のコードを書いて比較することで気付けた。

　結構気付きにくいようにも思うので、上手くリカバーできて良かった。

F - Removing Robots

　とりあえずソート。

　すると、「そのロボットを起動させたとき、どのロボットまで連動して起動するか」が分かればDPで答えを求められそう、と分かる。

　なので、それをセグメント木を用いて求めていく。

ゆるふわ競プロオンサイト #3 (Div. 1)

　三完＋部分点で終了。
　結構がんばったのだけど、難しい問題は解けず悔しい出来でした。
　しかし、改めて復習すると、解けなかった問題はどれも解けそうになかった気がしてしまった。

コンテストへのリンク

解説スライドはここ

Bananas Multiplier

　LCAは書けますか？　という問題。

Banana Game

　解説AC。

　Grundy数を知っていればやるだけの問題。

　Grundy数についてはふるやんさんのブログが分かりやすいと思う。

　……が、その「やるだけ」のはずのパートが難しくないですか？

　Grundy数を調べるのも、そこから規則性を見つけるのも結構難しい。コンテスト中は、Grundy数の記憶が曖昧だったから飛ばしたけど、飛ばさずやったとしても非常に時間がかかった（もしくは、終わらなかった）気がする。

Sweets Distribution(Hard)

　解説AC。（Python3でACしましたが、同じコードをPyPy3で提出したらTLEでした）

　公式解説も分かりやすいし、検索すれば他にもいくつか解説（私にはアルメリアさんの解説が分かりやすかった）が出てきます。

　こういうものがセグメント木に乗る、ということを初めて見たので驚きました。面白い。

　「二点変更クエリを処理する」と思えば、セグメント木を使うのは不自然ではないですが、とはいえ、似たようなことをやったことないとセグメント木を使うという発想は出にくい気がします。

Yet Another Cake Division

　アルメリアさんの解説やけんちょんさんの解説を見て解説ACはしました。
　（答えの式が書いてあったので、それを書いただけとも）

　最初の一手も、その後の考察も難しい……。

Digit Sum Multiple

　解説ACはしました。

　公式解説を読んだとき、「下k桁が$2^k$の倍数であるような整数」を見つける部分をどうすれば良いか分からなかったのですが、けんちょんさんのブログ記事に構築の仕方が書いてありました。
　いや実際は、公式解説にも帰納法で証明できる旨は書いてあったので、それをちゃんと実行すれば分かったんですよね。