デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）

　Eまで五完でレートをまた下げる。

コンテストへのリンク

コンテスト後のツイート

デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）Eまで。FもGも分からず。
B 愚直でOK
C シミュレーション
D 左右から更新
E ここに行けばその上全てを壊せる、というブロックがある。そこへたどりついたら、その上全てに行けるとして良い。

— titia (@titia_til) January 31, 2026

F - Non-Increasing Number

　解法ツイートを見たら当たり前に感じたが、実際にACするのは結構大変だった。

　最後に使った数字がxで、Nで割った余りがyのとき……というDPを考えるしかなさそう。

　この(x, y)が被ってはダメ、という状況になれば状態数を抑えられる。そのためには、上の桁につけていくのではなく、下の桁に数字を付け足していけば良い！（桁DPで下の桁に足していくような発想ですね）

　あとはDPの復元をすればOK。

　なのだが、最小性を言うため、どの数字を使うか、という順番も大事。

　普通にやればこの順番を満たすのだが、ソートしたりしてしまいハマった。

　一桁のときは、

・[(1, 1), (2, 2), (3, 3), (4, 4),...]

　となっており、これが一番上の桁なのだがから、

　左から順番に、かつ次に使う数字が小さい順に探索していけばOK。

yukicoder contest 319

　ABの二完。難しくないですか？

コンテストへのリンク

No.1715 Dinner 2

　解説AC。

　連続して同じ料理を食べてはいけないということから、二回の食事をまとめて行うことばかり考えてしまい、

・DP[j]＝最後にjの料理を食べたときの元気の最大値

　という簡単なDPの立式を考えられなかった。

　NとDが10^3以下という制約を見ても、自然なDPの立て方。これを思い付けないのはまずい。

No.1717 Levi-Civita Triangle

　一応自力AC。

　1と2が隣り合う状態は作れないと気付き、大抵の場合は0になるんじゃないか？　と思ったがそれだけではダメ。

　実験すると、1になるパターン、2になるパターンは3種類ずつしかないと気付いてAC。

　初手から実験すべき問題でした。

JPRSプログラミングコンテスト2026#1（AtCoder Beginner Contest 442）

　Fまで六完。Eで偏角ソートに苦戦。自分で実装したが遅かったためレートを落とす。

コンテストへのリンク

コンテスト後のツイート

あ、Fセグ木DPって書いたけどセグ木使ってない。
最初セグ木でやろうとしていたけど、実装途中で累積minで良いことに気付いてそっちで書いたんだった。

— titia (@titia_til) January 24, 2026

G - Lightweight Knapsack

　解説AC。

　6でまとめるというヒントは見たのだが、ピンと来ず、解説を見てAC。

　何個か取った後、貪欲に帰着するというのはなるほどです。

　条件反射で、「ナップザックならばDP」と考えていたので、自力でこの解法に至るのは厳しかったと思う。

Codeforces Round 1075 (Div. 2)

　C1まで三完。C2もD1も難しい……。

コンテストへのリンク

C2. XOR-convenience (Hard Version)

　分からず解説を見てAC。

　2ベキだと解が存在しないことは分かるが、そこからどうすれば良いか分からなかった。

　nが奇数ならC1のままでOK。

　nが偶数でもC1の解法を利用を考えるべき、というのが重要か。

　そのままだと、最初の要素が上手くいかないので、そこをどこかとswapすれば良いのでは？　と考え、最上位bitに思い至れば構築方法が分かる。

　偶数の場合、全く別の構築方法が必要だと考えてしまったのがまずかったかもしれない。が、普通に難しい気がする。

D1. Little String (Easy Version)

　苦戦したが自力AC。

　こちらはcについてはあまり考える必要がなく（答えがn個程度の数の積になるため）、数え上げを行う問題。

　まず、S[0]="0"やS[-1]="0"のときは存在しない。

　それ以外のとき、0001という部分を一度に考える。

　012までの位置関係が決まっているとし、そこに3～6を付け加えるとすると、6はその最も左か最も右におくしかない。そして、3～5は端以外のどこにおいても良い。

　なので、2（左右）*3*4*5をかける。

　……というのを繰り返していく。

　かなり長いこと実験したら気付けたけど、難しかった。

　

AtCoder Regular Contest 213 (Div. 1)

　Aしか解けず。そのAで酷く時間がかかってしまった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 213 (Div. 1) Aのみで破滅
A costは転倒数。転倒数は高々36なので36歩以上進む場所は必ずいけるとして良い。DP[i]でi番目を使ったとき獲得したお金として、累積maxを組み合わせればOK。が、DPの初期値を0にしてずっと気付かず13ペナ。序盤、絶対使えないやつがあるもんねぇ。

— titia (@titia_til) January 25, 2026

B - Hamming Distance is not 1

　ヒントだけ見て解こうとしたが、全然答えが合わず20ペナ以上を重ねた。

　bitcoutを2で割った余りが重要なのは分かる。

　bitcountが奇数のもののみ、もしくは、偶数のもののみを集めたものは条件を満たす。

　ところで、2nと2n+1はbitcountの偶奇が必ず異なる。（これを利用することはコンテスト中気付いていなかった）

　なので、全体の約半分は必ず含めることができる。

　問題は、Lが奇数、Rが偶数のとき、L～lastまではbitcount偶数（奇数）、last+1～Rはbitcount奇数（偶数）のものを採用すると、答えが一個増える場合があること。（このことにはコンテスト中気付いていた）

　そのようなlastをどう求めれば良いか？　というのが分からなかった。

　あるbit iについて、R^(1<<i)がL以上だったとする。すると、それとRが同じグループに入っていてはいけない。なので、lastはR^(1<<i)以上と分かる。

　これを繰り返していけば、lastの候補を絞っていってACした。

　公式解説では、LとRで異なる最上位bitに着目しているよう。なるほど。結果的には同じものを求めていそうですね。

　二部グラフへ持ち込む証明は思いつかない。というか、最大独立集合（参考）について理解していなかったことに気付きました。

yukicoder contest 491 Go on Back!!

　Cまで三完。

コンテストへのリンク

No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?

　一応自力AC。

　二分探索し、P番目の価格の値が求まれば、復元は難しくなさそう。が、コンテスト中は二分探索の判定方法で詰まり解けなかった。

　ソートして二分探索して……では、同じ色の場合の処理が難しい。

　こういうときは、片側だけ色で分類すると良い。半分全列挙のときと同じ感じでやれる。

　

　各トップスに対して、

・全体で何個が価格X以下か？

・同じ色のものについて、何個が割引せずに価格X以下で、割引した後価格X以下か？

　はどちらも二分探索で求められるので、判定できる。

　復元は簡単だと思ったが、復元でも詰まった。

　同じ色のものが答えになるときは簡単。

　そうでないときは、価格Xになるものの個数がbisect(A,X)-bisect(A,X-1)で求まることを利用した。

　全体で、価格Xになる個数と、同じ色で価格Xになる個数を比較し、全体の方が多くなっていればOK。

No.3437 [Cherry 8th Tune C] Silhouette

　自力AC。

　三点がどこに映るかを計算し、三角形の面積を求めれば良い。

　ただ、最初から割り算をmod 998244353で行うと正負が分からなくなる。なので、分数で計算し、最後にmod 998244353の形に直した。PythonのFractionをそのまま使ったらTLEだったが、入出力高速化してAC。

　模範解答は、三角形の向きを行列式で求める方法らしい（よく分かっていない）。

No.3438 [Cherry 8th Tune D] 競プロは向いてない

　自力AC。

　実験したら、凸包内部にあるときはNoそう。具体的な（A,B）を求める方法は分からなかったが、凸包の前後の頂点だけ見て乱択したらACした。

　しかし、凸包の前後の頂点だけ見れば良いという予想が正しいのなら、不等式を解くことで具体的な（A,B）を得ることはできそうですね……。後から気付きました。

　乱択は嘘っぽいけど、どういうときダメなのかはよく分かっていません。

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

　Fまで。

　Fは初めから解法は合っていたので、どうしたら良かったのか悩む。定数倍高速化を頑張るより、codonを試す方が良いんだろうか？

コンテストへのリンク

コンテスト後のツイート

F DPと復元をやるだけ。だが、普通に書くとPyPyだとTLE&MLE。高速化しても2caseでTLEが取れず困ったし、ランダムテストしてもどういうケースで落ちているか分からない→ダメ元でcodonで提出したらACした。えー。
G 遅延セグ木で解けそうだが……。

— titia (@titia_til) January 17, 2026

G - Takoyaki and Flip

　解説・解説放送を見てAC。

　遅延セグメント木を使うとは分かっていたが、基本的なことからおかしかった。

　もつデータを（最大値, flipしているか）だけで良い気がしていたが、それだと、複数の皿が「全て表か、全て裏か」の二通りの状態しか表せないので明らかに間違っている。

　それを解消するため、表の皿が何枚で裏の皿が何枚か、というのをもつようにすれば自然と遅延セグメント木に乗る。

　ただし、遅延させるものは、

・(a, b)　a回flipした後、b加算

　なのだが、(a, b)の後に(c, d)を行うのと、(c, d)の後に(a, b)を行うのとで結果が違うことに注意が必要だった。

　自分が解いてきた問題は、ここが可換なことが多かった気がする。順番に注意しなくてはいけなかった。

　ところで、PyPyだと1873msなのだが、codonだと301msでした。codon凄い！