2026年9月16日水曜日

Codeforces Round 1121 (Div. 2)

　Dまで四完。レートが上がったが、昨日の大失敗を取り返すことはできず。

コンテスト後のツイート

E1. A Prime Flood (Easy Version)

　Aの最小値、最大値が分れば、f(A)の値は求まる、ということはコンテスト中に分かっていた。
　DP[最小値][最大値]とDPすれば、fの値を求めることができるという情報を見てAC。

　確かに、言われてみればDPできるが、コンテスト中は全く考えなかった……。
　Easy versionの制約がn<=3000である理由を追求するべきでした。



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

2026年9月15日火曜日

AtCoder Heuristic Contest 071

　187位。
　最初は焼きなましを考えていたが上手くかず。方針転換しこの解法を思い付いたときは割と筋の良い貪欲を思い付いたと思ったが、実際はイマイチでした。

コンテスト後のツイート

　上から置き方を確定させて良い、とは気付いていたのに、実際の解法に生かせなかったのがまずかったか。
　分割してDPとか、上からビームサーチなどという解法が流れてきて、確かに……という気持ちになった。



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

Codeforces Round 1120 (Div. 2)

　C1まで。
　Div. 1とDiv. 2が分かれている回でDiv. 2に出なくちゃいけないこと自体悔しいのに、そこで大失敗してしまった。

コンテスト後のツイート

C2. Floor of MEX (Hard Version)

　結局、次の問題が解ければ良い。

　自然数1,2,...,nからいくつかを選ぶ場合の数のうち、 
・[l_i,r_i]から少なくとも一つ選ぶ 
　という条件Q個を満たすものの個数を求めて下さい。

　これをO(n+Q)くらいで解ければ良い（logが付いても良い）のだが、解けなかった。

　コンテスト中は包除原理を主に考えていた。
　これらの条件のうち、満たさない個数が偶数個の個数は求まるのだろうか？　などと。この方針は筋が悪かった。

　これはもっと直接的にDPで求めることができる。

・DP[i]を、「1...iについて条件を満たし、iを選んだときの求める個数」

　とすれば良い。
　こうすると、[l_i,r_i]から少なくとも一つ選ぶという条件は、「r_iより大きいjについて考えたとき、その一つ前に選んだ数はl_i以上である」という条件に直すことができ、それを利用すると累積和を使えばDPが回る。

（なお、DP[i]=「1...iについて条件を満たす場合の数」としても答えを求めることができるが、ちょっと遷移が複雑）

　これくらいの問題は簡単に解けなくちゃいけないんだろうけど……。筋の悪い解法にハマって抜け出せなくなってしまった。
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 475

　F分からず、G間に合わずで五完。

コンテスト後のツイート

F - Rectangle Filling

　解説放送を見てAC。
　「Bounding Boxを見る」を全く思いつかなかった。色を塗る長方形で、一番上（下左右）の辺が全部#だと縮めて良い、ということには気付いていたのだが。

　F飛ばしたのは正解でしたね。

G - Has Many Divisors

　コンテスト中の方針でAC。
　最初の素数いくつかのベキを決め打ち、それ以降の素数を高々一個できるだけ使う感じでやった。
　コンテスト中は、実装ミスで、決め打った素数と一個ずつ順に使う素数の間に使わないものがでていたりしたのがひどかった。そういうミスがなかったとしてもTLEとの勝負があったから通せてたかは分からないけど、惜しかったねぇ。
　F飛ばした判断自体は間違ってなかったと思う。
　



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

2026年9月8日火曜日

AtCoder Beginner Contest 474

　F解けず六完。早めにGに行ったおかげだけど、レートが上がって嬉しい。

コンテスト後のツイート

F - Increment All Divisors

　自力AC。

　コンテスト中の方針で、判定方法を変え、三分探索にしたらACできた。
　判定方法は、「揃えたい数字との差の絶対値、の和」これが最小になるものを探した。

　凸性は示してないけれど……。
　公式解説を見ると、一次式の和であることを利用して解いている。これなら凸になりそう？（分かっていません）





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

2026年9月7日月曜日

AtCoder Regular Contest-- 229

　ACDEの四完。

コンテスト後のツイート

B - Halving Subtraction

　解説AC。

　全く考えていない方針だったのでびっくりした。
　Nが小さいからシミュレーションみたいなことをするのでは？　という方向性でしか考えられなくなった時点で負けている。
　全ての要素を0にすることは可能か？　と考えて必要条件で絞っていかなくてはいけなかったが、一旦まずい方針にハマると難しかった。

F - Angst for All Pairs 2 

　自力AC。

　実験すると、（コストが最大の）一枚を除いて他の全てのカードについて、複数毎あるか、複数枚あるものとペアか、どちらかであれば良いと分かる。
　複数毎使うカードを全探索すると、コスト計算は累積和を利用すれば計算できる。

　自分にとってはBより簡単だったけど、実験したりしてそこそこ時間かかっているから、こっちに取り掛かれば解けたという気はあまりしないねぇ。


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

2026年9月4日金曜日

AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選（AtCoder Beginner Contest 472）

　Gが解けず。

コンテスト後のツイート

G - Cascading Grid

　「燃やす埋める」だと聞いても解法が分からず、けんちょんさんが最近出した記事を読んでAC。
　が、この記事の解法通りの方法は思いつけず、グリッド中の、#でない最も左端の頂点だけを取り出し、そこから左右だけを見たときのスコアの増減を見て、その頂点同士の木構造を調べて、ようやく燃やす埋める問題に直せてACできた。

　その後、けんちょんさんの解法も理解してACしたけど、その実装にも苦戦。

　「燃やす埋める」の中では簡単な問題と書いている人もいたが、個人的には簡単に思えなかった。もっと慣れたら違うのかなぁ。
時刻: 0 件のコメント:
ラベル: , ,

2026年8月31日月曜日

AtCoder Regular Contest++ 228

　一問も解けずおしまい。しかし、Bは解けなくてはいけない問題だった。

コンテスト後のツイート


B - Minimize Topological Order

　コンテスト中の方針でAC。
　値を変更したらセグ木の更新を二ヶ所しなくてはいけないのに、一ヶ所しかしていなかったせいでした。

　最初にとりあえず一列に並べて置いて、後ろの一段を先祖のどこかへ付け替える……と考えていたのがまずかった模様。これだと正当性がよく分からないし、葉から考えるのが自然（？）にも思える。

　根から順番に木を構成すると考えれば貪欲の正当性も分かりやすかった。
　
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 473

　久しぶりの全完だが、良い順位とは言えず。

　Dは「最後の一要素を場合分け」が正当であったらしい。確かに、これをすれば無駄な探索を省けるが、こういう枝狩りみたいなのを要求されるると思っていなかったため、思いついた後も正しい解法とは思えなかった。

コンテスト後のツイート





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

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 件のコメント:
ラベル:
登録: 投稿 (Atom)