2026年5月11日月曜日

AtCoder Regular Contest-- 219

　Cまで三完だが、Aは嘘だった。DもEも思いつきにくい部分は思いついていたのだが。

コンテスト後のツイート


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が左半分に……みたいなときに連結性が保たれない。連結性を保つような取り方はあるはずだけど、若干実装の手間が増えるし、コンテスト中はそもそも反例に気付いていなかった。

　★が本質だと思うのに、★に気付いても違う方針へ行ってしまったのは痛い。

　一番の鍵となる部分は思いついて実装していたため反省点も見出しにくく、冷静にならないと……くらいしか言えないのも辛いところ。
時刻: 0 件のコメント:
ラベル:

2026年5月9日土曜日

yukicoder 499 contest

　Fを考えていたが分からず、Dのみ一完。


No.3537 Thank You!

　解説AC。

　どのカードを1にするか決めたら貪欲で良い……というのはコンテスト中から分かっていたが、それは簡単に求められないと思って迷走してしまった。（安い方からあるところまで貪欲に買った後、それ以降で個数が一番多いものを1にする、とすれば良いと思ったが嘘でした）

　二分探索を使えば、実装はやや難しいが普通に計算できた。これは気付かなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2026年5月8日金曜日

Next DP Contest

　F以外の4点以下の問題は正解。後は部分点を拾った。もう少し取れないとまずい。

コンテスト後のツイート

J - 個数と総和

　この問題と同じテーマというのを見てAC。
　「繰り上がりを持つ桁 DP」と呼ばれているのは知らなかった。

　類題をACしたときは理解していたのだろうけど、DPテーブルを使い回して解くという解法を忘れていた。結構汎用性がある解法のようなので、ちゃんと身に着けておきたい。





時刻: 0 件のコメント:
ラベル:

2026年5月7日木曜日

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

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

コンテスト後のツイート

E - Endless Holidays

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

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

F - Plan Holidays

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

　これも、セグ木で解けると気付かなかったことが敗因。
　多分、クエリが与えられて、[l,r]の範囲での答えを求めよ、と言われていたら解けていた気がする。
　その問題が解けるならこの問題も解ける、と気付くのが大事。



時刻: 0 件のコメント:
ラベル: ,

2026年5月6日水曜日

yukicoder contest 聖光学院プログラミングコンテスト2026 day2

　A一完で睡魔に襲われ撤退。


No.3527 Minimum Abs Sum

　解説AC。
　最初はCHT（slope trick）に見え、その後も、係数が一番大きいところなどと考えて失敗。

　係数が全て1のときの解法は知っていたし、
・abs(a*x+b)=a*abs(x+b/a)
　という式変形も見たことがあったはず。
　それにもかかわらず解けなかったのは反省。

No.3528 Happy XOR Candy

　自力AC。
　総xorが打ち消し合うというのはどこかで見たことあったと思う。
時刻: 0 件のコメント:
ラベル:

2026年5月2日土曜日

Codeforces Round 1095 (Div. 2)

　Cまで三完。レートがひどいことに。

コンテスト後のツイート

D. Reserved Reversals

　解説AC。

　コンテスト中、初手実験に行ったのは良かったと思う。
　そこで、min(A)とmax(A)の偶奇が違う場合は、必ずYESになる……などということは分かった。
しかし、そこから良い性質が見つけられなかった。

　ここで、「min(A)とmax(A)の偶奇が違う場合は、必ずYESになる」のはなぜか？　などと考えれば良かったのかもしれない。
　たとえば、「4 3 1」のとき、1と3を入れ替えられるのはなぜか？　と考えるべきだった。
　それは、4が使えるからである。
　そこから、3より大きい偶数、もしくは1より小さい偶数があれば入れ替えられそう……と気付く……という流れはそんなに不自然に思えない。

　だが実際はそういう風に思考できていないわけで。
　実験すると、一直線に答えが求まるのでは？　と考えて思考することが疎かになりがちなのが問題。実験して得た結果について考察することに失敗していることが多い。




時刻: 0 件のコメント:
ラベル:

yukicoder contest 498 リアクティブコンテスト

　C一問完。DやEを考えていたが分からなかった。リアクティブ（インタラクティブ）形式の使い方が斬新な問題が多くて良かった。


No.3519 A/B問題

　自力AC。

　結果的には公式解説と同じ方法でやっていたが、これが筆算と同じだと気付いていなかった。解説を読んでびっくり。

No.3521 接線の傾き

　自力AC。
　コンテスト中、結構考えて思いつかなかったのに、今見たらすぐに気付いた。平均値の定理は知っていたのにねぇ。

No.3522 冪乗乗

　公式解説が賢い。こういう式変形をぱっとできたら嬉しいね。
　ただ、tester解は思いつける内容だったので、できなかったことを反省。
時刻: 0 件のコメント:
ラベル:

2026年4月25日土曜日

yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1

　B一完。CとDを考えたが分からず、Bだけ解いた。しかし、Cは解けなくてはいけない問題だった。


No.3513 Greedy Yokan Party

　解法ツイートを見てAC。

　答えで二分探索して、大きい方から二番目の長さがmid以上になるような、K個の分割があれば良いということは分かったが、その判定問題が解けなかった。

　が、落ち着いて考えるとこれはDPで解ける。0/1/2回mid以上のものを取ったときのindexまででの最大分割数を配列として持てばOK。

　DPで解けると言われればすぐに気付いたので、落ち着けば解けたはずの問題だった。

No.3514 Majority Driven Tree

　解説AC。

　木DPは考えたのだが、遷移の式などが上手く立てられず、全方位木DPが必要か？　などと考えてしまった。
　DPテーブルを二つ用意すれば解けるというのはびっくり。「親が既に塗られていると仮定したときのコスト」を用意すると上手くいくとは気付けなかった。
　二つDPテーブルを用意すると知った後なら、遷移を書くことは難しくなかった。

No.3515 Anti EIKO

　解法ツイートで行列累乗を使うと知ってしまったけど、大体自力AC。

　Kが小さいときはDPで求められることに気付けば難しくなかった。
　これは自力で解けたはず、と思う。コンテスト中、最初にこの問題を開いたのに、ちゃんと考えずに違う問題に行ってしまったのは良くなかった。
　

　
時刻: 0 件のコメント:
ラベル:

2026年4月24日金曜日

Educational Codeforces Round 189 (Rated for Div. 2)

　Eまで五完。

コンテスト後のツイート

F. String Cutting

　解説AC。
　コンテスト中に考えていた方法はダメだった。誤読で間違えただけだったら、ちょっと直せば通るはずだけどそれでは無理で、根本的に間違っていた。

　気付いていなかったのは、
・各開始位置indexについて、S[index:?]を考えるとき、n,k,lの条件から?は定まる。（そもそもその開始位置では条件を満たさないものもあるが、それも判定できる）

　ということ。
　言われてみれば当たり前ですね。

　これを使えば、Suffix-arrayとLCP配列を使ってどの開始位置が最適かを調べることができる。
　Suffix-array配列をSAとすると、SAの中でできるだけ後ろにある開始位置が良い。その長さがLCP配列より大きければそれが答え。そうでなければ、SAの一つ前の開始位置のものの方が良いかもしれないので比較していけば良い。







時刻: 0 件のコメント:
ラベル:

2026年4月21日火曜日

AtCoder Regular Contest 217

　AB二完。Bはまあまあ速かった。実験したら解ける問題はある程度速く解ける（こともある）らしい。

コンテスト後のツイート

C - Greedy Customers 2

　公式解説を読み、解説放送を見てAC。

・所持金のmultisetが同じなら、人がどういう順番で来ても買う商品のsetは変わらない

　というのが気付くべきポイント。これにも気付いていなかったので、コンテスト中のACは遠い。

　その後はDPなのだが……。

　品物がk個以上売れる確率を求めたいというのは良い。
　が、k回そういうDPを行うというのは意外だった。

　DP[i][j]でA[i]以上のお金をj人が持っている確率、とすれば、kを固定していれば遷移が回るというのは分かりやすい。が、kを固定しないと回らない（のか？　少なくとも解説ではそうなっている）というのが混乱しやすい気がした。

　なお、PyPyではTLEしたため、codonでACした。




時刻: 0 件のコメント:
ラベル:

2026年4月19日日曜日

キーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）

　Eまで五完。

コンテスト後のツイート

F - Make it Palindrome 2

　解説放送を見てAC。

　結局のところ、「区間加算がきたら差分を取って考える」ができていなかった。この典型にはいつもやられている気がする。

　今回は忘れていたわけではなくて、コンテスト中、差分を取って考えてみようとはしたのだが上手くいかないと思ってやめてしまっている。
　しかし、区間の話を二点の足し引きにできているという時点で前進しているのだから、捨てたりせずちゃんと思考を進めるべきだった。

　あまり意味のない言い換えに思えたとしても、やっておかなくてはいけない。

G - Mode in the Subtree

　解説、解説放送など色々参考にしてAC。

　その過程で、HL分解について、HL分解した後にセグ木などに乗せる場合の並べ方を勘違いしていたことに気付き、自分がHL分解を初めて知ったこの問題をようやくACした。
　HL分解した後、色々したいなら、オイラーツアー順に並べるのが鉄則！　そうすることで、子孫たちが区間に並ぶので、上手く処理することができる。

　このこと自体は知っていたけど、当時は知らなかったのかな？　HL分解とこの処理を組み合わせられるというのは初めて知りました。

　さて、この問題ではDSU on Treeを初履修した。

　アルゴリズム自体は分かりやすいけど、正当性の胆は、「全ての頂点における「light edgeたちに関する子孫の個数」の総和はO(NlogN)になる」ということだと思う。公式解説でもそう書いてあるのだけど、理解できず生成AIに相談してようやく理解できた。

　その上で、定数倍が厳しく、PyPyじゃ通せずcodonで通したのだけど、PyPyで通している人もいますね。もっと上手くやる方法があるのかな。
時刻: 0 件のコメント:
ラベル: , ,

2026年4月17日金曜日

AtCoder Beginner Contest 453

　Eまで五完。
　順位表を見てGまで行ったが、Gは未履修で、思い付くのは不可能だったように思う。実装も非常に大変だった。

コンテスト後のツイート

G - Copy Query

　解説AC。
　永続セグメント木を初めて勉強し実装した。
　遅延セグメント木などを理解していれば理解することは難しくないが、実装はかなり大変だった。

　セグ木の値、各nodeの左側の子、右側の子、親、その区間の左端と右端、各Versionの根の値などを更新があるごとに追加していく。ちょっとTrie木のような実装を行った。


　


時刻: 0 件のコメント:
ラベル: ,

2026年4月16日木曜日

AtCoder Beginner Contest 452

　Fまで解けたが遅かった。

コンテスト後のツイート


G - 221 Substring

　自力AC。

　コンテスト中の方針であっていた。数字の個数＝数字の大きさならそのまま、個数が数字の大きさより大きければ、k 0 kと置き換えて並べる。
　その上で、Suffix array、各indexから0までの個数を調べていく。そのままだと重複が出るが、LCP配列を使えば重複は除ける。

　コンテスト中に失敗していたのは、自分のライブラリだと文字列Sの後ろに、最も小さい文字（今回は数字）を置いておかねばいけないところだった。あとは、SA[i]でi番目に小さいindexを表すのだが、その逆関数なのかどちらか分からなくなって混乱したところ。ただ、これは久しぶりにSuffix arrayを使ったのだからしょうがない気もする。

　後はすんなりできた。
　Fより時間かからなかったと思うので、F捨ててG行けば通せてたかなぁ。


時刻: 0 件のコメント:
ラベル: ,

2026年4月9日木曜日

Codeforces Round 1091 (Div. 2) and CodeCraft 26

　Cまで三完。過去最悪に近い成績。しかし、DもEも難しい気がしたが……。

コンテスト後のツイート

D. Flip the Bit (Hard Version)

　解説AC。

　隣接する値が異なる場合は1、同じ場合は0とする配列を持っておく。
「ある区間の反転は、この配列の二項を反転させるもの」と捉えるのは（この前のARCのAで出題されたので）覚えていた。

　さらに、この問題のようにindex iを含む区間の反転は、
★「iより左側とiより右側で反転させる」と捉えることができる。

　ここで、P[i]で配列を区切っていくつかの区間を持つと、
★「二つの別の区間から反転する」という操作なら全て行えることが分かる。

★ところで、最終的な値を0にしたいなら、Aの左右に0が広がっていると考えても同じ。

　そう捉えて区間を分割し、隣接項が違うものの個数を数えたものをSとすると、
・Sの異なる項から1ずつ引く
・Sの一つの項から1を引く
　の操作を行ってSの全ての要素を0にするとき、最低何回必要か？　という問題になり、これは、最大値で場合分けしたりheapqを使ってシミュレーションしたりすれば解ける。

　難しかった。
　★で書いた三つとも自力では思いつけなかった。隣接xorを取る部分は定石だけど、それ以降の処理にも難しい部分があると、なかなか正解まではたどり着けない。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 1090 (Div. 4)

　全完したが順位はあまり良くなかった。そんなに遅かった気もしないのに厳しい。

コンテスト後のツイート



時刻: 0 件のコメント:
ラベル:

2026年4月4日土曜日

yukicoder contest 496

　Fを考えたが解けなかった。


No.3492 区間冪乗加算一点取得

　解説AC。

　まず、D<=100に気付かなかったのが敗因。だが、解説を見ても、なかなか理解できなかったのは良くない。内容的には、D<=100に気付いたなら解けなくてはいけない問題だった。

　ただ、D<=100でクエリ問題だからやることが決まってくるから解法に気付きやすいというだけで、(i+C)^Dののd次数目が、CやDが変わっても似た形で表せるというのは意外だった。立式をすれば分かることとはいえ、こういう観点で見たことがなかったので面白かった。

No.3493 等比数列の和の素因数

　解説AC。

　いまだにフェルマーの小定理やオイラーの定理があやふやなのが敗因。
　等比数列の和の公式を考えた後、オイラーの定理を使う方向で考察を進めなくてはいけなかった。ちゃんと立式して、落ち着いて考えるべき。

　


時刻: 0 件のコメント:
ラベル:

2026年3月29日日曜日

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)

　C1までとDの四完。

コンテスト後のツイート

E. Minimum Path Cover

　解法ツイートを見てAC。
　gcdたちのうち必要な値を何個か持たなくてはいけないと思ったが、それらをlcmで代用することが可能だった。
　言われれば確かに……。

　木DPのとき持つ値は一個で良いはず！　という気持ちになれば思いつけたはず。TLEになるだろう提出の結果を待っていたのはダメでどうにか一個の値にできないか？　と粘るべきだった。
　


時刻: 0 件のコメント:
ラベル:

2026年3月28日土曜日

yukicoder contest 495

　BとEの二完。あとはFを考えていたが分からず。Eは上手い方法が分からず、a,b全探索でcの範囲を定め、その後、ミラー・ラビン素数判定法を使って判定、で通ってしまった。良かったのかなぁ。


No.3483 A Forbidden Fruit

　自力AC。

　自力ではあるのだけど、たとえば、「M個の中からr個選んだとき、外れ（の一個）が含まれない確率」が1-r/Mであることも計算しないと気付かなかった。
　確率について直感が働いてないなぁ。

No.3484 Just a Maze Game

　大体自力ACだが、Wと書くべきところをMと書いたり、W=5, 7だけ書いてW=3の場合を書き忘れたりと、ミスが多かった。

No.3486 Draw a Rainbow

　解説AC。

　最初解説を見て、ゼータ変換やメビウス変換を理解できていないから解けなかったのかと思ったが、実際はDPの方針が立てられなかっただけでした。反省。

　ゼータ変換やメビウス変換は、（今回のように集合に関するものの場合）bitごとの累積和やimos法なだけなので、全く恐れる必要はない。フーリエ変換と違って集合や約数の畳み込みは難しくない。（フーリエ変換はいまだに難しい……）

　なお、今回の自分の解答ではBitwise OR Convolution自体は使わず、DPとして累積和を取ったとき（ゼータ変換したときの値）をそのまま持って計算し、最後に一回だけメビウス変換を行った。

　集合に関するこのあたりの変換が分からなくなったときは、この問題のりんごさんの解説放送を見るのが手っ取り早いと思う。

　
　
時刻: 0 件のコメント:
ラベル: , , ,

2026年3月26日木曜日

AtCoder Regular Contest++ 216

　一問も解けず。

コンテスト後のツイート


A - Reversi 3

　解説AC。
　既出で解いたことのある問題だった。
　時間が経っているので忘れているのは仕方ないし、この解法を思い付くのは難しいと思うので仕方ない面もあるが、初手の隣接xorを取るところすら思いつけなかったのはまずかった。
　隣接xorを取った後の処理も思いつきにくいが、偶奇に着目するのはやってみなくてはいけない。

　定石の組み合わせではあるのだが、調子良かったとしても本番中に自力で思いつけた可能性は低かった気がする。最初に問題を見たとき、これ既出じゃないの？　と思ったので、その疑いに従って検索した方が良かったか？（とはいえ、見つけるのは至難のわざという気もする）

　






時刻: 0 件のコメント:
ラベル:

2026年3月25日水曜日

AtCoder Beginner Contest 450

　ABCDFの五完。なんとかFを解けて良かった。

コンテスト後のツイート

E - Fibonacci String

　コンテスト中のコードを修正してAC。

　コンテスト中に見逃していたのは、[L,R]の文字の個数は[0,R]の範囲のものから[0,L-1]のものを引いて求められるということだった。基本的なことだけれどなぜか忘れて最後まで気付けなかった。
　[L,R]のまま扱おうとしたことでlが大きい場合にREになるコードになっていたのも本質的にまずい。これも、ここを直すと自然と修正された。

　これでREが取れ、再帰の変数を一個減らすことができ、メモ化再帰を用いてcodonでAC。

　しかし、PyPyではACできず、なぜ？　と思ったが、メモ化再帰で使っているdictのせいで遅くなっていた。
　再帰の回数は少なく、あえてメモ化する必要はない。各段階での文字の個数は前計算できるので、それを使えばPyPyでもACできた。



時刻: 0 件のコメント:
ラベル:

2026年3月21日土曜日

yukicoder contest 494 オムニバス

　Cのみ一完。Dを最初に考えたが分からずCに行ったのだが、Dを分からなかったのはまずい！


No.3476 {2^n-1}-gon

　円の中心を含まないものを引く。
　円の中心を含まないものは、最も左の点を固定し、そこから半周以内にM個全てが収まっているようなもの。
　全体の個数も、引くものも二項係数で求められる。

　これ、概ね最初に考えた解法だったのだが、なんでNは2ベキ-1なんだろう？　とか、引く数はこれで良いのだろうか？　などと考えてしまい混乱。もっと落ち着いて自然に考えていれば解けたはず。

No.3474 Concat Decimal

　自力AC。これは普通に解けた。
　全ての(i, j)でなく、i<jなるペアのみなのがちょっと引っ掛けっぽいですね。

No.3473 AtCoder < CMS

　解法ツイートを見てAC。自力では分からなかった。

　2^M-1を含む場合を考えると、各bitごとに、0/1を割り振るもののうち、全て0を除いた場合の数と一致する。（ここが分からなかった！）

　あとは、2^M-1を何個含むか考えれば良い。
　式変形をすると二項定理が使える形になるので、それで計算すれば解ける。

　難しいが、解けないのはダメ。

No.3477 Yet Another LIS Triangle

　自力AC。
　これは簡単でした。

No.3478 XOR-Folding Primes

　自力AC。
　2,k,k+2という素数の三数がたくさなあり、その間を行き来するしかない。

　素数を列挙した後、行き先を考えてDP→行列累乗で解ける。

　Mまでにkが含まれるがk+2が含まれない場合、2→kみたいな行き方がありうると思ってしばらく悩んでしまった。このときは、P_iがk+2になるので、ありえないのですね。
時刻: 0 件のコメント:
ラベル:

2026年3月8日日曜日

AtCoder Beginner Contest 448

　Eまで。D・Eとも若干苦手な問題だったとは思うが、時間かかり過ぎてしまった。Eを飛ばしてFへ行った方が良かったか？

コンテスト後のツイート

F - Authentic Traveling Salesman Problem

　自力AC。

　コンテスト中、Moじゃダメだと思った理由は、MAX=2*10^7として、MAX√MAX>10^10だからダメだと思ったせいでした。
　MAX√Nと比較しないとダメですね。

　ただ、コンテスト後の実装でも、ミスで3ペナしてしまったので、コンテスト中にEを飛ばしていたら必ず通せていたとも言えなそう。
時刻: 0 件のコメント:
ラベル:

2026年2月27日金曜日

yukicoder contest 493

　AHC中だったのでAだけ解いて撤退。
　Bは読んで多少考えたので、すぐ解けたのなら解いていたと思うが。


No.3448 ABBBBBBBBC

　解法は自力で分かったが、WAだったためテストケースを見てAC。

　こういうのを合わせるのどうすれば良いんだろう？　本番ならランダムテストを書いて頑張ると思うが、短時間で解ける気がしない。
　割り算の感覚（商と余りなど）が重要そうだけど。
時刻: 0 件のコメント:
ラベル:

2026年2月25日水曜日

AtCoder Regular Contest 215

　Cまで三完。良い成績とはいえないが、ARCで黄パフォを出せたのは久しぶり。

コンテスト後のツイート

D - cresc.

　解法ツイートを参考にAC。

　Aの一つおきの配列が広義単調増加になることはコンテスト中に気付いていた。しかし、それだけだと重複があってダメ。

　じゃあ、重複をなくすためどこか固定・場合分けすればいいのでは？　と考えるのが重要。

　A[0]=0とした場合、A[1],A[3],...は全ての広義単調増加列を取りうる。
　それ以外の場合、A[奇数]の最後の値がMにならなくてはダメ。なぜなら、A[偶数]を全てｰ1したものが同じ配列を作るから。

　これで重複なく全て数えられているので、二項係数を使って計算できる。


　初項を固定・場合分けする発想がもてれば決して難しくないし、重複をなくすためにどこか固定してみようと考えるのは自然。
　今見ると難しくない気がする。

　また、二項係数の何か（積か和か）になりそうなことはコンテスト中から見当がついていたし、実験コードも書いていた。

　それで解けないのは、こういう二項係数を使う数え上げに苦手意識があるのかなぁ、と思ってしまう……。
　

E - CNOT Party

　悩んだが自力でAC。

・最初にできるだけ0→1にする
　のは最適そう。なぜなら、逆の手順をやれば1を0に戻せるので。

　コンテスト中は、その後、今作ったトポロジカルソート順の逆順？　などと考えてしまいダメだった。

　この後、
・1→0にする部分は別の問題

　と捉えると分かりやすい。こう思いつくのが重要だった。
　すると、B[i]=1のものは最後まで残ると分かるので、そこを根としたトポロジカルソートの逆順を考えれば良い。
　ただし。x_i=y_iなるものがあればそれも起点になることに注意。

　その順に1→0に戻していけば答えになる。

F - Scapus

　自力AC。
　直径は明らかに良いパス。

　そこから考えると、直径上に通らなくてはいけない点が何点かあり、それを含む全てのパスが良いパスになると分かる。

　あとは通らなくてはいけない点が一点になるかパスになるかで場合分け。

　パスの場合は、二つの端点から距離xでいける点の個数は何個あるかを調べ、それらを足し合わせれば良い。これが畳み込みの形になり、FFTが必要になったのにはびっくりした。

　一点の場合も同じなのだが、畳み込みの際の配列の長さを意識しないと計算量が落ちない。そこを気を付けて実装したらACできた。

　実装は面倒だが、割合素直な発想で解ける問題だった。
　


時刻: 0 件のコメント:
ラベル: ,

AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選　（AtCoder Beginner Contest 446）

　全完できた。
　簡単めの回とはいえ、全問解けると嬉しい。Gは想定の計算量ではなかったようだけども。

コンテスト後のツイート









時刻: 0 件のコメント:
ラベル:

2026年2月18日水曜日

AtCoder Regular Contest 214

　ABの二完。ARCで連敗が続く。

コンテスト後のツイート

C - Divide into 4 Teams

　解説放送を見てAC。

　コンテスト中、SUM/2の二つに分けることは考えたが、その後何も思いつかなかった。
　
　ランダムテストを書いて実験すべきだった、ということはあるかも。SUM/2の二つに分ける方法と、答えとを比較したら答えが導けた可能性はあるね。

　今回のSUM/2の二つに分ける方法みたいに、これを使いそうだと感じたのなら、とりあえずそれを求めてみて答えと比較して考えるのは一つの方針としてありそう。

D - Distinct Sum Grid Path

　コンテスト直後にしばらく考えても解けなかったが、今考えたら簡単に解けた。
　1から順に数字を作っていこうと考えるのは自然（コンテスト中も、まず考えたはずなのだが……）で、右上ルートより左下ルートが大きくなるようにしようとしたら自然に構築できる。

　普段なら解ける問題という気もするので、あまり解けなかった原因を考えてもしょうがない気もする。
　が、こういうのが解けるかどうかでレートには大きく差が出るんだよねぇ。









時刻: 0 件のコメント:
ラベル:

yukicoder contest 297

 　Bまで。コンテスト後にCをAC。


No.1520 Zigzag Sum

　自力AC。
　実験したらACできたが解説の考え方を再現するのは難しい。

No.1521 Playing Musical Chairs Alone

　自力AC。
　行列累乗が思い浮かべば難しくない。

　一回遷移行列を間違えた（行と列を逆にした）けど、それでsample通るのね。
時刻: 0 件のコメント:
ラベル:

2026年2月17日火曜日

yukicoder contest 292

　Cまで。Dはコンテスト後にAC。



No.1490 スライムと爆弾

　自力AC。
　簡単だったけど、

・各マスのダメージがいくつかを求めるためのimos法
・矩形のダメージの総和を求めるためのimos法

　を両方やるので、二回累積和を取ることになるのが面白かった。




時刻: 0 件のコメント:
ラベル:

2026年2月15日日曜日

AtCoder Beginner Contest 445

　Fまで六完。Gも解法はあっていた。惜しかった。

コンテスト後のツイート

G - Knight Placement

　フローした後、最大独立集合を求めるために色を塗るところで、色を塗った後間違ってもう一回初期化してた（塗った色を消していた）のが敗因だった。一行消したらバグは取れ、そのままだとTLEしたけどfloat("inf")を1<<63に直したりしたらACした。
（ただし、1<<30にしたらもっと早くなるかな？　と投げてみたらTLEしたので、運が良かっただけみたい。コンテスト中のACは厳しいかも？）

　惜しかった……。




時刻: 0 件のコメント:
ラベル:

2026年2月7日土曜日

yukicoder contest 492

　A一完。Bを考えているとき睡魔に襲われてしまった。

No.3441 Sort Permutation 2

　自力AC。

　index x→P[x]に辺を張り連結成分ごとに分解した後、その差のgcdがxなら、xの約数たちには連結成分-1をプラスする。
　と、これが必要条件なのはコンテスト中に分かっていたが、それ以外にも答が増えることはありそうに思い、たとえば、「3 4 2 1」のとき2を使わないようにできるか？　と考えていた。
　コンテスト後に実験してみると、結構簡単に使わずにソートできたので、上で書いた必要条件が十分性を満たしそう、と思って提出したらAC。

　なお、これだけで良いことは、公式解説を開いても「帰納法などで証明可能」としか書いていなかった。現在も証明方針が分かっていないが、やろうとすれば自力で証明できるのだろうか（やる気はない）。

　
　
時刻: 0 件のコメント:
ラベル:

2026年2月2日月曜日

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

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

コンテスト後のツイート

F - Non-Increasing Number

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

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

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

　なのだが、最小性を言うため、どの数字を使うか、という順番も大事。
　普通にやればこの順番を満たすのだが、ソートしたりしてしまいハマった。

　一桁のときは、
・[(1, 1), (2, 2), (3, 3), (4, 4),...]
　となっており、これが一番上の桁なのだがから、
　左から順番に、かつ次に使う数字が小さい順に探索していけばOK。

G - Another Mod of Linear Problem

　解説放送を見てAC。

　floor sumを使うと言われても、自力では全く分からなかったのでコンテスト中に解くのは厳しかった。

　解説放送のように、X_k>C（定数）の場合を絵で理解できていることが大事な気がする。それが押さえられていれば応用できそう。
時刻: 0 件のコメント:
ラベル:

2026年2月1日日曜日

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。

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

No.1716 Bonus Nim

　自力AC。

　普通のNimよりBobが勝つのは難しそう。
　で、最初Bobは勝ちがないのでは？　と思ったのだけれど、sampleに一個勝つ例が書いてあり、真似っこ戦略なら勝てると分かった。

　これ以外ないと予想し、AC。

時刻: 0 件のコメント:
ラベル:

2026年1月28日水曜日

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

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

コンテスト後のツイート

G - Lightweight Knapsack

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

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

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





時刻: 0 件のコメント:
ラベル:

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をかける。
　……というのを繰り返していく。

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

　
時刻: 0 件のコメント:
ラベル:

2026年1月27日火曜日

AtCoder Regular Contest 213 (Div. 1)

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

コンテスト後のツイート


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に着目しているよう。なるほど。結果的には同じものを求めていそうですね。
　二部グラフへ持ち込む証明は思いつかない。というか、最大独立集合（参考）について理解していなかったことに気付きました。
時刻: 0 件のコメント:
ラベル:

2026年1月25日日曜日

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）を得ることはできそうですね……。後から気付きました。

　乱択は嘘っぽいけど、どういうときダメなのかはよく分かっていません。
時刻: 0 件のコメント:
ラベル:

2026年1月22日木曜日

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

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

コンテスト後のツイート

G - Takoyaki and Flip

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

　遅延セグメント木を使うとは分かっていたが、基本的なことからおかしかった。
　もつデータを（最大値, flipしているか）だけで良い気がしていたが、それだと、複数の皿が「全て表か、全て裏か」の二通りの状態しか表せないので明らかに間違っている。

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

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

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

　なのだが、(a, b)の後に(c, d)を行うのと、(c, d)の後に(a, b)を行うのとで結果が違うことに注意が必要だった。
　自分が解いてきた問題は、ここが可換なことが多かった気がする。順番に注意しなくてはいけなかった。

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


時刻: 0 件のコメント:
ラベル: ,

2026年1月18日日曜日

AtCoder Regular Contest 182

　ABの二完だが、レートは上がった。

コンテスト後のツイート


C - Sum of Number of Divisors of Product

　解説AC。
　積の和典型の練習をしようと思って解こうとしたが難しく、解説を読んでもしばらく理解できず非常に苦労した。

　公式解説のように積の和典型を適用すると、タワーと積み木の問題と同等になることは分かる。しかし、それがbit DPで表せることが分からなかった。（ChatGPTに聞いたりしつつ悩んだ）

・どこかで積み木を選ぶのだから、積み木を置いたそのときに選べば良い

　と考えると理解できた。
　たとえば、「6」の積み木を置くとき、それは、2と3の位置に積み木を一個ずつ選ぶことを意味する。
　そして、それまでに2の位置や3の位置の積み木を選んでなかったとしたら、このときに選べば良い。
　その、既に選んだかどうかでbit DPをしている。

　また、最初に積み木が一個ずつ置いてあり、それを選んでも良いので、bit DPの初期値は全て1になる。

　こういう考え方でDPを書いたものが、この提出。これを行列累乗で高速化するとACできる。



時刻: 0 件のコメント:
ラベル: ,

2026年1月16日金曜日

Codeforces Round 1072 (Div. 3)

　ACの二完。Bで詰まって一旦離脱して、最後に戻ってきてもう少し解こうと思ったけどDが間に合わなかった。


B. Hourglass

　難しくないか？
　mを2*kの余りとした後、sとkの大小で場合分けして考える……という方針は簡単に立つけれど、s=kやm=kのときどうなるか？　など注意すべきところが多い。
　コンテスト後にも2ペナを出してしまった。

E. Exquisite Array

　自力AC。
　差が大きい順に見て、Union-findで要素をつなぎ、答えを更新していく。しばらく思いつかず結構時間がかかってしまった……。

F. Cherry Tree

　自力AC。mod 3での可能な回数の集合を持って木DP。
　この解法はmod 3だからできたもの。maspyさんの解説によると、modが任意の場合にもできるらしいが理解できていない。

G. Nastiness of Segments

　自力AC。セグ木＋二分探索。問題文がやや難読だが、内容は簡単だった。

　結局、Bが一番難しい回だったみたい。
時刻: 0 件のコメント:
ラベル:

2026年1月14日水曜日

AtCoder Regular Contest 212 (Div. 2)

　ABDの三完。

コンテスト後のツイート

C - ABS Ball 

　解説放送を見てAC。

　積の和典型と言われても全然ピンと来ないし、積の和典型の解法自体も忘れているしで全然ダメでした。

　というか、最初この問題を見たとき、積の和典型を使うのでは？　と思ったはずなのに、苦手意識があるせいか、そう思ったことを忘れてDPを考えていたのもダメ。もっと練習した方が良さそう。







時刻: 0 件のコメント:
ラベル: ,

2026年1月13日火曜日

AtCoder Beginner Contest 440 (Promotion of Engineer Guild Fes)

　ABCDFの五完。

コンテスト後のツイート

E - Cookies

　コンテスト中に書いていた方針でAC。
　コンテスト中、例題を解いた経験があると思ったが、実際正しかった（どの問題かは探せなかったけど）。そして、Aを降順にソートして、[K,0,0,0,0]からはじめて、一つずつずらしていく探索をすれば良い……という方針もできていた。

　ただ、コンテスト中は、Kの値が大きいことに混乱して、[K,0,0,0,0]のような配列で扱えると気付かず、Counterを持ち出していた。そのため実装でCounterのhashを求めなければいけなくなったりし混乱。
　そして、hash値を求めているのにその値を使い忘れたり、値が0のときはじくのを忘れたりしてWAが取れぬまま終了した。

　コンテスト中は混乱して、正しいことを書いているのか分からなくなっていたけど、落ち着くことさせできればコンテスト中に通すことも可能だった気がする。






時刻: 0 件のコメント:
ラベル:

2026年1月3日土曜日

Educational Codeforces Round 186 (Rated for Div. 2)

　Eまで。終了後F1は通った、と思ったらシステムテストで落ちた。

コンテスト後のツイート

F2. Christmas Reindeer (hard version)

　自力AC。見直したら難しくなかった。

　各桁について、何個使うのがギリギリなのかが分かるので、ギリギリのときと、それ以上が確定したときに分けてDPしていく。ギリギリのときは何個使えば良いか？　が分かるので、それより大きい個数を使うときは確定。同じ個数を使うときはギリギリ。二項係数で計算する。
　これも桁DPの一種といって良いかな。

　コンテスト中、30分残っていたら解けて良かった気もするけど、問題把握に結構時間かかってしまったなぁ。


時刻: 0 件のコメント:
ラベル:

2026年1月1日木曜日

yukicoder contest 286

　Cまで。


No.1425 Yet Another Cyclic Shifts Sorting

　自力AC。
　二種類あれば隣接要素SWAPができそうなので、答えは高々2。0回の判定は簡単なので、1回でできるかどうかを調べれば良い。

　一回でできるかどうかは、ソートした配列と比較し、最大値が一致していれば消していく。
　残った配列について、ソートしたものを巡回したものになっていれば良いので、ローリングハッシュを使って判定した。

　が、解説を見たらもっと簡単にできたらしい。なるほど。

　ところで、なぜタグが「動的計画法」なのだろう？　解けたと思った後タグを見たらそう書いてあって、何か間違っているのでは？　と疑心暗鬼になりながら実装した。
（タグに頼るのはいけないかもしれないけど、yukicoderのタグはいつも出したまま問題を考えています）

No.1426 Got a Covered OR

　解説AC。
　A_iが全て正、という条件の扱い方が難しい問題。

　包除原理で扱うのかな？　とは思ったものの、DPで包除原理でやるのかと考えてしまってダメだった。

・範囲を分割できること
・それぞれの範囲について、二項係数を使って計算していける

　ことに気付ければ解ける。
　bitの中で条件を満たさないものの個数で包除すれば良い。

　方針が分かれば難しくない。何で包除すれば良いかを考えるのが大切だった。

No.1427 Simplified Tetris

　解法は自力で分かったが、ACするのは苦戦した。

　盤面が与えられたとき、ちゃんと置けるかどうかは、この問題と同じ。
　なので、元の盤面の候補を全探索したい。

　ブロックが入っているマスの前後に何マスあるか？　をDFSで調べれば良さそうだが、何列必要かが分からない。高々2列で十分だろう、と思ったらWAで、3列必要な場合があった。

　そして、それで全探索するとTLEしてしまったため、ずるいけれど時間で打ち切る処理を入れてAC。

　解説を見ると、もっと上手にやる方法が書いてあった。気付かなかった。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)