Cまで三完。
No.3551 Regions by Random Points 2
自力AC。
線分と線分が交差する確率が分かれば解けると思ったが、よく分からず。とりあえず、線分で分けられた円周の一方の長さをaとしたときの確率は2*a*(1-a)なので、これを積分してみたらsampleがあったので正解できた。
公式解説通りだが、積分すればこの確率になる、というのがしっくりきていない。
titiaのノート
2026年5月24日日曜日
2026年5月21日木曜日
Educational Codeforces Round 190 (Rated for Div. 2)
Dまで。Eは惜しかった。
コンテスト後のツイート
D (2,2)を使うなら、次の(3,3)まで行くか、それ以前に(3,x)があればダメ。各(a,a)について何回使うことにか係数を足していく。
— titia (@titia_til) May 18, 2026
E 不要なものを取り除くとPの昇順、Cの降順になる。tp,tcにより、どの範囲ならp+cになるとか、tp+d+cになる、とかが分かるので、p、c、p+cについてセグ木を立てる。
E. Minimum Influence
コンテスト中のコードのセグメント木をSparse tableに変更したらAC。
TLEしたときは試さなくてはいけないことの一つだったのに、全く思いつかなかった。反省。
2026年5月20日水曜日
AtCoder Regular Contest++ 220
A一完でさらにレートを落とす。
コンテスト後のツイート
AtCoder Regular Contest++ 220 Aしか解けず。
— titia (@titia_til) May 17, 2026
A 6の倍数xとx/2、x/3を利用すると、35以上は全て作れる。34以下で作れないものについては、約数列挙を利用して全探索&埋め込みした。
Bはグラフの問題になる気がしたが分からず。Cはindexの小さい順に決めるしかないはずだが解けない。
B - Incomplete Shuffle
解説放送を見てAC。
グラフの問題だろうとは思ったが、問題特有の考察は全くできていなかった。あまり考察せず解説を見てしまったけど、まずは、操作をした結果どのようなものが現れるか？ を実験してから考えていく感じですね。
C - Range Increment
解説放送を参考にAC。
解説放送を見ても（他の解説を読んでも）なかなか理解できず、一時間くらいじっと考えたらようやく分かった。
解説放送に出てくるmod=3で1 0 1のケースより、（実質的には同じだけど）mod=6で1 5 1のケースを考えた方が自分には理解しやすかった。
解法自体は、左から決めていくしかなくて、単純な貪欲で上手くいかないのなら、heapqか何かを使うかも……と想像することはできるかもしれない。しかし、こういう風な推察から正しい解法に至るのは結構厳しそうなので、じっくり問題の性質を見極めるしかなさそう。
2026年5月18日月曜日
SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）
Eまで。またレート1800を割る。
コンテスト後のツイート
SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458） Eまで。Fの12WAが取れない。何故！？
— titia (@titia_til) May 16, 2026
C Cの文字からmin(最初への距離,最後への距離)
D SortedMultiset
E 1313……が何回続くかで考える。
F Trie木のnodeを使って行列累乗。Aho-Corasick法で遷移行列を見つける。で良いと思ったがWA
F - Critical Misread
コンテスト中の方針で大まかなものはあっていたが、どこでWAになるか分からず、ランダムテストでACしている提出と比較した。
ミスは次のようなものだった。
たとえば、"bcb"と"c"がある場合に、"bcb"が出たらそもそもいけないのだが、"bc"や"bcb"もノードとして数えてしまっていた。
そのようなものを削る前処理を行ったらAC。
Aho-Corasick法を使う場合に、必要になることが多い前処理という気がするが、知らなかった。
そして、AIに聞いたところ、Failure_pathを利用して"c"に印がついているなら、"bc"にも印がつくようにする、という構築を行うのが一般的らしい。勉強になった。
2026年5月14日木曜日
Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）
F以外の六完で久しぶりの黄パフォ。Gは公式解法と違うので嘘解法疑惑があるけれど、多分大丈夫？→とりあえず、ランダムテストではHack caseは発見できませんでした。
コンテスト後のツイート
E [S:?]と[?:T]で詰める場合と、[S:T]と[S,T]に入る何かで詰める場合二通り考える。前者は開始位置、終わり位置を持って調べる。後者はセグ木を使った。
— titia (@titia_til) May 9, 2026
G 座標が小さい順に詰めていく。SortedSetで管理すれば、どのロボに入れられるかを二分探索できる。
F - Second Gap
解説AC。
コンテスト中、maxとsecondのindexを持てばDPできるのでは？ みたいなことは考えたのだが、上手く分からず実験をはじめて考察をやめてしまった。
実験自体は悪くないのだけど、ちゃんと考察しないといけない。
実際は、maxのindexだけ持ってDP（挿入DPみたいなやつ）できる。maxとsecondを持つDPが書ければ、そこに気付くのは難しくないはず。
Gが解けたから助かったものの、こちらも解けなくてはいけない問題でした。
2026年5月11日月曜日
AtCoder Regular Contest-- 219
Cまで三完だが、Aは嘘だった。DもEも思いつきにくい部分は思いついていたのだが。
コンテスト後のツイート
C 右端のエレベーターを使わない場合と使う場合とで場合分け。使う場合、その行を突っ切らない場合の最短コストを求めて大きい順にソート。二つまとめてW-1にできる。
— titia (@titia_til) May 10, 2026
D 実験したが分からず。
E 外周から順に構築していったが失敗。（WA6個）
A - Similarity
文字列Xの01を反転させたものをX'とすると、S中にX'が含まれないなら、Xを答えとして良い。
ACした提出は、Sの文字を全探索してそれを調べたが、Sの要素が全て対になっているとき、これではダメ。乱択などしなくてはいけなかった。WAが出たら気付いてACはできていたと思う。
D - Grid Game
解法ツイートを見てAC。
コンテスト中、（一次元での）実験により、
・(i+j)%2==1の箇所しか影響しない
ことには気付いていた。
また、（K+1）での余りを考えて良いことも分かっていた。
しかし、判定条件が分からず、交代和などを考えて迷走。分からなくなってEへ行った。
実際は、NIMと同じなのでxorを取ると良かった。
NIMに近いのでは？ と考えたことはあったはずなのに、なぜ試してみなかったのか。悔やまれる。
E - Equal Distribution
解法ツイートを見てAC。
★「oが偶数個とxが偶数個で作られた配列があったとき、その連続部分区間でoとxをちょうど半分ずつ含むものが存在する」
を使うことはコンテスト中に気付いていたのに、全体のハミルトン閉路を取ることを思いつかなかったという。
外周から距離０、1、２の順に、oがちょうど半分か、一個少ないか、みたいなものを取って構成しようとしていた。
この方法でもできなくはない気がするけど、外周ではAが右半分に、次ではAが左半分に……みたいなときに連結性が保たれない。連結性を保つような取り方はあるはずだけど、若干実装の手間が増えるし、コンテスト中はそもそも反例に気付いていなかった。
★が本質だと思うのに、★に気付いても違う方針へ行ってしまったのは痛い。
一番の鍵となる部分は思いついて実装していたため反省点も見出しにくく、冷静にならないと……くらいしか言えないのも辛いところ。
2026年5月9日土曜日
yukicoder 499 contest
Fを考えていたが分からず、Dのみ一完。
No.3537 Thank You!
解説AC。
どのカードを1にするか決めたら貪欲で良い……というのはコンテスト中から分かっていたが、それは簡単に求められないと思って迷走してしまった。（安い方からあるところまで貪欲に買った後、それ以降で個数が一番多いものを1にする、とすれば良いと思ったが嘘でした）
二分探索を使えば、実装はやや難しいが普通に計算できた。これは気付かなくてはいけなかった。
登録:
投稿 (Atom)