2025年7月21日月曜日

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

　Cまで三完。DとEはできなくてはいけない問題だったよう。

コンテスト後のツイート

E. Greedy Grid Counting

　コンテスト中書いていた方針でAC。
　実装ミスがあったためデバッグは結構大変だったけど、コンテスト中考えていたことは正しかった。

　右上と左下のマスをペアで見ると、「左回りルートが右回りルートをいくつ上回っているか？」（これが0未満になるとダメ）が分かり、この値を持ってDPできる。
　この値は高々kなので、計算量はn*k*kで収まる。

　累積和を使えば計算量がn*kに落とせるはず……などと考えたのが時間を食った原因か（実際落とせるはず）。ただ、そのときは状態数がkより大きくなる（n*kになるのでは？）と思っていたから考えてしまったのだけど。

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

2025年7月20日日曜日

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

　全完して黄色復帰。良かった！

　一時期（今年はじめ～四月ごろ）、ABCで良いパフォーマンスを出すのがかなり難しくなった気がし、黄色に戻れるか不安に思っていたのだけど、ここ数回はそれほど厳しくない気もする。

コンテスト後のツイート




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

2025年7月19日土曜日

yukicoder contest 474

　A一完。
　10分以上Bを考えても何も思いつかず、疲れているんじゃないか？　と思い寝てしまった。起きたらすぐ思いついたので、本当に疲れていたのかも。


No.3204 Permuted Integer

　自力AC。

　コンテスト中は、「事前列挙するのは良いが、8桁の数を並び替えたら8!個必要だし……」などと考え分からなくなってしまった。

　今回は、sortした文字列で持っておけばOK。クエリ毎に調べる際も、その数字のstrをsortした文字列がどの数を作れるか？　と考えれば解ける。

No.3205 Range Pairwise Xor Query 

　自力AC。

　各bitごとに考えればOK。これは迷わなかった。

No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑

　大体自力だけど、どこかで全方位木DPというキーワードは記憶に残っていた。

　全方位木DPで検索し、このときの自分のコードを使ってAC。
　しかし、このコードのUPとDOWNが何を指しているか分かりにくくて時間がかかった。
時刻: 0 件のコメント:
ラベル: ,

2025年7月13日日曜日

yukicoder contest 473 第1回 生成AI作問コンテスト

　遅刻参加でEまで。

　AIでこれくらいの問題が作れるのか、という思いもあるけれど、実際に作ったときのプロンプトを見るとかなり苦労しているのが分かるので、現状だと、AIによって時間節約になるか？　にはあまりならないのかなぁ。


No.3200 Sinking Islands

　自力AC。
　後ろから見るのはすぐ分かったけど、何を求めれば良いか（後ろから見たときの答えの求めかた）が分からなくなり間に合わず。

　落ち着いて考えれば難しくないが、残り五分では解けなかった。……とはいうものの、五分で解けて良い問題だと思うので、ここで詰まったのは良くなかった。

No.3201 Corporate Synergy

　色々資料を見ながらAC。

　燃やす埋めるだと分かってからも時間がかかってしまった。
　特に「Aが赤でBが赤だとC円報酬」の形のときどうするかが分からず調べた（参考：ここやここ）。このときは頂点を追加すれば良いのね。

No.3202 Periodic Alternating Subsequence

　解説AC。生成AIが作った問題を解けなかったのは良くないねぇ。典型といえる内容だし。

　制約から行列累乗を使いそうとは分かるが、そこへもっていけなかった。つまり、K=1の場合のDPが構成できなかったということ。

　こういう、スコアが二乗の形で表される問題は、二乗という特性を使って何かすることが結構あるが、上手く使えず解けていないことが多い。とりあえず、l^2が(l+1)^2になったらどうなるか？　というのを式で書き眺めて見なくてはいけない。
時刻: 0 件のコメント:
ラベル: ,

ミラティブ プログラミングコンテスト2025（AtCoder Beginner Contest 414）

　Eまで五完。
　またレートを落としてしまったが、大失敗というわけでもないので……。

コンテスト後のツイート

F - Jump Traveling

　解説＆解説放送でAC。

　後一歩で解けたのではないか？　とコンテスト終了時には思っていたが、本質が分かっていなかった。

　ウニグラフのときの遷移の処理が難しいが、各頂点について、「その頂点についてk歩目に行く」というのは二回遷移してあれば十分、というのがポイントで、それで計算量を減らすことができる。

　言われてみれば分かるが、思いつきにくい計算量の減らし方だった。
　辺属性のDPを考えているとき、頂点の出入りで計算量を減らせる、というのは気付きにくい。


G - AtCoder Express 4

　解説放送を見てAC。

　「区間に辺を張るテク」は聞いたことはあった気もするが、内容は覚えておらず、今回初めて実装した。
　理解するのは難しくないが、実装は結構面倒くさいね。
時刻: 0 件のコメント:
ラベル: ,

2025年7月7日月曜日

Codeforces Round 1035 (Div. 2)

　Cまで三完。
　Cまでが遅かったのは集中力が足りなかったせいだけど、Dは普通に難しかった。


D. Token Removing

　解説AC。

　色々見たけれど、一番参考にしたのはmaspyさんの解説でした。
　（制約を見ると）二乗のDPっぽいことは分かるし、後ろから見ると良さそうとも考えた。しかし、そう思っても上手くいかなかったし、解説を理解するのもかなり時間がかかった。

　なんというか、問題を整理して把握する能力が足りてなさそう。
　とはいえ、（自分に合った）解説を読めば理解できるのだから、改善の余地はあるはず……。
時刻: 0 件のコメント:
ラベル:

2025年7月3日木曜日

AtCoder Beginner Contest 396

　Fまで。

コンテスト後のツイート

G - Flip Row or Col

　解説放送を見てAC。

　一回解説放送を見も二回できず、もう一度見返してAC。それほど難しい考え方ではないはずなのだが、理解に苦労した。
　なお、アダマール変換は（アダマール変換を使う解法も）理解できていない。




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

Codeforces Round 1034 (Div. 3)

　ギリギリ全完。

　Cが難しかったのだが、難しかったといっている人が少なかった……。

　Gは、最初の提出がTLEになったとき諦めかけたが、STATUSを見るとPyPyでもACがたくさんあったので高速化した。一番きいたのは無意味なgcdをなくしたところ。gcdのlogは軽いから関係ないかな～と書いていたが、オーダーレベルでの改善であれば効果があった。

コンテスト後のツイート





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