2026年8月21日金曜日

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

　既出に気付けたおかげで、久しぶりに2400パフォを獲得。全完チャンスだったねぇ。

コンテスト後のツイート



E - Concentration

　自力AC。
　DP[x毎既知][y毎取得][z消費ライフ]とする方針で合っていた。

　コンテスト中は、y枚取得しているとき残っているカードの枚数をN-yにするのを忘れて、yのまま計算していたため答えが合わなかった。
　これくらい気付いて欲しいものなのだが、今（コンテスト後）にコードを見直したときも気付けず、デバッグ出力を行って気付けたので、コンテスト中に気付けないのは仕方ないのかなぁ。
時刻: 0 件のコメント:
ラベル:

2026年8月18日火曜日

AtCoder Regular Contest 227

　AB二完。

コンテスト後のツイート

D - Median of Binary Strings

　解説放送を見てAC。

　全く思いつかなかったのでどうしようもない。なかなか天才的な発想が必要だった。
　これはコンテスト中に解けた気がしないので、他の問題にいくべきでした。







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

2026年8月14日金曜日

ユニークビジョンプログラミングコンテスト2026 夏（AtCoder Regular Contest 226）

　Bまで二完。

コンテスト後のツイート

C - Square Corner Packing

　自力AC。
　ツイートに書いた解法であっていた。HかWが偶数の場合は愚直で良く、(4n+1)*(4n+1)の最大の正方形を入れて、あとは愚直でOK。

　が、実装は大変だった。10分ではとても実装終わらず。早く実装できている人は凄いなぁ。
時刻: 0 件のコメント:
ラベル:

2026年8月3日月曜日

AtCoder Beginner Contest 469

　E解けずABCDFの五完。

コンテスト後のツイート

E - Pro Exam Eligibility

　キーワードを見てAC。解けなくてはいけない問題だった。

　二分探索だと思ったものの判定問題が解けなかった。
　これは「oとxに上手く値を振り分ければ」連続部分列の和が0以上になるか？　という問題になり解ける。

　「oとxに上手く値を振り分ければ」の部分、最近だとこの問題で同じようなことをやっていて、このときは解けている。しかし、実数値を振り分ける問題は見たことがなく、頭が働かなかったのだと思う。
　


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

2026年7月20日月曜日

AtCoder Regular Contest 225

　Dまで四完。Cでバグらせたのが敗因。

コンテスト後のツイート

E - Gap Swap (hard)

　解説AC。

　実験しなきゃ思いつかなかったと思うけど、実験する時間もなかったし仕方なかったか。
　近くの場所へ移動させる貪欲は思いついていたけどねぇ。

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

2026年7月18日土曜日

Codeforces Round 1108 (Div. 2)

　Dまで。

コンテスト後のツイート

E. lce4113 and Security Game

　maspyさんの解説を読んでAC。

　コンテスト中に、o(v, x)=xのとき以外は簡単なことは分かっていた。そして、こちらができることは、xのbitcountを何個選ぶか？　くらいしかなく、それも、一個にするか半分にするか？　くらいしか選択肢はない。

　しかし、つい半分くらいにするのが最善かな？　と考えてしまいダメだった。
　方針転換して一個の場合を追及すれば答えに辿り着けた気もするけど、意外と思いつきにくいし、詰めるのに時間がかかりそう。
時刻: 0 件のコメント:
ラベル:

2026年7月17日金曜日

AtCoder Regular Contest 223

　Cまで三完。三完の速解きにはまあまあ成功したが、DやEで迷走した。

コンテスト後のツイート


D - Xpectation of Cards in Hand with Laboratory

　解説放送を見てAC。
　経路数とか鏡像法とかいうキーワードを見てもピンと来ずACできなかったので、コンテスト中のACは遠かった。

　やることは、
・ドローカードをx軸、普通のカードをy軸としてプロットし、どの経路を計算するかを調べる。
・鏡像法で計算

　というだけ。

　ただ、そもそも、問題文では全てカードを区別しているのに、カードを区別しなくても良いの？　というところから詰まった。
　これは、
・A_1 A_2 B_1 B_2 A_3
　という区別した順列に対して、
・A A B B A
　という区別しない順列を考えると、どんな区別しない順列に対しても、区別する順列はA、Bの並び替えA!B!通りを掛けただけ存在することから分かる。


　また、経路数を求めた後、使っていないA、Bの並び替えを掛けなくてはいけないことにもなかなか気付かなかった。
時刻: 0 件のコメント:
ラベル: ,

2026年7月16日木曜日

Codeforces Round 1109 (Div. 3)

　Eまでしか解けずひどい順位に。

コンテスト後のツイート

F. Anya Loves Trees!

　コンテスト中は何かの実装ミスかと思っていたが、考察が間違っていた。

　あるノードの子の番号たちが、（9が最大だったとき）

・8 9 1 2

　のように、一つながりになっていたら良いと考えていたが、これだと最終的にぐるっと連番になることはできたとしても、1をスタートにできない！

　なので、一番小さい数字から初めて、全て連番になっているようにしなくてはいけない。

　番号が連続になっているかどうかを判定するのには、左右を管理するやつを利用した。

G. Yura and Deadlines

　解説AC。

　条件が、iの条件とjの条件の&に分解できるので、iの条件についてセグ木を使ってやりながら、イベントソートでjの条件を処理する。

　これはFよりはっきり典型的で優しく、解けなくちゃいけない問題だった。
　Fの勘違いは仕方ないところもある。とはいえ、F解けなくて動揺していたとしても、こういうのは取らないと。





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

2026年7月4日土曜日

yukicoder contest 503

　Eを考えていたが解けず、Cのみ一完。

コンテスト後のツイート

No.3580 二成分の和

　解説AC。

　一目見て、連立方程式だから行列……と思ってしまったが、それが間違いだった。
　グラフの問題だと思えば、自然と、連結成分ごとに一つの要素の値を決め打つ、というのが思いつく。

　行列で上手くいかないと思えば、この解法に至るのがそう難しい気はしないんだが……。一旦思い込んだものを方針転換するのは難しい。

No.3581 分数対称差更新区間計数取得

　TLEが取れず、ChatGPTにPyPy→RUSTに変換してもらってAC。

　各クエリにおいて、変更すべき点が√i個に収まるので、BITで管理してACした。

　だが、解説を見ると、平方分割した方が高速になるらしい。言われてみればそういう高速化を要求されたことがあった。忘れていた。


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

2026年7月3日金曜日

CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462)

　Fまで。

コンテスト後のツイート

G - Completely Wrong

　解説放送を見てAC。包除原理で解ける。

　Cを並び替えたもののうちk箇所が一致（C_i=G_iとなる箇所がk箇所）しているものを求めたい。
　これを、各色ごとに求めて、それを合わせることにより求められる、と考えるのがポイント。具体的には、FFT（畳み込み）を使って計算できる。

　最後に、包除原理を用いて、kが奇数のとき-1の係数をかけて足し合わせれば良い。（解説放送では-1を掛けるのをFFTする前にやっていたけど、最後にやってOKですね。その方が分かりやすいと思う）




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

2026年7月2日木曜日

Codeforces Round 1106 (Div. 2)

　Dまで。Eは解法はあっていたので、Fを考えていた時間がなければ間に合っていたかも？

コンテスト後のツイート

E. Cake Trial

　ツイートしていた解法で正しく、定数倍高速化を頑張ったら通った。
　時間があれば他の言語に直してACしたと思うけど、そんな時間なかったから仕方ないね。
　AtCoderならcodonを使えば通せていたはずなので、あまり気にしないようにしたい。


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

Codeforces Round 1107 (Div. 3)

　Eまで。Fを（実験せずに）考えていたら寝てしまった。


F. A Bit Odd

　解説AC。

　難しくないか？　実験せずに思いつける気がしないし、実験したとしても規則性に気付くのは簡単ではないと思う。
　実験せずに解くなら、一回で勝つための条件は……と考えるのだろうけど、思いつくのは困難に思える。そもそも実験したとして解けていたかもあやしい。
時刻: 0 件のコメント:
ラベル:

2026年6月21日日曜日

yukicoder contest 480 (Gemini Tester)

　AB二完だが、BはHackされた。


No.3250 最小公倍数

　マージテクの練習問題だった。
　ただ、PyPyだとTLEし、PyPyで通している人もいなかったので、PyPyのコードをChatGPTにRUSTに翻訳してもらってAC。

　今はこういう翻訳もAtCoderでは禁止されているし、この問題はアルゴリズムの練習問題みたいなものだから、自力で書いた方が良いとは思うけど。
時刻: 0 件のコメント:
ラベル: ,

2026年6月19日金曜日

Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)

　Dまで。二時間近くあってE通せないのは悲しい。

コンテスト後のツイート

E. Permutation Commutation

　コンテスト後、落ち着いて考えたら自力でACできた。

　Functional Graphと見て、サイクルに分解する。

　たとえば、
A=[4, 5, 1, 3, 6, 2]
　を考えると、(1,4,3)と(2,5,6)というサイクルがある。

　これに対応するBは、(1番目, 4番目, 3番目)が(1,4,3),(4,3,1),(3,1,4)もしくは、(2,5,6),(5,6,2),(6,2,5)でなくてはならない。（2番目, 5番目, 6番目）も同様。

　ここまではコンテスト中に実験で分かっていた。i→A[i]とうつるとき、対応するいずれかのサイクルでindexを一つずらしたように入れなくてはいけない、と。
　しかし、さらにサイクル長に関して条件がありそうだとは思ったが、上手くまとまらなかった。

　実際は、同じサイクル長のものでないといけない。サイクル長3のものをサイクル長1のもので埋める……みたいなことができる気がして混乱してしまったが、こういうことができないと気付き、同じサイクル長のものしか使えないと分かった。
　なので、サイクル長で分類すればACできた。

　

G. Send GCDs

　解説AC。

・150個の素数を使うと、10^6までで1<<18個の数が作れる。
・bitごとに見るとn*20くらいの長さだが、これを18個ずつに分解すれば、上の対応表により変換できる。

　解法を聞けばまあ分かるが、これは10/9*nとか150とかいう怪しげな制約から類推するしかなさそう。推理力が問われる問題だったようだ。
　






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

2026年6月15日月曜日

第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222）

　Aしか解けず。

コンテスト後のツイート

B - Circular RPS

　解法ツイートを見てAC。

　コンテスト中は、正当性の怪しい三分探索にいってしまいダメだったし、a=0,b=cのようなケースも思いついていなかったため、全然ダメだった。

　冷静に、勝者が一人の場合、二人の場合、三人の場合について立式していったら解けた。配列から「二つの要素を選んで1ずつ減らす」という操作が何回できるか？（最大値が他の要素の和以上かによって場合分け）　という頻出問題を意識したら分かりやすい。

　ただ、a=0,b=cのようなケースは全く頭から抜けていたので、コンテスト中にACできた可能性はなさそう。

C - 2 Directions vs 4 Directions

　解法ツイートを見てAC。

　分かってしまえばなんてことはない。
　三列ずつ動く感じになるというのはコンテスト中も考えていたが、端にいかないとそこからはみ出てしまうと勘違いしてしまった。実際は、横三マスをキープしたまま、一つずつずれて上下に動ける感じになる。

　手痛い考察ミスで、そういう変な思い込みをしてしまっては修正は難しかったと思うが、もっと落ち着いて考えられていたなら正しい考察ができていたようにも思う。

　AとBをすんなり通せていたら違ったのでは？　とも思うけど、Bがすんなり通せた可能性はなさそうなので厳しい。

D - Shift and Add

　解説AC。

　下八桁くらいの数字と、その上の桁に9が何個続いているか？　を持ってDPすれば良いと思って実装を始めたが、TLEやWAが出てダメ。
　まず、下八桁ではなく九桁が必要。そして、9が何個続いているか？　ではその個数が複数あったときに計算量を減らせない。なので、「1を足したときに桁和がいくつになるか？」を持たなくてはいけなかった。

　また、桁和を求めるときは、int(str(x))を足していくのではなく、x%10を足してx//=10する、という風にした方が速い。その辺に気を配らないとTLEは取れなかった。（し、codonにしないとTLEは取れなかった）

　おおまかな解法はあっていたが、そこから実際にACするまでは遠い問題だった。

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

2026年6月13日土曜日

yukicoder contest 501

　A一完。

コンテスト後のツイート

No.3566 Subsequence Sum

　解説AC。

　そもそも通常の部分列DPでK=1の場合を解くことができなかったのは反省。
　しかし、そこを理解しても難しかった。

　まず、部分列DPでNEXTを使わずにやる方法があることを知らなかった。それを行列累乗に持ち込むためにどういうコードを書けば良いかも分かっていなかった。
　勉強になった。

No.3567 Modulo Grid

　実験して、行の数が足りていればいけそうな解法と、ギリギリでも大体大丈夫な解法を作り、組み合わせることで無理矢理ACしたが、多分Hack caseがあります……。

　とりあえず、良いペアという条件が、gcd(a,M)%gcd(b,M)==0 or gcd(b,M)%gcd(a,M)==0と表せることだけは理解しておこう。（ACしたのにそれすらよく分かっていなかった）
時刻: 0 件のコメント:
ラベル: , ,

2026年6月7日日曜日

AtCoder Beginner Contest 461

　Dまで四完で破滅。Eは一分後に通ったが。

コンテスト後のツイート

F - Total Product is N

　解法ツイートなどを参考に、Aを降順に列挙するDFSを書いたら（codonなら）通った。コンテスト中の提出（はmodの余りを取るの忘れたけど）とあまり本質的には違わないのだが。


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

2026年6月5日金曜日

AtCoder Beginner Contest 460

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

コンテスト後のツイート

F - Farthest Pair Query

　解説放送を見てAC。

　セグ木と言われても、何を乗せるか分からず、解説放送を二回見て（解説も読んで）ようやく理解。
　分かってしまえば当たり前に思えるが、全く発想になかった。
　「その頂点集合のみを見たときの、直径の端点」を乗せれば良い。


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

2026年5月28日木曜日

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

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

コンテスト後のツイート

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を使う（だろう）というヒントもある。






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

2026年5月26日火曜日

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

　Eまで。

コンテスト後のツイート

F - -1, +1

　解説放送を見てAC。

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



時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)