2025年7月13日日曜日

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

　遅刻参加でEまで。

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


No.3200 Sinking Islands

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

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

No.3201 Corporate Synergy

　色々資料を見ながらAC。

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

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

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

コンテスト後のツイート

F - Jump Traveling

　解説＆解説放送でAC。

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

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

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



時刻: 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 件のコメント:
ラベル:

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