Processing math: 100%

2025年6月29日日曜日

日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）

　Eまで五完。
　久しぶりのRatedなABCだったが、レートを落とした。
　30分あってFが解けなかったのは問題だけど、Eでミラーラビンを使う方法しか思いつかなかった方が罪は大きいかも。

コンテスト後のツイート

E - LCM Sequence

　ミラーラビンを使わずにACした。

　Rの最大値が10^14であることに着目すれば、10^7までの素数を列挙し、エラトステネスの篩のようなことを行うことで、区間[L, R]での素数を見つけることができる。
　ミラーラビンを使わずに解けるんじゃないの？　とは思ったし、Rの最大値に着目した時間もあったはずなのに、どうして思いつかなかったんだろう。これをさっと通せていたらFも解けていた気がするなぁ。

F - Socks 4

　自力AC。

　ソックスの個数が多いものが出たらそっちへ移動する方がいいのは明らかで、あとはいつもの期待値DPの式を立てるだけ。
　結構すんなり立式でき、Sample1の値があったから実装し始めたのだけど、結局間に合わなかった。

　もっと一般的な形で立式していれば実装で詰まらなかっただろう……とはいえるけど、Sample１と一般の形でそれほど違いはないので、残り時間を考えればここで実装を始めたのは悪くなかったはず。
　なので、ここをこうすれば良かったという点はあまりなくて、期待値DPの立式や実装が遅かったことを敗因として良さそう。

　Fに時間を残せなかったのが不味かった。




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

2025年6月27日金曜日

AtCoder Beginner Contest 408

　Fまで。

コンテスト後のツイート

G - A/B < p/q < C/D

　解説AC。

　公式解説の方法は賢いが、Stern–Brocot木は知っていたのだが、それを使って解くことはできるべきだったのかもしれない。（ただし、今回Stern–Brocot木を使う解法ではACしてない）


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

2025年6月25日水曜日

Educational Codeforces Round 180 (Rated for Div. 2)

　Dまで。
　Bは難しい方法で解いてしまったが、単調増加や単調減少だとダメだけど、そうでなければ一回、という簡単な解法があった。単調増加or単調減少じゃないなら、山や谷の箇所があるので、確かに、という感じだが、気付かなかった。

コンテスト後のツイート

E. Tree Colorings

　根以外で枝分かれのない木の場合はコンテスト中にできていて、その場合は、素因数分解して、x*y*zなら、1+x/2+y/2+z/2みたいに求まる。
　それを応用して解こうと思ったが、結構苦労してしまった。

 木を、根からではなく、葉から作っていこう、と考えると良い。

・木Aと木Bを根同士を合わせる形で合体させると、node数はその和-1で、mの値はその積のような木になる。
・木に親をつけると、mの値は+2する。

　この二つの遷移でDPすればOKでした。



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

2025年6月23日月曜日

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

　ABの二完で青に落ちる。Dの解法は分かっていたのに実装できず。最近、実装力が落ちているのかも。まずいなぁ。

コンテスト後のツイート

C - Prefix Covering

　Trie木、木DPというキーワードを見てAC。

　コンテスト中は、Trieを使うのだろうとは思ったが、数え上げ方が分からなかったため飛ばした。
　しかし、木DPだと言われたらすぐ解答が思いつけたのだから、もう少し粘るべきだったかもしれない。とはいえ、考えていたときに木DPは浮かんでいなかったので、本当に解けたかは分からない。

D - Match, Mod, Minimize

　WAの原因は、累積和用のLISTを円環用に2*Nの長さにしていたのに、累積和を取るときNまでしかしていなかったせいだった。
　ちゃんと累積和取ったらWAはなくなってTLEになり（二分探索中に二分探索してるので仕方ない）、RUSTに直したらAC。
　その後、尺取りに直してPyPyでもAC。

　しかし、bisect→尺取りに直すのでも3WAしておりまずい。

　実装力というか注意力みたいなのが落ちているのかも。それってどう対策したら良いんだろう？






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

2025年6月22日日曜日

ユニークビジョンプログラミングコンテスト2025 夏（AtCoder Beginner Contest 411）

　Eまで五完。

コンテスト後のツイート

F - Contraction

　自力AC。

　コンテスト後の冷静な状態ならすぐ分かるだろうと愚直書かずにやろうとしたらペナ量産。一時間くらいして諦めて愚直＆ランダムテストを書いたらようやく分かってAC。消すべき辺を消していないところがあったためのWA（やRE）でした。

　愚直を書いた方が速く解ける場面が多いのはそうだけど、これくらいの問題で愚直を書くのも……という気持ちも間違ってないと思うので、どうしたら良いのかね。

G - Count Cycles

　一応自力ACだが、bit DPでいける……みたいなツイートは目にしていた。

　素直にbit DPを書くとN^3 * 2^Nくらいの計算量になるが、定数倍高速化をしていればなぜか通る。ただし、自分の場合はPyPyでは通らず、RUSTに直さなくてはいけなかった。

　が、これは、start位置を固定してそれぞれでbit DPを行っていると考えられるためで、そう考えると実は（ならし）計算量が減っている（解説を見て理解）。
　その方針ならPyPyでもACできた。



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

2025年6月21日土曜日

yukicoder contest 471

　A一完。
　AtCoder 創立13周年記念 企業対抗 Team Battleの放送を見ながら考えていたらBが思いつけず、疲れてそのまま撤退。


No.3184 Make Same

　解法ツイートを見てAC。

　クエリの30回ってbitの長さくらいだね、とは思ったはずなのに、思いつけなかったのはダメ。

No.3185 Three Abs

　自力AC。
　いわゆる耳DPですね。これはすんなり解けました。

No.3187 Mingle


　もらうDPで二乗になるのを配るDPにすると区間加算になるとは気付けなかった。
　さらに、どのような区間になるのか？　という部分でも結構困った。実験したり、式を書いたりしてなんとか理解し、AC。
　実装には双対セグ木を使いました。

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

2025年6月20日金曜日

Codeforces Round 1032 (Div. 3)

　Fまで六完。Div. 3で二問解けないのはまずい。

コンテスト後のツイート

G. Gangsta

　解説AC。典型かもしれないけど難しく感じた。

　まず、0と1の個数のうち多い方、というのを

・((0の個数)+(1の個数)+(0の個数と1の個数の差))/2

　と言い換える。

　そうすると、あとは、全ての区間について、(0の個数と1の個数の差)の総和を求めれば良い。

　このために、"1"を+1、"0"を-1とした累積和を考える。この、任意の二項の差の絶対値を求めれば良い。
　ここでBITを使って、BITに個数や総和を載せて解く方法もあるようだ（よく分かっていない）。

　が、公式解説はもっと簡単。
　累積和の配列をAとし、Aをソートする。
　二項の差の絶対値を考えるということは、自分より大きい項からは引かれ、小さい項については足されるということ。
なので、

・A[i]*(i-(len(A)-1-i))

　の和を求めれば良い。

　前半も後半も見たことあるような内容ではあるが、とはいえこの二つを繋げるのは結構難しい気がする。

　




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

2025年6月18日水曜日

CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)

　Fまで。

　Fはうまくやればdictは必要なかった。どの数字が何個あるかを配列に記録し、差分計算すれば良かった。PyPyで通せなかったのには理由がありました。

　ただ、思いつくべき内容ではあったが、個人的にはこういうlog外しはあまり重要に思えないのよね。AHCで焼きなましの回数を増やしたい！　とかなるとこういうことも重要になってくるけども。しかしそれも、高速な言語に書き換えた上での話な気もする。

コンテスト後のツイート

G - Longest Chord Chain

　解説放送を見てAC。解説を見てしまったけど、多分時間があれば自力で解けたと思う。

　[a,b]と[c,d]の区間が交わらないような最長のものを求める感じなのは分かるが、円環の問題なので、どこかで切り分けなくてはいけないのが難しい。

　これを、[a,b]だけでなく、[b,a+2*N]も考えることで、ただのLIS（今回は、最長減少部分列の方だが）を求める問題になるというのは驚き。こうすると実装しやすいね。



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

2025年6月16日月曜日

AtCoder Regular Contest 200 (Div. 2)

　ABの二完。若干レートは下がったが、それほど失敗したという感覚はないため厳しい。Aは、最初から紙で立式すべきだったかなぁ。

コンテスト後のツイート

C - Movie Theater

　後ろから決めていけばいい、というツイートを見てAC。

　どこでWAになっているかの判断を誤っていたのがダメだった。今回は、人の順番の配列を求めた後、その逆写像が答えになるわけだけど、「人の順番の配列」の辞書順最小を求めても、その逆写像が辞書順最小にはならない。
　ここに気付かず、もっと別の条件の部分で間違っていると思ってしまってダメだった。

　逆写像を辞書順最小にするためには、後ろから決めていけばよい。
　このことは知らなかったけれど、この部分が間違っていると気付けたら試したと思う。

D - |A + A|

　自力AC。

　コンテスト中に書いた実験コードを利用してAC。
　コンテスト中は実験しても偶数のときの構築が分からなかったのだけど、落ち着いて実験結果を見たら、6以上なら、0, 1, 2, 4のように、0から連続する数＋一つ飛ばしでできていた。
　2は、偶数のときは0とM/2で良い。（奇数だとダメ）
　4のときでWAを出してしまったが、2のときと同じように、Mが4の倍数なら0, M/4, M/2で作れる。

　コンテスト中は、Dを20分くらい考えた後、分からなそうと思ってCに行ったのだが、その判断はどうだったんだろう。
　一応、今考えてACするまで30分はかかっていない気がするが、コンテスト後に落ち着いて
実験結果を眺められたからという気もするし、WAの修正に12分もかかっている。

　Dに集中していたら解けた可能性がなかったとは思わないけど、望み薄だったかなぁ。
時刻: 0 件のコメント:
ラベル:

2025年6月14日土曜日

yukicoder contest 470

　Cまで三完。


No.3180 angles sum

　tangentの加法定理を使って書いたら1case（コンテスト後追加されたHackのcase）以外AC。y座標が0の場合が問題なため、場合分けしてAC。

　コンテスト中は、ベクトルの内積でcosを求め、加法定理を使って式変形をしていたが、答えが合わなかった。誤差のせいなのか式変形がまずいの分からず困っていたら終了。
　tangentの加法定理でも解けるだろう、ということはコンテスト中から気付いていて、そっちで式を書いてみるとその方が簡単だった。

　ただ、どっちの方法でも解けるはずなので、早く方針転換すべきだった、というのも違うような。

No.3181 find H

　三角形の五心について、何かと何かの距離が1:2になるというのは覚えていたが、どれとどれかが覚えておらず検索した。
　知識問題ですね。

No.3182 recurrence relation’s intersection sum

　解説AC。

　解説を読むと行列累乗の典型問題なので、自力で解けなかったのが悔やまれる。
　行列累乗に持ち込むため、A_nやS_nだけではなく、1やn, n^2といったもの（関数）を行列の要素に入れるという手法は見たことあったはずなのに思い出せなかった。
時刻: 0 件のコメント:
ラベル: ,

2025年6月10日火曜日

yukicoder contest 469

　AHCの途中だったため、Aだけ解いた。

コンテストへのリンク

No.3172 三角関数べき乗のフーリエ級数展開

　何も分からなかったので、サンプルからOEISを経由してAC。
　まあ、二項係数じゃないか？　とは思ったので、OEISを見なくてもACできたかもしれないけど。
　自力で解答にたどりつけたかもしれないけど、式変形して正解を得られる気がしない。

No.3173 じゃんけんの勝ちの回数

　ツイッターで、フローで解けるというのを見てしまったため、それでAC。（minだけフローを使った）
　解説を見たら、フローを使わなくても解けるのね。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~

　AHCを頑張ろうと思っていたのでAだけAC。


No.3166 [Cherry 7th Tune *] 桜の守人

　解説AC。

　二分探索は分かったが、その後分からなくなり解説を見た。

　分からなくなってしまったのは、全ての整数座標、もしくは整数/2の座標の頂点が守られているか？　と考えてしまったせいだった。座標圧縮が必要なはずだけど……などと考えて混乱。
　守る範囲は区間なのだから、[x-p,x+p]に全ての区間が含まれているか？　と考えるのは自然。これは、イベントソートを使って解くことができる。

No.3167 [Cherry 7th Tune C] Cut in Queue

　自力AC。そこそこ苦労したが解けて良かった。

　クエリ先読みを使い、クエリ2の削除しないものとして、最終的なAの配列を求める。
　クエリ1で、何の直前に何が付け加わるか？　というのが与えられている。これをなぞるのは、木構造でDFSして求めていく感じになる。

　あとは、Bit_indexed_tree上の二分探索を駆使したら解けた。

No.3168 [Cherry 7th Tune D] Manhole

　自力AC。

　図を描いて相似を見つけたら解けた。空間図形には苦手意識があるため、図を描いた後しばらく分からなくて焦った。
時刻: 0 件のコメント:
ラベル:

2025年5月28日水曜日

Codeforces Round 1027 (Div. 3)

　全完。若干遅刻したのに良い順位で嬉しい。

コンテスト後のツイート


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

2025年5月27日火曜日

AtCoder Beginner Contest 407（Promotion of AtCoderJobs）

　ABCDFの五完。コンテスト終了後すぐにGは通った。

コンテスト後のツイート

E - Most Valuable Parentheses

　解説AC。
　結構思いつきにくいと思う。

　別の方針からこの解法へ行きつくこともできるようだけど、
　「index iまでのうち"("は少なくとも何個含まれるか？」という考え方は身に着けておきたい。
　括弧列の定石の一つなのだろうけど、身に着いていなかった。

G - Domino Covering SUM

　自力AC。
　これは焦っていなければコンテスト中に通せていたはず。落ち着こう。
時刻: 0 件のコメント:
ラベル: ,

2025年5月26日月曜日

AtCoder Regular Contest 198 (Div. 2)

　Bまで二完。レートが落ちたが黄色には残った。

コンテスト後のツイート

C - Error Swap

　自力AC。惜しいようで惜しくなかった。

　大まかな考察は合っていたけど、詰めなくてはいけない箇所が残っていた。

　左端から揃えていく、という解法でやった。index iを揃えようとするとき、B[i]+1に一番近いA[k]を探して、A[k]が小さいなら左回り、大きいなら右回りに回転させて、B[i]+1になったらクエリ(i,j)を投げる、という方法でやっていた。

　だが、A[i]=B[i]+1となったときに(i,i)と投げられないのが問題だった。(i,N),(N-1,N)とすれば(i,N-1)とできるのだが。ここに気付いていなかった。

　ここを修正してAC。
　あと20分くらいは必要だったか。

D - Many Palindromes on Tree

　自力ACはしたが大変だった。

　問題の内容を理解するのがちょっと大変だが、理解できれば解法そのものは難しくない。(i, j)間の距離が大きいペアから、A[i][j]=1なら、一つ近づけて(i', j')も1にし、Union-findでくっつける、という操作をする。
　その上で、今度はその逆順で答えを構成していく。

　しかし、この順番を構成する部分（上の(i', j')に対して、(i, j)が何かを前計算したりする）の実装で苦戦。さらに、ちゃんと実装してもMLEになり、PyPyでは通せなかった。二次元配列にしていたり、tupleで実装しているのを整数化したりすれば解消されるのかもしれないが……。
　RUSTに直してもらいAC。今回は、Gemini Canvasを使ってみたら、一発だった。
時刻: 0 件のコメント:
ラベル:

2025年5月19日月曜日

Codeforces Round 1025 (Div. 2)

　C1までの三完。C2を考えていたら寝てしまった。


C. Hacking Numbers 

　こたつがめさんの放送の振り返りを見てAC。
　こんなの思いつかない。初手で掛け算すること自体を考えなかったので厳しい。

D. D/D/D

　自力AC。
　偶奇に分けて、最大何歩歩けるか？　各マスまで最小で何歩でいけるか？　を求めればOK。
時刻: 0 件のコメント:
ラベル:

2025年5月17日土曜日

yukicoder contest 467

　ABCEの四完。Dは、問題の意味がぱっと理解できなかったから飛ばしたけど、分かっても難しかった。


No.3143 Colorless Green Parentheses Sleep Furiously

　WAが出た後、テストケースを見てAC。

　カッコ列が正しくなければダメ、というのはOK。その上で、
　できるだけ少ない個数の1を加えたとき、何個加えることになるかを知りたい。

　()なら、(1+1)+1にしなくてはいけないが、
　()()なら(1+1)+(1+1)で良い。

　(())なら、((1+1)+1)+1にしなくてはいけないが、
　(()())なら、((1+1)+(1+1))にする。

　カッコ列の対応を考えて、その対象範囲に自分のカッコだけしかないときは、()+1としなければならない、というのがなかなか気付きにくいポイント。

　実装では、最初に、どの"("がどの")"と対応しているかindexの対応を調べておき、((...))となっているようなら、後ろか前かに+1を置けば良い。

No.3145 Astral Parentheses Sequence

　解説AC。難しい。

　括弧列の個数（カタラン数）をDPで求める方法を応用するとこの問題のDPも導ける。ただ、括弧列の個数を求めるDPがそれほど明らかではないため、それと似た方法でこれもいけるというのは直感的に分かりづらい。

No.3146 RE: Parentheses Counting

　解説AC。難しい。

　解説の最初にある漸化式（三乗の計算量になるやつ）を自力で出そうとしていたが、それすらできなかった。
　ネストの深さが0の部分がカタラン数の積になるっていうところが思いつかない。ここは主客転倒で考えているのか。
　その後の、計算量削減の式変形も難しい。カタラン数が満たす漸化式を知っていればいけるかもしれないが。

　自力で解くには、実験→oeisしかなかった気がする。

No.3147 Parentheses Modification and Rotation (RM Ver.)

　解説AC。

　解説を見てしまったけど、これは自力で解けて良かった。括弧列の累積和（いつものやつ）を使い、最大値・最小値から答えが導ける。
　タイプ1が右回転なのがちょっと引っ掛けな気がした。S[1:]+S[0]だった方が直感的に分かりやすい。

No.3148 Min-Cost Destruction of Parentheses

　01 on Treeの類題ということはツイートで知っていたのに、大分時間がかかってしまった。この自分のコードなどを参考にしてどうにかAC。
　当時のコードはちょっと不思議なことをしていた。大体同じだけど、今のコードの方が自然な気がする。

　括弧列から木を作るパートはスタックで行えば良い（参考）。この部分で詰まらないようにしたい。
時刻: 0 件のコメント:
ラベル: ,

2025年5月15日木曜日

AtCoder Regular Contest 197 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E - Four Square Tiles

　解説AC。

　二項係数でどうにかするのでは？　という気持ちになるのが大切だったか？　中央の重なりがない場合については、そういう気持ちになれば求められたと思う。

　しかし、中央に重なりがある場合も、それと独立に、二項係数で表せると気付くのは難しかったと思う。
　ただ、中央に重なりがない場合が二項係数で表せたなら、正しい答えも二項係数の足し引きで表せるのでは？　と思って実験し、正しい答へ辿り着けた可能性はあるか。
時刻: 0 件のコメント:
ラベル:

2025年5月14日水曜日

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

　Fまで。

コンテスト後のツイート

G - Range Shuffle Query

　ACできなかったのは仕方ないが、Mo＋セグ木の解法は自力で思いつかなくてはいけなかった。

　平方分割するとセグ木を使うより計算量が良くなることは知らなかった。頭に入れておきたい。

　ところで、Moを書くときは、区間を広げた後、縮めていくように書くべきだということも知らなかった。今回、PyPyでTLEを取ることができず、ChatGPTにRUSTに直してもらったのだが、それが原因で配列外参照が起こってしまった。原因が分からず大分苦労した。
時刻: 0 件のコメント:
ラベル: ,

2025年5月13日火曜日

Codeforces Round 1024 (Div. 1)

　ABDの三完。

コンテスト後のツイート

C. 23 Kingdom

　解説を見たがそのままは理解できず。

　使う個数xを固定した場合、「x,x-1,...,1の順に、できるだけ左にあるものを貪欲に使う」「x,x-1,...,1の順に、できるだけ右にあるものを貪欲に使う」として取ったものを合わせれば良いことは分かった。

　それを三分探索すればACできるというコメントを見て、AC。PyPyじゃ間に合わないので、ChatGPTにRUSTに直してもらった。

　もっと良い方法があるようだが理解できていない。




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

2025年5月7日水曜日

AtCoder Beginner Contest 404（Promotion for Engineer Guild）

　Eまで五完。

コンテスト後のツイート

F - Lost and Pound

　解説AC。解説放送も見た。

　分割数全部調べる方法は理解できたけれど、DP内でDPする方法の方が理解できず苦戦した。

　結局自分で（再帰で）書いて見たらACコードは書けたけど、かなり難しく感じた。

　残りターンT回、残り押さなくてはいけない回数K回のときの勝率をcalc(T,K)、とし、
（残りターンT回のとき）残りボタンを押す回数M回、kai回押す場所を決め、残り押さなくてはいけない回数x回のときの勝率をcalc2(M,kai,x)という関数を定義し、計算した。

　引っ掛かっていたのは、kaiという変数が必要なこと。
　kai回当たらなかった場合、当たりのボタンはN-kai個の中に含まれるので、当たりの確率は上がっているはず。

　解説や解説放送のDPではこれをどう処理しているのかが分からなかったので、必要ないのか？　と思ったけど、やっぱり必要でした。
　snukeさんのコードだと、26行目に(n-i)を掛けているのがそれに当たるんですね。

　再帰だと（多分）同等なコードが書けるけど、このDPを書くのは難しい……。確率DPは再帰じゃないと書けないかもしれない。

　

G - Specified Range Sums

　解説放送を見てAC。

　牛ゲーは、解説を見れば理解できるけど自力で構成するのは難しい。
　牛ゲーじゃないかと思ったときは、けんちょんさんのこの記事を見るのが良いかもしれない。


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

2025年5月3日土曜日

yukicoder contest 466 オムニバスコンテスト

　ABDの三完。


No.3134 二分探索木

　自力AC。コンテスト中は思いつかなかった。

　二分探索木を構築する部分が難しい。
　単純な方針だとできなそうに思えたため、SortedSetを使う方針を考えたら上手くいった。

　使ってなさそうな提出もあるけど、大抵の提出では使ってそうだし、まあ良いかな（？）

　※逆順列のCartesianTreeを作ると良いらしいです。

No.3137 Non-Intersect Chord Triangle Game

　解説AC。
　葵ちゃんの行動を誤読していたのでそもそもダメだが、正しく捉えていたとしても解けたとは思えない。

　小さく、かつ弦のない円で実験したとき、2頂点、6頂点で茜ちゃんが勝つ、と正しく把握できたら考察を進められそう。




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

2025年4月29日火曜日

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

　Fまで六完。

コンテスト後のツイート

G - Odd Position Sum Query

　解説放送を見てAC。

　この前のこたつがめさんの解説放送で、セグメント木≒Binary Trieだという話を聞いていた。知識はあったので解けなくてはいけない問題だった。

　ただ、そもそも、値が小さければ普通のセグメント木で解ける、ってこと自体思いついてなかったんだよね……。



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

BrainPad プログラミングコンテスト 2025 （AtCoder Heuristic Contest 046）

　384位。終了間際の提出がTLEになってしまい悲しい。

コンテスト後のツイート

　コンテスト中考えていた提出でバグがなかったら81位相当だった。

　惜しかったようで惜しくなかったのでは、考えていた方針はそれほど悪くなかったと慰めたい。






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

2025年4月26日土曜日

yukicoder contest 465

　Eまで。


No.3129 Multiple of Twin Subarray

　自力AC。コンテスト後に自力で解けたけど、大分時間がかかった。

　左右から、累積和の差分が最大・最小になるような値を見つけられれば良い。これは、左右から累積和を取り、さらに今の累積和の値とそれまでの累積和のminの差分を取り、そのmaxを取っていき……のようにやればできる。

　最初、切れ目を全探索を考えて上手くいかず悩んでしまった。
時刻: 0 件のコメント:
ラベル:

2025年4月25日金曜日

CPCTF2025

　81位でした。
　「CTF」初体験だったので、CTF中心にやったつもり。LV1は一応全部解いたけど、LV2から苦戦する問題が多くて大変でした。

　競技プログラミングがパズルっぽいとすれば、CTFは謎解きっぽい印象。
　面白いとは思うけど、自分は謎解きよりはパズルの方が好きかつ得意だと思うので、もしCTFを解くために必要な基本技術を習得したとしてもそんなに上手くはなれないだろうな、と感じました。
　まあ、もう少し勉強してみないとなんとも言えないだろうけど。

コンテスト後のツイート

　以下は、yukicoderの問題について書きます。

No.3117 Reversible Tile

　解説AC。これが解けないのはダメ。

　こういう区間をひっくり返すやつは、0と1の切れ目が二個変わる、と考えるのが定石。制約を見ると、二乗DPということが分かるので……というところで詰まってしまった。

　ここまでの考察は合っているのに、なぜ解法にたどりつけないのか。

　今回は、「切れ目の値が入れ替わっている個数」を持ってDPすれば良い。なぜかそう思いつけなかった。

No.3119 A Little Cheat

　解説AC。
　swapによって増大する分と、通常の値を分けるというのは考えたけど、swapによる増大分が高々1と気付かなかったし、それをDPで求められるというのも分からなかった。

　また、解説を理解した後も、DPの遷移（場合分け）が大変過ぎて実装が大変過ぎるのでは、と感じた。実際に場合分けしてみると遷移に共通する部分が多い（コピペで良い部分が多い）ためそこまで大変ではなかったが、とはいえ、こういうのをさくっと実装するにはどうすれば良いのかなぁ。

No.3120 Lower Nim

　自力AC。

　最初にx=1を選択するとすると、Aの総和が奇数だと先手必勝。
　なら、最初にx=2を選択するとすると、A[i]/2の総和が奇数だと先手必勝。
　なら、最初にx=4を選択するとすると、A[i]/4の総和が奇数だと先手必勝……というようになることを利用した。

No.3121 Prime Dance

　自力AC。

　メモリ制限が大変だけど、難しいという気はあまりしなかった。
　……と思ったら、メモリ制限が大変だったのは、左に操作した回数、下に操作した回数を持ったせいか。
　自分は、DP[left, down, x ,y]で、左にleft回、下にdown回操作して(x, y)に辿り着いたか？　をboolで持ってやったけど、もう少しメモリを減らせたんですね。
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 400

　Eまで。

コンテスト後のツイート

F - Happy Birthday! 3

　解説AC。解説放送やこたつがめさんの放送の振り返りも参考にした。

　区間DPなのは良いが遷移が難しい。四乗にする時点でかなり難しくないか？

　こたつがめさんにやると、計算量削減部分は「区間DPの遷移でDPする必要があるとき」という典型らしい。l降順、r昇順にDPを計算していく。

　しかし、そのパートにたどりつくためには遷移を把握できていなくてはいけないのが厳しい。ただ、こういう典型があると知っていれば、どういう遷移かを掴める確率は上がるはず（と信じたい）。
時刻: 0 件のコメント:
ラベル: ,

2025年4月18日金曜日

Kotlin Heroes: Episode 12

　Eまで。

コンテスト後のツイート

F. Weapon Upgrade

　三乗で良いというツイートを見てAC。難しくない。

　残り時間が少なかったのでACまでもっていくのは厳しかったかもしれないが、方針は立っているべきだった。

　a, bをそのときのそれぞれのパワー値とし、DP[a][b]=そのときのダメージ量の最小値として更新していけば良い。(a, b)が分かれば、そのときまでに倒した敵の数が分かる。なのであとは、(a, b)のときに倒せる敵の個数さえ分かれば良いが、これは、毎回500*500のマップを更新していけば良い。

　敵が出尽くした後も、さらにn回くらいDP更新作業を続ければ答えが得られる。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 1017 (Div. 4)

　全完。
　Hの方針が若干自信なかったけど、通って良かった。

コンテスト後のツイート






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

AtCoder Beginner Contest 401

　全完でした。

　調べてみたら、ABC全完はABC197以来だったらしい。四年ぶり！
　当時のABCは六問時代だった！

　最近も何度か簡単なABCはあったけど、いつも全完を逃していたからね。
　嬉しいけど、自分の実力で全完できるくらいのABCはちゃんと全完できるようになりたいね。

コンテスト後のツイート





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

2025年4月12日土曜日

yukicoder contest 464

　ABの二完。


No.3101 Range Eratosthenes Query

　解説AC。これが見えなかったのは良くない。

　たとえば、[L,R]中にあるx=20を食べるかどうか考えるとき、xの1でない一番小さい約数は2なので、20/2=10が[L,R]中に存在するかどうか、で判定できる。Lが10以下か10以上かで変化する。
　このことに気付いていなかった。

　これが分かれば、クエリを先読みし、Lの順にソートして見ていけば解くことができる。

No.3102 floor sqrt xor

　解説AC。

　x^√xを考えると、上半分の桁はxのままなことを利用できそう。xを動かすとまずいけど、√xを固定すると、ルートして切り捨てた値が√xになるような範囲が分かるので、それで調べられる。

　……というようなことを考えたはずなのに、実装する段階になると分からなくなってTLEの解法を書いてしまい、解説を見て考察していた内容を思い出した。

　ちょっとあやふやなところはあったけど本質的解法は一度自力で考察したはずなので、時間があれば解けていたと信じたい。

No.3103 Butterfly Effect

　自力AC。

　その人がはじめて噂を知った時刻を持って、毎回ダイクストラすれば良いように見えるが、それだとTLE。
　同じ辺は二度通らないように見えるため、なぜTLEするのかしばらく気付けなかった。

　なぜTLEするかというと、ある人から辺（AさんとBさんの噂話）がたくさん出ているとき、（伝播しないのに）それらの辺を何度も見ることがあるため。

　じゃあ、「同じ辺は二度通らない」という性質があるのなら、辺もheapqで持ち、一度通った辺は削除すれば良い、と気付きAC。

　「ダイクストラで解けそう」という方針自体は思いつきやすいけれど、ちゃんとそこから一捻りしてあった。

　

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

2025年4月11日金曜日

AtCoder Grand Contest 071

　A一完。

コンテスト後のツイート

C - Orientable as Desired

　解説AC。解説放送も見た。

　全く惜しくはなかったが、サイクルがあってもYesになる条件を考える、という方針自体は良いのかも。そういうグラフを列挙していけば正しい条件にたどりつけるかもしれない。

　ただ、解法を理解した後も、二重頂点連結成分分解を実装したことがなかったため、自力で実装できなかった。LOWLINKを使った関節点や橋は実装したことがあるので、あと一歩なはずなのだが……。

　とりあえず、二重頂点連結成分分解をChat-GPTに実装してもらいAC。原理は理解したつもりだけど、実装がよく分かっていない。ちゃんと自力で実装しなきゃなぁ。



　ついでに、二重頂点連結成分分解を調べる仮定ででてきたこの問題も解説（放送）ACした。ポリアの数え上げ定理（バーンサイドの補題）はこういうときに使うのか。数え上げパートまでいけたとしても解けなかったと思うので、そこまでいけたら解けるようになりたい。



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

2025年4月3日木曜日

April Fools Day Contest 2025

　ADの二完。


B. Plinko

　自力では解けず。
　0～17におくとゲームをプレイしなくてはいけないが、その外側におけば良かった。これは思いつきたかった。

C. Would It Be Unrated?

　解説AC。
　一つACが出るまでできることがなくないか？

D. Where Am I?

　写真を検索するとラスベガスだと分かるので、その緯度と経度を書く問題。それっぽい提出をしても「very close!」などと返ってきて、submitデバッグするしかなかった。
　……が、もっと狭い範囲に絞れたらしい。

E. Pair Count

　解説AC。リンクがあればそこを押す、ということさえしていれば、順を追って解ける問題でした。

　エイプリルフール部分の後にもk=0というコーナーがあるのも面白い。


G. Definitely a Geometry Problem

　解説AC。
　制約に引っ掛けがあるだけで普通の（注意力を要する）問題だった。問題文は丁寧に読まないとね。
時刻: 0 件のコメント:
ラベル:

2025年3月30日日曜日

AtCoder Beginner Contest 399

 　Eまで。

コンテスト後のツイート

F - Range Power Sum

　解説AC。

　「積の和典型」とも呼ばれる、組み合わせに帰着して解く問題。この解法、何度見ても解けるようにならないのだが……。
　コンテスト中に「積の和典型」で検索したのに解けておらず、辛い。





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

yukicoder contest 462

　AHCがあるのでAだけ解いて撤退した。


No.3075 Mex Recurrence Formula

　自力AC。

　実験するとN+1周期になると分かった。MEXを求めるところを愚直にやってしまったためTLEしたが、heapqを使えば良いと気付きAC。

No.3076 Goodstuff Deck Builder

　自力AC。これは迷わなかった。

　コストが大きい方から使うのが良い。残りのコストと、カードを使った回数をもってDPすればOK。
時刻: 0 件のコメント:
ラベル:

2025年3月27日木曜日

Codeforces Round 1013 (Div. 3)

　全完。
　Div. 3も最近は全完を逃していたことが多いので、今回は全完できて良かった。

コンテスト後のツイート

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

2025年3月24日月曜日

AtCoder Regular Contest 195 (Div. 2)

　三完はしたがレートは落ちた。Bは同じ解法で通している人を何人か見かけた。

コンテスト後のツイート

B - Uniform Sum

　嘘だと思ったが、（嘘かもしれないけど）それほど嘘ではなかった。

　A, Bがdistinctだとすると、S=A[i]+B[j]が何個ずつ現れるかをカウントすれば、それを見るだけで判定できる。
　今回はdistinctじゃないのでもう一工夫必要だが、大体それで良かった。

　distinctなら上手くできるのでは？　と考えるべきでした。

D - Swap and Erase

　解説AC。

　コンテスト中に考えていた貪欲（左から見ていき、A[0]==A[2]ならA[1]とA[2]をswapする）がどういうときまずいのか気付けなかったのが敗因。

　たとえば、

・1 2 1 1 1

　のときまずかった。A[0]とA[1]をswapしなくてはいけないときもある。

　Aの各要素が高々一回しかswapされないというのは言われてみれば自然だし、貪欲でダメと分かればDPしようと思えた可能性はあるかもしれない。

E - Random Tree Distance

　解説AC。解説放送も見た。

　まず、lcaを考える（u,vの距離を、D[u]+D[v]-2*D[lca]とする。D[x]は1からxまでの距離です）のはすべきだった。lcaがどこにあるか分からないから、lcaを考えることで状況が良くなるとすぐには思えないけれど、これはまずして良いですね。

　あとは、D[lca(u,v)]が、u<vのときvの値によらないと気付けるか、だが、これは実験していれば気付けるかもしれない。しかし、その後、D[lca]に関する漸化式を立てる部分が理解できず、解説を見ながら悩んでしまった。lcaが再帰的に決まっていく、と考えれば難しい式ではないのだが……。

　発想があった方が良い部分（D[lca(u,v)]が、u<vのときvの値によらないと気付く部分）もあるけれど、それ以外の定石的な部分でも詰まっているので、その部分はどうにかしたい。
　
時刻: 0 件のコメント:
ラベル:

2025年3月23日日曜日

AtCoder Heuristic Contest 044

　98位。

　コンテスト中バグらせて書き終わらなかった方針を最後まで書いていれば30位くらいにはなったので、惜しかったといえば惜しかった。

コンテスト後のツイート




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

Codeforces Round 1011 (Div. 2)

　Cまで三完というまずい成績。

コンテスト後のツイート

D. Serval and Kaitenzushi Buffet

　解説AC。
　heapqを使って上手くやる問題だと見てすぐ思い、それはあっていたのだが……。

　後ろから見てheapqで、それまでで最も良いのを出していく感じだと考えてしまったが、これだと上手くいかない。

　寿司を取る回数の最大回数が決まり、その回数だけ取るべき、というのが重要。そうすると、一回目、二回目……について、どの範囲の寿司から取れるかが定まり、heapqで答えを求めることができる。

　各回について、どの範囲の寿司を取ることができるかと考えなくてはいけなかった。愚直解（DP）と比較し、自分の解法がどういうケースで落ちるかも分かったのだけど、答えにたどりつけず。こういうときはどうすれば良いのだろうか……。

E. Serval and Modulo

　解法ツイートを見てAC。
　kはsum(A)-sum(B)の約数になる。言われてみれば確かに……。



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

2025年3月22日土曜日

yukicoder contest 461

　EHJの三問が解けず。

コンテスト後のツイート

No.3068 Speedrun (Hard)

　解説AC。

　二つ固定すれば、残り二変数については連立方程式になり、解ける。気付かなかったのはまずい。

No.3071 Double Speedrun

　自力AC。

　斜め向きにDPしていけば良い。ちょっと雑に書いたらPyPyで間に合わず、ChatGPTにRUSTに直してもらいAC。

No.3073 Fraction Median

　解説AC。気付けなかったのは悔しい。

　「中央値」というのを見て二分探索でどうにかしようとしてしまったが、それだと上手くいかない。よく問題を見ると、x/yとy/xの両方が含まれるので、この中央値は大体1。つまり、1以下で最大の数を求めれば良いと分かる。





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

2025年3月15日土曜日

yukicoder contest 460

　11ペナを経てA一完。


No.3056 Disconnected Coloring

　1の周り、もしくは、Nの周りだけ青にすれば良いだろう、という方針はすぐに立ったが、そこからが長かった。
　どういう場面でWAになるか分からず、submitデバッグも経てなんとかAC。

No.3057 Tree Distance Set

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

　2頂点の間に辺がある状況から、もう一点、それらから等しい距離Dの頂点を作りたいなら、その辺の中央に頂点を作り、そこから辺を伸ばして、新たな点を加える（そして、それのみSに加える）とすれば良い。
　そうして作った木は、「2頂点の間に辺がある状況」を維持しているのでその後も再帰的に作れる。

No.3058 Deque and Brackets

　解説AC。

　hamamuさんの解説ツイートが分かりやすかった。
　分かってしまえば難しくない問題なはずなのに、「後ろから見る」というキーワードを見ても自力で解けなかった。

　こういう貪欲系は、調子いいと解けたりするんだけど、安定させるにはどうしたらいいのかなぁ。
　
時刻: 0 件のコメント:
ラベル: ,

2025年3月13日木曜日

Codeforces Round 1009 (Div. 3)

　Fまで。D以降どれも難しい印象。
　と思っていたら、Fはシステムテストで落ちた。

コンテスト後のツイート


F. Counting Necessary Nodes

　ちゃんとメモ化してAC。
　tupleでメモ化しようなどとしたのが浅慮でした。ちゃんと整数でメモ化したら通った。

G. Game With Triangles: Season 2

　区間DPなのは良いけれど、円環だということを意識する必要はなく、シンプルな区間DPで良いと気付けなかった。（自分が書いたコードは結構複雑……）

　それに気付けていればもっと簡単に書けたねぇ。


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

2025年3月10日月曜日

AtCoder Regular Contest 194 (Div. 2)

　ABDの三完。終了10秒前にDを通して青落ちを免れた！　かと思いきや、その後、Dが（本質的に）嘘解法だったことが発覚！

コンテスト後のツイート

C - Cost to Flip

　一応自力AC。
　三分探索解と比較して、バグ探しを頑張った。

　コンテスト中は、(1,1)→(0,0)→(0,1)と変化させるものの個数で三分探索できる気がしたが、それでは上手くいかず。なら、差分計算するしかない！　と書いたもののWAが出て、諦めてDへ行った。

　しかし、差分計算するしかない、というのは正しい。
　愚直解（三分探索解）とランダムケースで比較し、どうにかAC。

　この問題では、AHC的な能力を問われている気がした。差分計算は山登りや焼きなましをするとき重要。
　AHCでも、差分計算の立式が下手で失敗していることは結構ある。足りないのは状況整理能力だろうか……。

　なお、差分計算の失敗だけでなく、（三分探索で失敗したのに）凸性が保たれていると勘違いして実装していた。これも反省。せっかく差分計算しているのだから、全探索しないと。

D - Reverse Brackets

　嘘解法でした。


　コンテスト中は時間なかったけど、落ち着いて考えていれば気付けたはず……。
　

E - Swap 0^X and 1^Y

　解説放送を見てAC。

　標準形（辞書順）を考えるという方針をまず考えたけど、それで正しいのかが分からず解説を見てしまった。

　実はそれで正しく、どうやって高速に標準形を求めるか？　という問題だった。swapできるものを最初にまとめておくという方針は分かりやすいですね。
　あまり考えずに解説を見てしまったけど、考えたら気付いたのかなぁ。
　







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

2025年3月9日日曜日

Codeforces Round 1005 (Div. 2)

　Dまで。

コンテスト後のツイート

E. Mycraft Sand Sort

　解説AC。
　簡単なのかと思ったら、全然簡単ではなくて、解説など色々参考しても理解するまでずっとかかってしまった。（なお、解説の方法は理解していないし、自分がやった方法に嘘の疑いもある）

　Cは与えられたものと同じものを使うしかなく、Pの個数を求める。

　P_iとP_jが交換可能なのは、

・iとjが隣接しており、同じ色なとき

　だけではなく、

・iとjが同じ色で、iとjの間にあるもの全てが、P[i]やP[j]より小さいとき（これは、上の条件を内包している）

　と気付かなくてはいけない。

　コンテスト中はここにも辿り着いていなかったが、それをどう数え上げれば良いかが難しい。

　解説とは（多分）違う、左右を管理する方法でやった。

　P[i]が小さい方から見ていき、隣合っている同じ色がどの範囲までか、を見て、その要素数を答えにかける。その後、index iを削除する。

　削除というのは、左右を管理し、

・RIGHT[LEFT[i]]=LEFT[i]
・LEFT[RIGHT[i]]=RIGHT[i]

　のようにするということ。まあ、左右を管理するときはよく使う手法ですね。

　ここで、毎回同じ色がどこまでか？　を調べるとTLEするので、Union-findでくっつけ、Unionできる端の値をもっておく。
　しかし、そうすると、その端の値は既に消えていることがある。そのときは再計算（消えていないindexまでLEFT,RIGHTをたどる）してACした。

　最後の再計算するところの計算量が怪しいけれど、今回はACできた。危ないテストケースはありますか？




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

2025年3月8日土曜日

yukicoder contest 459

　ABの二完。Cを考えているうちに寝てしまった。Cは一応自力で解けたけど、寝なかったら解き終っていたかというと微妙なところ。


No.3050 Prefix Removal

　自力AC。

　もし、Aの要素全てを使い切るとすると、満足度の変化は、

・最初の操作で全てのiに対して+A[i]
・選ぶpより大きい全てのiに対して+A[i]

　のようになる。
　これを最大化するためには、Aの後ろからの累積和を取って、大きい方から選んでいけば良い。ただし、最初に0を必ず選ばなくてはいけないことに注意。

　ここまで分かったら、後はAのうち何個使うか？　という部分。
　これがなかなか思いつかなかったのだが、heapqを使えば全探索できることに気付いた。やや思いつきにくいし面倒ではあるけれど、何度もしたことがある方法だった。

　上手くやれば全探索できるのでは？　と考えてみなくてはいけないねぇ。

　

No.3051 Make All Divisible

　テストケースは見たけど、一応自分で考えてAC。

　まず、

・sum(A)がkで割り切れる
・max(A)<=sum(A)/k

　のとき、この操作で全てを0にすることが可能（ということは考えているうちに思い出した）。

　なので、各A_iをA_i%kに置き換えた数列でこの条件を満たせば一番良い。

　そして、満たさない時は、現在のAの中で最も小さい数で、かつ、+kしても最初のAの値以下であるようなものに+kして、条件を満たすかを見ていく。

　計算量は分からなかったが、この方法でACできた。

No.3052 Increasing Sliding Window Minimum

　解説AC。

　二乗DPになりそうなのは分かる。
　DP[i][j]を、左からindex iまで埋め、使っていない数字の個数がj個のときの個数としてできそう、と思いかなり長いこと取り込んだがWAが取れず解説を見た。

　すると、小さい数字から埋めて行くのが正解だった。
　考え方は似ていたが、それだと、次の数字がどこのindexにまで入れていい、ということが分かるため、最初から分かっている数字を扱いやすい。

　DP[i]をindexいまで置くことが可能なときの個数、と定義してやったが、この定義の仕方が悪く、n=2のときに例外処理をしなくてはいけない実装になってしまったが、無事AC。
　DP[i]を、今までの数字で一番右に置いたindexがiのときの個数、とすべきだったか。
　




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

2025年3月7日金曜日

Codeforces Round 997 (Div. 2)

　Cまで三完。


D. Unique Median

　こたつがめさんの放送の振り返りを見てAC。アイディアは自然だが難しい。解法を理解するまでに、三回放送を見返した。

　コンテスト中は、中央値が1～10それぞれになるときに、場合の数を求めるという方針を考えていた。
　中央値がaのとき、aを0、a未満の数を-1、aより大きい数を1としたとき、（1の個数と-1の個数の差）が(0の個数)/2切り捨て以下になれば良い、というところまでは分かったが、数え上げに持っていけず。

　そうではなく、k以下で-1、kより大きいとき+1として、累積和を取らなくてはいけなかった。
　こうすると、区間和が0のとき、k以下のものの個数とkより大きいものの個数が等しくなるため、goodでない配列の個数を求められそう。（Zero-Sum Ranges系の処理ですね）
　これに加えて、「kが中央値になるため区間内にkが存在する」という条件が必要になる。これは二分探索で処理できる。


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

2025年3月1日土曜日

yukicoder contest 458

　Eまで五完。Eまではすらすら解けたが、Fが分からず考えこんだところで睡魔に襲われてしまった。


No.3040 Aoiスコア

　自力AC。

　DPを考えていたがうまくいかず、三頂点のpathなら列挙できると気付きAC。
　結構苦戦した。眠りに落ちる前に一度解けたと思ったが、そのときはDPを考えており、それではダメだった。

No.3041 非対称じゃんけん

　解説AC。

　bitsetの利用は考えたけれど、bit_countの部分が速くならないためダメだと思ってしまった。その部分も1/64になるんでしょうか？
　PyPyではTLEだったけれどPythonだとAC。

No.3042 拡大コピー

　自力AC。

　こういう問題で重心を考えるのは定石ですね。

No.3043 括弧列の数え上げ

　苦労したが自力でAC。

　括弧列の個数がカタラン数であることは分かっているので、calc(x):長さxの括弧列Sのf(S)の総和を、最初の(と何番目のindexが対応するかで場合分けして計算した。

　一番外側で"("と")"が対応している長さxの括弧列Sたちのf(S)の総和は、長さx-2の括弧列たちの総和に、その個数*(x-2)/2（閉じカッコの数）だけ足したものとなることを利用した。

　難しかったし、解説の方法も簡単ではない気がするのだが、AC人数を見ると解けなくてはいけない問題だったのか。

No.3044 よくあるカエルさん

　自力AC……と言っていいのかな。

　「すごろくであるマスに止まる確率」と検索したら、DPで求められるということが出てきて、それなら行列累乗で求められると気付いた。
　検索しないとDPと気付かなかったのは良くない。

No.3045 反復重み付き累積和

　解説AC。

　解説を参考にしたけど、行列ベースで考えていた。

　長さ4の数列A（1*4の行列として見ている）に対して、重みkの累積和を一回取る操作は、

1 k k^2 k^3
0 1 k     k^2
0 0 1     k
0 0 0     1

　という行列を右からかけることに対応している。

　このx乗がどうなるかというと、実験すると、これらのk^nなどのところに、Combi(n+x-1,x)という二項係数を掛け合わせたものになる。

　のだが、これだと三乗になってTLE。

　解説を見ると、この行列計算はFFTで計算できるらしい。
　それを見てAC。

　行列計算のうち、どのようなものが形式的ベキ級数的に表せるのかを知っていると良いのかもしれない。


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

2025年2月25日火曜日

鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）

　Fまで。Gも解法はあっていた。

コンテスト後のツイート


　G、unratedだったから提出しなかったけど、ratedだったらどうしただろう。多分提出していたと思う。
　ChatGPTにプログラミング言語の変換をしてもらう→自分で修正、は許されていると思っているんだけど……。

　ただ、ルールにある文言を入れても、忠実に変換してくれなかったり、元のコードのコメントアウトしろ、っていうのを無視されたりする。また、そのままでは動かないコードが出てくることも多い。
　意図通りの変換になることはそれほど多くないよね。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 457

　AHCの最中だったため、Aだけ解いて撤退。


No.3028 No.9999

　一見、何も分からなかったが、タグの「循環小数」というのを見て、循環節の長さと一致することに気付く。
　それでも分からなかったので、ChatGPTに解き方を聞いてみたところ、コードを教えてくれ、そのままAC。

　10^L=1(mod x)を満たす最小のLは10のxに対する位数と一致し、これはトーシェント関数の約数のうち最小のものなので、トーシェント関数の約数のみを試せば良い、という解説も分かりやすい。

　トーシェント関数のライブラリも、自前のものよりこっちの方が良いのかと、考えてしまう。

No.3029 オイラー標数

　setにソートしたものを放り込んでいき、AC。

　クエリの与えられ方の意味がぱっと分からなかったけど、三角形をなす三頂点をどんどん与えられているということなんですね。

No.3030 Kruskal-Katona

　定理の名前で検索したら、貪欲で良いと書いてあったためAC。

　なお、N_i=N_i-1+1じゃなくてはいけないと定理を検索するまで誤解していた。サンプルの答えが全部連続した数なのが分かりにくくしている気がする。

No.3031 曲面の向き付け

　自力AC。タグのDFSはヒントにした。

　問題を理解するのが難しいが、理解したら面白い内容で、難しくはなかった。数学的な問題文は理解するのに時間がかかってしまうね。
時刻: 0 件のコメント:
ラベル: ,

2025年2月16日日曜日

yukicoder contest 456 オムニバス

　Cまで三完。


No.3022 一元一次式 mod 1000000000

　解説AC。だが、解説を読んだ後も混乱した。

　整数論の問題なので、2と5に分解してどうにかするしかない。Mに2や5の素因子が多いとダメそう……というところから、整数解が存在する条件が得られる。

　すると、両辺を2や5で出来る限り割ることで、

・N'*k+M'=0(mod d')

　という形の式になり、N'とd'は互いに素になる。なので、オイラーの定理を使って-M'/N'の値を求めることができる。

　この値が0になるのは、そもそもM'がd'の倍数のとき。なので、N*kがd'の倍数になれば良い。N'とd'は互いに素なので、このときはd'が答え。

No.3024 全単射的

　自力AC。

　二部マッチングだからフロー！　と思ったが、うまくグラフが構築できず、よく考えたらUnion-findで解けると気付きAC。

　しかし、公式解説の解法はフローで解いていた。景品だけでなく、人の方も頂点にすると思いつけなかった。
時刻: 0 件のコメント:
ラベル:

2025年2月14日金曜日

Codeforces Round 1004 (Div. 1)

　AB二完、だった。が、AはinteractorのバグでACになっていて、正しいinteractorだとWAだったらしく、WAになっていた。このブログを書いている2/14現在、レートも、当初は+1だったのが-76になっている。


UPD3: After the analysis, it was determined that this problem affected a small number of participants. There are no submissions that get AC with the correct interactor and erroneously received a non-AC verdict earlier. Therefore, the following decision was made:

If your solution worked with the old interactor, but does not work with the correct one and your rating has decreased, then the round will be unrated for you.

　に該当するためこれが正しければunratedになるはずだけど、この後、unratedになりレートが戻るのだろうか？

コンテスト後のツイート

A. Object Identification

　自力ACだが、本質的な考慮漏れがあった。

　自分のツイートの方法で大体良いのだが、「値が違ったり両方1だったらA」の「両方1だったら」というところがおかしい。両方n-1未満なら、などとしてAC。

　ここでは、1とnが巡回する場合を考えている。1とnだけが巡回するなら両方1だが、1→2→n→3→1なら距離2で巡回するわけで、距離1だけで巡回するわけではない。
　コンテスト中は距離1で巡回する場合しかありえないと思っていたので、本質的な間違いだった。

　本質的なミスでWAになっているのだから、システムテストで落ちたときと同じ気持ちで、レートが下がったとしても受け入れるべきか。

D1. Club of Young Aircraft Builders (easy version)

　自力AC。

　実験したら二項係数そのままだったので、それを使ってAC。
　あと10分あれば解けていたと思うけど、なぜ二項係数になるかは分かっていない。



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

2025年2月11日火曜日

AtCoder Regular Contest 192 (Div. 2)

　BCの二完。

コンテスト後のツイート

A - ARC Arc 

　解法ツイートなどを参考にAC。
　コンテスト終了直前に4の剰余で場合分けすれば良いことには気付いたので、時間があれば自力で解けたとは思う。

　しかし、誤読に気付いた後、10分くらい時間はあったのだが正しい解法にはたどりついていなかった（10分くらいかかって4の剰余で場合分けすれば良さそうなことに気付いた）ので、4で割って2余る場合の考察にはもう少し時間を要したと思う。
　惜しい、という感じではなかった。

D - Fraction Line

　解説AC。

　素因数別に考え、後でまとめられるということに気付けば難しくない。しかし、この部分は結構非自明な気がする。
　ただ、こういう問題で素因数ごとに考えるのは定石の一つなので、それでできるのでは？　と疑い、実験してみるべきだったか。
時刻: 0 件のコメント:
ラベル:

2025年2月10日月曜日

日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）

　Fまで六完。だが、Fまでも時間がかかり過ぎだし、Gも解けなくてはいけない問題だった。

コンテスト後のツイート

G - Fine Triplets

　まず、類題（このC）をやっていたのに、それを生かせなかったのがまずい。
　いや、FFTを最初考えたのは類題経験があったからかもしれないが……。FFTを思い付き、しばらく考えたにもかかわらず棄却したのはひどい。

　類題の記事でも書いた、「登場回数の配列同士を畳み込めば、二つの配列の和の要素の登場回数になる」が本質。頭に入れておかねば。






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

2025年2月3日月曜日

AtCoder Beginner Contest 391

　Eまで五完。

コンテスト後のツイート

F - K-th Largest Triplet

　解説AC。

　Kの制約に気付いていたら正解できたと思う。こういう致命的な制約見逃しはあまりやったことなかったのだが。

G - Many LCS

　自力AC。

　LCSを求めるのにDPが必要なので、この問題もDPで解くしかなさそう。
　N<=10という制約を見て、bit DPなどを考えたがちょっと違った。「i文字の部分列を構成するときの最短のindexはどこか？」を考え、それをDPのキーとしたいと考えると、それは単調増加なのでindexの部分集合の個数しかない。これを利用すれば解ける。
時刻: 0 件のコメント:
ラベル:

2025年1月28日火曜日

Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)

　Cまで三完で紫に落ちる。

コンテスト後のツイート

D. Balanced Tree

　こたつがめさんの放送の振り返りを見てAC。

　全方位木DPが必要などと思っている時点で解法には遠かった。
　（全方位木DPのためにトポロジカルソートはしていたが）根付き木にして考えて良いということも分かっていなかったため、正しい解法まではかなり遠かった。

　惜しいところまで行っていないため、まず根付き木で上手くいかないか考えましょう、くらいしか言うことがない。

E1. The Game (Easy Version)

　こたつがめさんの放送の振り返りを見てAC。

　コンテスト中に似たことは考えていた時間はあった気がするが、まとめられなかった。ただ、実際の敗因は、実装（LCAと比較する）が思い浮かばなかったことだと思う。この放送を見たときも、まず思ったのは、実装どうやるんだろう？　だったので。

　木の問題で、subtreeについて問われているのだから、LCAを考えるのは自然。そこを元に考えていたら正しい解法を見つけられたかもしれない。



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

2025年1月27日月曜日

AtCoder Regular Contest 191 (Div. 2)

　Bまで二完。

コンテスト後のツイート

C - A^n - 1

　解説AC。

　オイラーのトーシェント関数などを考える方針は悪くはなかったようだが、そこからどうすれば良かったか。原始根などに関する知識がもっとちゃんとあれば良かった？

　想定解の方はどうやって思いつけば良かっただろう。
　実験はしたがそこから進めなかった。n乗が絡むので、二項定理に思いを馳せるべきだったか？
　

D - Moving Pieces on Graph

　解説AC。

　場合分けがちゃんとできたとしても実装で引っかかる部分が多く、難しい問題だった。2nd shortest pathを求める必要がありそうだが、実際は必要ない……といったあたりも混乱しやすい。
　



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

2025年1月26日日曜日

AtCoder Beginner Contest 390

　ABCEの四完。

コンテスト後のツイート

D - Stone XOR

　冷静にDFSを書いてAC。
　全探索する問題なのは制約を見れば分かる。あとは、どうやって書くかなのだが……。コンテスト中は、部分集合ごとにbit全探索しており、「ただ全部見る」というのより明らかに時間がかかっていた。

　DFSし、今ある分け方のどこへ次の要素を加えるか？　を見るようにしたらAC。制約が厳しいのか？　と思ったけど、PyPyでも問題なく通る問題でした。


F - Double Sum 3

　解説AC。

　コンテスト中にあまり考えず、コンテスト後すぐ解説を見てしまったけど、主客転倒と言われれば確かに、となる問題。

　[L, R]のLの方を基準に考えるのは自然だし、A[i]=Lとなる範囲はどれくらいか？　と考えるのもそんなに思いつきにくい感じはしない。
　Dを中心に考えていたとはいえ、問題を読んだのなら解けなくてはいけない問題でした。反省。
時刻: 0 件のコメント:
ラベル:

2025年1月25日土曜日

Codeforces Round 1000 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Triangle Tree

　苦労したが、公式解説など色々参考にしてAC。

　まず、木DPでできそう、と思ってしまったのが筋が悪かった。
　主客転倒的な考え方でいくべきだった。

　その後は、うーん、どうすれば良かったんだろう。
　min(d_u, d_v) の総和と、d_{LCA}の総和に分けて考えれば良い、というのは立式を見れば分かるが、その時点でちょっと思いつきにくい。

　さらに、それぞれの求め方も簡単とは言えず……。


　とはいえ、立式し、式を簡単な形に分解しようと思う部分は自然。
　その後、主客転倒でいこう、と思えるかどうかが勝負なのかな。
　



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

2025年1月23日木曜日

Codeforces Round 998 (Div. 3)

　Eまで。Div. 3なのにFから難しい……。


F. Multiplicative Arrays

　こたつがめさんの放送の振り返りを見てAC。理解した後でも難しい気がするが……。

　二項係数でどうにかする問題というのは分かるが、そこで止まってしまった。

　たとえば、k=6でn=4のときの場合の数は、2を入れる位置と3を入れる位置を考えて、4*4となる。なので、n以下のを足し合わせる場合、4*4+3*3+2*2+1*1＝30となる。

　……のように考えて、上手くいかなかった。


　このように考えるのではなく、数字を入れる箇所を何個にするか？　と考えると二項係数の和になり高速化できる。
　先程の6の場合だと、[6], [2, 3], [3, 2]の三通りがある。

　[2, 3]の順で入れるとすると、Combi(4, 2)通り。n=3, 2, 1の場合を考えると、Combi(3, 2), Combi(2, 2), 0通りとなり、その和は（公式により）Combi(5, 2)と計算できる。

　単純に素因数分解するのではなく、何をどういう順番で掛け合わせてkにしたか？　と考えなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2025年1月22日水曜日

ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041）

　413位という苦しい成績。

コンテスト後のツイート

　高さ10の頂点をできる限り増やしたい、というのは分かるのだけれど、どうすれば実現できるか分からず上手くいかなかった。
　山登りなども考えた（し、どうやらそれをやった方が良いスコアが出たらしい）が、子たちも一斉に変えなくてはならないず、高さが10より大きいものが出た場合どうすれば良いのか？　というあたりで躊躇してしまった。


　このツカモさんのツイートを参考に、コンテスト後に話題になった貪欲を実装してみた。

　根にできるだけ小さい値を割り当てたい、という気持ちは良いのだが、そのために、「Aを小さい順に見て、全点にいきわたるよう必要なだけ取る」、というのではなく、「Aを大きい順に見て、その点がなくても全点にいきわたるようなら除く」としているのが技巧的に感じた。
　ただ、その方法にさえ気付けば後は自然ともいえるか……。



　コンテスト中どうすべきだったかは悩ましい。

　自分がコンテスト中考えていた方とこの貪欲解法は結構似ているので、そこへ辿り着けたら良かったのだが、上手くいかなかった。

　DFSを試すべきだったとは思うけど、普段再帰でのDFSを書いていないため、解説放送にあるようなDFSにはちょっと慣れていないんだよね……。解説放送のDFSを再現するのに時間がかかってしまった。それだとあまり良いスコアが出なかったので、DFSの良さに気付くのもそんなに容易でなかった気がする。

　シンプルな解法を考えて、山登り/焼きなましなり、ビームサーチなりを試す、という方針の方が良かったのかなぁ。
時刻: 0 件のコメント:
ラベル:

IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)

　Eまで。

コンテスト後のツイート

F1. Kevin and Binary String (Easy Version)

　端から貪欲で良いという情報を目にしてAC。

　ツイートにも書いた通り、コンテスト中も端から貪欲で良いのでは？　と思ったのだけれど、「SとTで端に同じ文字があったら消去する」という処理を入れていたためWAになっていました。
　いやこれ、まずいかも、とは思ったのだけど、検討したら大丈夫に思えたため、実装の都合で入れたんですよね。実際はそれほど実装が楽になるわけでもないのに、無駄な処理を入れたためWAになったのは悲しい。ACしなくてはいけない問題でした。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 300

　ABの二完で終わってしまった。


No.1552 Simple Dice Game

　Writer解説とほぼ同じことを考えていたのに詰められなかった。
　解説中の、

　ベン図を考えれば、最小値が L 、最大値が R の数列の個数は、
・(R-L+1)^N-2(R-L)^N+(R-L-1)^N
　と求まります。

　という部分。この式がもっと複雑な包除原理の式になる気がして悩んでいた。

　（今回は二つの集合だけの単純な場合だけど）包除原理を使う問題は苦手なんだと思う。包除原理を疑ったらまずベン図を描いてみると改善するかな……。

No.1554 array_and_me

　自力AC。作者さんが、ABCで似た問題が出たとツイートしていたのを見て挑戦、無事ACした。あまり似ている気はしなかったけれど……。

　heapqに入れて貪欲という解法はすぐに見えたのに、heapqに詰めるものを間違えて実装に時間がかかったのは反省。



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

2025年1月18日土曜日

yukicoder contest 455

　Bまで。A,Bは制約の違う同じ問題なので、実質一完でした。


No.3004 ヤング図形

　自力AC。

　二項係数と階乗の数の積で表すところまでは問題ない。問題は、制約が大きいため、それを愚直に計算しては間に合わないところ。階乗たち（F[i]とする）を陽に持っては間に合わないため、どのようなF[i]を何個かければ良いか、または何個割れば良いか？　を持てば良い、というところまでは分かったが、これでもTLEだった。

　コンテスト後、冷静になれば、どのような入力でTLEするかに気付ける。

1
2 5

　を、Combi(10,8)*Combi(8,6)*Combi(6,4)*Combi(4,2)*Combi(2,0)を計算し、5!で割る、と計算しようとしていたが、これだとm（この入力だと5）が大きいとき間に合わない。

　この積が実は、10!を2=で5回割ったものだ、と気付きAC。

　うーん、コンテスト中にACできなくてはいけない問題でした。

No.3005 トレミーの問題

　トレミーの定理（覚えていなかった）の逆を使ってAC。

　解説を見ると、整数だけで解く方法があるらしくびっくり。

No.3006 ベイカーの問題

　自力ACだけど、タグに「行列」とあったのを見てしまったから自力とは言えないね……。

　行列累乗だと気付ければ解ける。漸化式を考えるのだから行列を考えるのは自然ですね。
時刻: 0 件のコメント:
ラベル:

2025年1月14日火曜日

AtCoder Regular Contest 190 (Div. 1)

　A一完。

コンテスト後のツイート

A - Inside or Outside

　ACしましたが、after contestでWAが出ました。

　ソートの仕方がまずくて、[a,b],[a,c]と、左端が同じものがあるとき、包含関係の判定がおかしかったのが原因でした。
　本番中にWAが出ていたら気付くのに非常に苦労した気がする……。運が良かった。
　

B - L Partition

　解説AC。解説放送も見ました。

　コンテスト中に考えていた再帰では間に合わなそう、ということで、何か方針転換しなくてはいけなかったのだけど、そういうとき、二項係数を考えるのは定石の一つ。考えなくてはいけない方針でした。ただ、解法ツイートなどを見てそう言われても全然思い浮かばなかったので、解くのは厳しかったかもしれない。

　また、二項係数の和を順に求めていくところも、（多分やったことはあると思うのだけど）記憶にありませんでした。

C - Basic Grid Problem with Updates 

　解説放送を見てAC。

　コンテスト中、スタートとゴールからDPして、差分計算をどうにかすれば良い……というところまでは考えていた。

　あとは、それらを用いて答えがどう表せるかが分かれば良かった。ただ、各クエリごとにmin(H, W)使って良いということにも気付いていなかったので、正解に近かったという感じではないが。

　ただ、Bよりは惜しかった気がするので、こっちに集中すべきだったかもしれない。

D - Matrix Pow Sum

　解説AC。解説放送も見ました。

　難問に思えた。実験すればある程度分かるという意見も見たけど、あまり思いつきそうにないなぁ……。

　ただ、解説放送で言及していたように、行列をグラフの経路数と見て行列の累乗をn歩進むときの行き方と捉える（たとえば、ここが参考になる）という考え方は身に着けておきたい。
　特に、「隣接行列をn乗してできる行列の各要素は、その行番号から列番号への頂点までを、そのグラフの辺をちょうどn回使うルートの総数」である。
時刻: 0 件のコメント:
ラベル:

2025年1月12日日曜日

HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)

　Eまで五完。

コンテスト後のツイート

F - Dangerous Sugoroku

　コンテスト中の方針でACしたが、実装に非常に苦労した。というか、自力じゃデバッグできず、ACしているコードとランダムテストで比較した……。

　区間で管理する方針が良くなかったのだろう。
　どこへいけるかをlistで持った方が実装しやすかったようだ。

G - Simultaneous Kagamimochi 2

　Eの正しい解法を理解し、セグ木を使うと知れば後は難しくなかった（添え字で少し苦労したけど）。

　この問題がどうこうというより、Eで間違った考察をしていたのが敗因。


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

2025年1月9日木曜日

Hello 2025

　Cまで三完。

コンテスト後のツイート

D. Gifts Order

　けんちょんさんの記事を参考にAC。

　セグ木を使うのは第一候補だったのにこれを思いつかなかったのは良くない。可換性が成り立たないとセグ木が使えそうという判断が鈍ってしまうようだ。気を付けよう。

E2. Another Exercise on Graphs (hard version)

　こたつがめさんの放送の振り返りを見てAC。

　ワーシャルフロイド法で、一辺を変更するときは辺の二乗の計算量でできることは覚えておきたい。
　妙に制約が厳しい気がするけど、クエリ問題だから仕方ないのかな。（と思ったら、公式解説の方法はもっと速いらしい）

G. Secret Message

　証明は難しいが、「十字のマスのうち一マスを塗れば良さそう」というところから発想することは可能だったか。
　ただ、制約が厳しく、二次元配列を一次元に直さないと通らなかったので、コンテスト中にACするのは厳しかったかもしれない。
時刻: 0 件のコメント:
ラベル: , ,

2025年1月8日水曜日

AtCoder Beginner Contest 387（Promotion of AtCoderJobs）

　Cを飛ばしてFまで五完。

コンテスト後のツイート


C - Snake Numbers

　桁DP（もしくは、それに近い）方法でやっていた人が多そうだったけど、コンテスト中に考えた場合分けの方針のままでAC。
　ただし、場合分けに苦戦し、かなりの時間がかかった。解けることは分かったけれど、桁DPで書いた方が混乱は少なそうです。

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