2025年8月29日金曜日

Codeforces Round 1046 (Div. 1)

　D1まで四完。D2は分かったのに実装間に合わず。あと一分あれば間に合っていた気がするので悔しい。

コンテスト後のツイート

D2. From the Unknown (Hard Version)

　D1と同じ発想で解ける。
　最初[125]*10000と聞く。（この125とか10000は色々試して探す）
　0のときは[1]*15000で決定できる。
　そうでないときはD1と同じようにやる。同じ値が連続して15000/2個以上出てたらクエリの長さが間に合わないが、この値だと間に合っている。

　この最後のパートをD1と全く同じように書いていたのがダメでした。クエリ回数を抑えるため、同じ数字が返ってくるものの個数だけ使わなくてはいけなかった。これでAC。
時刻: 0 件のコメント:

2025年8月28日木曜日

AtCoder Beginner Contest 420

　Fを除く六完。500位以内だったのでレート減少は止まったかと思ったのだが、-5だった。悲しい。

コンテスト後のツイート

F - kirinuki

　解説AC。

　といっても、解説の詳細は理解できず、Cartesian Treeを使うことと前計算を行うことを理解し、あとは自分で考えた。

　まず、最大長方形っぽいと思うところは良かったが、そこから、Cartesian Treeを使おうという発想に行かねばならなかった。すると、横の長さと縦の長さの範囲が決まったとき、その中にK以下の長方形は何個あるか？　という問題に帰着できる。

　（横の長さ, 縦の長さ）が決まったとき、K以下の長方形が何個あるかは求められるので、それを前計算して累積和を取れば範囲に対しても対応できる。横の長さ*縦の長さに制約があるのがポイント。

　整理すれば一つ一つのステップはそんなに難しくないのだが、実際に解くのは大変な問題だった。

　とはいえ、一番重要なのは、最大長方形っぽいというところから、Cartesian Treeを使おうと発想する部分。ここは押さえておきたい。
　



時刻: 0 件のコメント:

2025年8月25日月曜日

Codeforces Round 1044 (Div. 2)

　AB二完。
　Cの解法は思いついていたのだが、クエリ回数が抑えられることに気付かず、考えているうちに寝てしまった。


C. The Nether

　自力AC。

　とりあえず、答えの個数を聞くため、S={1, 2,..., n}、とし、全ての始点に対して質問しなくてはいけなそう。それらをメモしAとしておく。

　その後、xが始点なら、A[x]=A[y]+1となっていて、かつx→yに辺があるものを探していけば良い。
　のだが、このクエリ回数がn以下になることが分からず考え込んでしまった。

　ちゃんと考えると、A[i]=kとなるiを一つ見つけたらk-1を探し始めれば良いため、このパート全体でn回質問すれば済む。

　なので、全体でのクエリ回数は2*n回に抑えられている。
時刻: 0 件のコメント:

2025年8月24日日曜日

AtCoder Heuristic Contest 052

　188位。しかし、評価値と温度を変えると本番4位相当が出た。

コンテスト後のツイート

　色々考えた後、焼きなましできるのでは？　と思い、ChatGPTにお願いした。
　以下のようなコードを出力してもらった。

初期状態：
・各ロボットの0番目のボタン、1番目のボタンを"U"、"R"とする。 
・まず、0のボタンをx=1回、1のボタンをy=1回押す。
・各ロボットの2番目～4番目のボタンを"L","D","R"とする。ここで、2番目のボタンと4番目のボタンは対を為すボタンでなくてはいけない。 
・「2番目のボタンをz=1回押し、3番目のボタンを1回押し、四番目のボタンをz回押し、三番目のボタンを1回押す」というのをw回繰り返す。ただし、w回目の最後の三番目のボタンは押さない。

　ここまでのボタンを押した回数が、turn=x+y+(2*z+1)*w-1回。この一連のロボットの動きでワックスがかけられていないマスがnマス残っていたとすると、 この評価値を、turn+n*100とする。 

遷移： 
・あるロボットの「0番目・一番目のボタン」を変更 ・あるロボットの「2番目～4番目のボタンのボタン」を変更 ・x,y,z,wを1増加、もしくは1減少させる。 

　この方針で1.8秒の間焼きなまし、最も評価値が良い場合を出力する。 このコードをRUSTで出力して下さい。

　この後、無駄な操作を省くのと、余ったマスを適当に掃除するコードを書いてもらい提出。

　その後、評価値をturn+n*5にした方が伸びると分かり、それが最終提出で188位だった。


　コンテスト後、評価値はturn+nにした方が良いと気付く（これで163位相当）。さらに、それに合わせて温度も調整したところ、本番4位相当のスコアが出た。


　提出コードをちょっといじれば各段にスコアが上がったので、惜しかったといえば惜しかったんだけど、今回自分でほとんど実装してないため実感が乏しい。

　自力で実装しないと身にはなっていない気もするし、どうなんだろう。

　ChatGPTさんはちゃんと実装してくれてたんだなぁ……。




時刻: 0 件のコメント:

2025年8月23日土曜日

Codeforces Round 1043 (Div. 3)

　Eまで。

コンテスト後のツイート

F. Rada and the Chamomile Valley

　コンテスト中の方針で良かったが、条件が抜けていた。

　橋で、かつ、
・edge x-yで、始点からの距離をD、終点からの距離をD2とすると、D[x]+D2[x]=D[y]+D2[u]を満たす

　ようなものを考えれば良い。こうするとAC。

　ただ、なぜかTLEが出て一時間以上悩んだ。
　結局、TLEの原因は、上記の距離Dを求めるのをDFSでやっていたためだった。木じゃないのだからBFSじゃないといけない！！

　こんな簡単なことで一時間以上悩んでしまい、20ペナ近く出したのは愚かとしかいいようがない。ひどすぎる！
時刻: 0 件のコメント:

yukicoder contest 479 AngrySadEightお誕生日コンテスト2025

　ABの二完。
　Cで桁DPをバグらせ続けた……。


No.3242 Count 8 Included Numbers (Hard)

　下の桁から桁DPしようとして長い時間をかけてしまった。

　求めたいものを二つに分離し、

・calc(keta,minus)でN[:keta+1]-minus以下の8を含む個数
・calc2(keta,minus)でN[:keta+1]-minus以下の個数（つまり、N[:keta+1]-minusの値）

　をそれぞれ桁DPしようとしたらなんとか書けた。

　下の桁から桁DPをする場合、Nという数字を明示的に持っても間に合う場合は簡単に書けるけど、繰り下がりの処理をちゃんと書いてやらなくてはいけないときは結構大変になってしまうのかもしれない。

No.3243 Multiplication 8 1

　行列累乗と言われてAC。

　コンテスト中この問題は読んだのに、DPで求められることにすら気付かなかった（組み合わせ的な何か？　と考えていた）のはショック。

No.3244 Range Multiple of 8 Query

　三桁の8の倍数を全探索し、rより以前にある数字を二分探索で探し、貪欲に使っていく……という方針は思いついた。
　が、一桁や二桁の場合に気付かずWA。テストケースを見て気付き変更したがTLE。ChatGPTにC++に直してもらいACした。

　C++に直しても制限時間ギリギリでなんで？　と思ったが、二分探索が不要だったよう。各indexについて、0～9それぞれの数字がどこのindexにあったかを三つもっておく、というのは二分探索を使わなくとも前計算できる。

　気付かなかったけど、確かにそうですね。

No.3245 Payment with 8-rep Currency

　自力AC。

　小さいものについては全探索し、大きい値については、作れる（8で割ったとき）互いに素な二つのものから作るという方針。

　（1, 1, 1, 0）で123が、（2, 1, 2, 0）で235が作れ、この二つは互いに素であり、拡張ユークリッドの互除法を使うと、

・123 * 107 - 56 *235 = 1という式が得られる。

　これを使って不定方程式を解くと、Nについての一般項が、

x=107*N -235*k
y=-56*N+123*k
（kは整数）

　となるので、これらを満たして0以上になるような最小のyを求め、その（x, y）のときに条件を満たすことを調べればOK。

　自然な解法かと思ったが、ツイッターを検索したところ拡張ユークリッドの互除法と書いている人はいなそうだったので、珍しいのかも。

No.3246 80% Accuracy Calculator

　非常に苦労し、提出してエラー出力結果を見ることを繰り返してAC。
　最初は、「+ A C C」みたいなのも許されると思ってなんでREなのかと何度も提出してしまったし……。

　足し算が100%成功するとした場合、
「A B 0」を「0 B 0」とした後、
「B B 0」「B B 2B」「3B B 2B」……とBずつ加算していく方法が考えられる。（最初にどちらにBを加算するかは偶奇で分類）

　足し算が成功しているかを適切に判断した場合（自分は、六連続正解が出たら採用、とかした）、これでもギリギリ回数が間に合ってしまいそうなのが迷うところ。だが、実際はこの方針で間に合わせるのは無理なんだと思う。

なので、
「B B 2B」「4B B 2B」「4B B 8B」……と、2ベキのBを作ってから、Bずつ加算していく方針でACした。

　しかし、解説を読むと、繰り返し二乗法のようにやればもっと早くできるようで。タグに「繰り返し二乗法」とあるのは見ていたのに、気付かなかった。
時刻: 0 件のコメント:

2025年8月21日木曜日

yukicoder contest 478 オムニバス

　AGの二完。
　Gはセグ木上の二分探索を用いて実装したので公式解説があまり理解できていない。


No.3234 Infinite Propagation

　自力AC。
　二文字だけなら難しくないけど、文字数が多い場合は解けるんだろうか？

No.3237 Find the Treasure!

　自力AC。
　木の二部グラフ性を使って半分に決め、あとは二分探索で。

No.3239 Omnibus

　26*26*26個、BITを立てなくてはいけないのか？　などと思い、良い方法があるかと思って解説を見たら、平方分割などというキーワードがあったので、それをヒントにAC。

　26*26*26個のうち、個数が小さいものはsetで愚直に、多くなったらBITを使って解いた。

　解説には、動的BITを使っても解けるなどと書いてあり、自分の解法もそれに近いと思うけれど、動的BITを持っていないので仕方ない。





時刻: 0 件のコメント:

2025年8月18日月曜日

AtCoder Beginner Contest 419

　Dまで四完でレートを大きく下げる。
　ABC二回でレート100落しているのだが。

コンテスト後のツイート


E - Subarray Sum Divisibility

　解説AC。

　コンテスト中は、
　B=[sum(A[i:i+L]) for i in range(N-L)]
　みたいな配列を作り、あるindexへのplusはBの区間にplusすること……と考えていた。こう考えると、連立方程式ができ、そこから、index iへ足す量が決まれば、i+x*Lに足す量も決まっていくことは分かる。が、そこからどうして良いか分からず混乱した。

　（iとi+x*Lの関係に着目するのは良いのだが）Bを作らずに考えた方が良かった。
　上で書いた関係は、A[i]とA[i+L]がmod Mで一致する、ということを意味している。そうすると、もう一つ、sum(A[i:i+L])の和が0になれば条件を満たすことが分かる。

　同等の条件は上の連立方程式から出すこともできる（後者の条件は、B[0]=0ならOKとなる）が、その解釈が分かりにくく混乱しやすい。
　Aのままの方が考えやすかったと思う。

F - All Included

　コンテスト中書いていた実装のバグを直し、ChatGPTにC++に直してもらってAC。

　添え字のミスでした。
　が、コンテスト中も添え字のミスだろうと思って懸命に探したのだが……。

　Aho-Corasick法との関係がよく分かっていないけど、復習した方が良いのかなぁ。

G - Count Simple Paths 2

　解説放送を見てAC。言われてみれば……という感じ。

　ただ、結構高速化を頑張らないとACできなかった。頂点数が22個（くらい）に抑えられるはずなので、C++に直したらTLE取れるはず……と思ったらPyPyより遅くなったりしてよく分からなかった。

　結局、頂点数を削減した後、座標圧縮してbitsetを使ってAC。

時刻: 0 件のコメント:

2025年8月13日水曜日

yukicoder contest 477 線形代数コンテスト

　AHCの途中だったのでCだけ解いた。


No.3225 2×2行列相似判定 〜easy〜

　全探索しか思いつかなかったが、それだとhardで困るんだよね……。

No.3227 Matrix Query

　自力AC。セグ木に乗せた。
　今回は、行列をそのままセグ木に乗せて間に合った。

No.3228 Very Large Fibonacci Sum

　自力AC。行列累乗で解ける。
　慣れてきたと思ったのだが、結構時間がかかってしまった。

No.3229 Liar Game Comibination

　自力AC。
　とりあえず基底を求めて何かするのだろう……と思ったが、よく分からない。しかし、サンプルが2のベキであることを見て、未証明ACしてしまった。

　解説を読めば正当性は理解できるが、SH=0と問題文を言い換えることすらできていなかった。

　
時刻: 0 件のコメント:

AtCoder Beginner Contest 416

　Eまで五完。

コンテスト後のツイート

F - Paint Tree 2

　解説放送を見てAC。

　木DPの遷移で混乱したが、遷移の部分をDPでやると分かりやすいというのはなるほどだった。
　ただ、解説を見て実装した後もしばらくWAが取れなかった。
　原因は、DPの初期値を全て0にしていたため。「そのnodeを含む途中のpathが存在する」という状況は何もない状況より有利なので、0で初期化してはいけなかった。

G - Concat (1st)

　解説放送を見てAC。

　解説の内容を理解はできるが、結構難しく感じてしまった。解けそうだけど解けない問題という感じがする。

　とりあえず、
・同じ文字列なら最小のものを使うべき
　を押さえて、後は実験するべきだったかなぁ。




時刻: 0 件のコメント:

2025年8月6日水曜日

yukicoder contest 476

　E一完だったがコンテスト後にHackされた。


No.3219 Ruler to Maximize

　一応自力ACだけど、bit全探索というタグを見てしまったので地力とは言えないか。

No.3220 Forest Creation

　想定ACコードが元の問題と不整合だったため、問題文が変更されHackされた模様。ただ、元の問題文に対して自分のコードが正しかったのかがはっきりしない。（多分、間違っている）
　概ね合っていたんだと思うけど、よく分からずちょっともやもや。

No.3221 Count Turns

　解説は見ずにACしたが、テストケースを見てデバッグしてしまった。

　問題文を理解するのにちょっと苦労した。
　問題文は正しく書かれていて紛らわしい部分はないのに、理解に苦労するのは数学的なセンスの問題なのかな……。


　どういう操作か分かると、A[i]の値は関係なく、何回でHを超えるか？　さえ分かれば良いことが分かる。これを使ってheapqでシミュレーションをしたらWA。

　もう一回問題文を見返すと、二つ以上の要素がH以上であるならば、最大値がある方を0にしてCに+1すると気付いた。ということは、Hを越えたとき何の値か？　も持つ必要がある。これもheapqに加えるとAC。

No.3222 Let the World Forget Me

　自力AC。

　この問題は簡単。ただ、葉を取り除いたとき新たな葉ができることを忘れて一度実装してしまった。そこまで単純なはずないね。
時刻: 0 件のコメント: