titiaのノート

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。

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

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

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

2026年5月28日木曜日

Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2)

　Dまで四完。E解きたかったね。

コンテストへのリンク

コンテスト後のツイート

C2 index iについて、j<iなるA[j]はプラス、A[i]はマイナス、j>iはそのまま、としたときの最大値
D 答えで二分探索。混乱したけど、答えより小さいものを、答え以上のものより少なくしたい。
E 二乗なら解けるけど高速化できない。遷移先が区間になったりしないか、とかもらうDPなら、とか考えていた。
— titia (@titia_til) May 23, 2026

E. Deconstruction Tree

　解法ツイートなど参照してAC。

　コンテスト中に配るDPでのDPは書けていて、それをどう高速化するのかが分からなかった。ツイートで書いたことがあっていて、もらうDPにするともらう先が区間になり高速化可能だった。なんで正しいことを考察しているのに、答えに至れないのか……。

　ただ、その上で、答えが何か？　というところでもう一考察必要だった。頂点Nに対して、DPがどこから遷移するか？　というのをちゃんと考えなければならない。それが上手くいかず、結局コンテスト中に書いたDPとランダムテストでチェックしてACした。

　惜しくなかったわけではないんだけど、実際にACするには遠かった気もする。

F. Load Unbalancing

　解説AC。

・一番大きい数を最後に加えるとして良い

・他のものたちについて、k個に詰めたときのminを最大化したい。

・これは答えを二分探索し、bit DPすれば良い。なぜなら、minの最大化の場合、できるだけ平均的に詰めれば良いので、問題文で指定されたような詰め方を考えなくて良いから。上手く詰める方法があれば、問題文で指定した方法で詰められるので、（二分探索の）mid以上のものが何個あり、最後の箱に何個入っているか？　だけ見ればOK。

　言われてみれば理解できるし、制約にbit DPを使う（だろう）というヒントもある。

2026年5月26日火曜日

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）

　Eまで。

コンテストへのリンク

コンテスト後のツイート

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459） Eまで。F分からず。
B 良い書き方を思いつかず。辞書に26個入れた。
C SortedSetを使った。PyPyだとTLEしたのでcodonでAC。
D 奇数番目→偶数番目に、多いものから順に並べる。
E 木DP。二項係数に注意。
— titia (@titia_til) May 23, 2026

F - -1, +1

　解説放送を見てAC。

　操作を、「ブロックを右にずらす」というイメージで捉えられると考察が進みやすい問題だった模様。コンテスト中は差分をとって考えている時間が長かったけど、それほど筋が良さそうではなかったのだから、元の問題に戻って絵を描くべきだった。

Codeforces Round 1099 (Div. 2)

　ACの二完で過去最悪順位。青に落ちて呆然自失。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1099 (Div. 2) AC二完。過去最悪の順位なんですが。
A 1 3 5 7...
B 分からず。
C min(A)<=2のときは、1や2への回数の小さい方。そうでないときは、どこで合流させれば良いか定まる。
D dfsで決定できる値を決定した後、nの小さい方から適当に決めて良いと思ったがWA。
— titia (@titia_til) May 21, 2026

B. Another Sorting Problem

　破滅した原因の問題。

　（多少解説を見たけど理解できなかったので）大体自力でAC。

　まず、i<jでA[i]>A[j]なら、iには足さず、jには足さない、しかあり得ないと気付かなくてはいけない。

　ここで、足すものと足さないものを分けて考える。

　足す方、足さない方それぞれは広義単調増加でないと条件を満たさない。

　index iが足す方だとしたとき、それ以降のことを考えると足す値はできるだけ小さい方が良い。それは、それ以前のmax-自分の値である。

　この最大値をkとして良い。

　kが決まれば、具体的に、A[i-1]>A[i]であるようなiについて、A[i]+=kする、というのを左からしていき、それで広義単調増加になるかチェックすれば良い。

　コンテスト中は、kを決めてからもう一回……というようなやり方が見えず、for文一回でどうにかなる気がして嵌ってしまった。

　ただ、解法自体は簡単だが、正当性の証明とか、直感的に理解するのは結構難しい気もする。

D. Maximum Prefix Sums

　自力AC。

　解法はあっていた。十分性をチェックしたらACできた。

　dfsするとき十分性をチェックしていたつもりだったが、漏れていたのね。

2026年5月24日日曜日

yukicoder contest 500

　Cまで三完。

コンテストへのリンク

No.3550 Another Rurumaru Function Problem

　自力AC。

　上のbitから順に見ていけばOK。これはすんなり解けた。

No.3551 Regions by Random Points 2

　自力AC。

　線分と線分が交差する確率が分かれば解けると思ったが、よく分からず。とりあえず、線分で分けられた円周の一方の長さをaとしたときの確率は2*a*(1-a)なので、これを積分してみたらsampleがあったので正解できた。

　公式解説通りだが、積分すればこの確率になる、というのがしっくりきていない。

　→二つの線分が交差するか？　というのは、線分の操作順によらないと気付いて納得した。

No.3552 Triangular Coloring

　自力AC。

　互いに辺で繋がっている三点が見つかれば、後はdfsして探していけば良い。

　その三点は、一点と、そこに隣接する点を選び、残り一点を全探索して見つけた（辺をsetで持って探索した）。

No.3553 Good Quartet

　自力AC。

　実験すると、良い集合が実質四通りしかないことが分かるので、あとは実装を頑張る。

登録: 投稿 (Atom)