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

2024年12月31日火曜日

AtCoder Beginner Contest 386

　Eまで。

コンテスト後のツイート


F - Operate K

　最長共通部分列のDPと同じようにDPすればACできた。コンテスト中はなぜもっと捻った方法を取ろうとしてしまったのか……。（Sのindex iまで使い、K回まで操作を行ったとき、Tをどこから操作できるか？　と考えていた）
　大いに反省。

　ただ、面倒がってDPをCounterで書いたらTLEし、RUSTのHashMapでもTLEだった（TLEが増えた）。こういうの、ちゃんとリストで書かないといけないんですね。


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

Educational Codeforces Round 173 (Rated for Div. 2)

　Dまで四完。


E. Matrix Transformation

　解説は理解したが、貪欲でAC。

　公式解説の方法は、「ある操作の後に別の操作がある」という条件がいくつも現れるので、グラフにし、トポロジカルソートしてループがないか探すというもの。

　しかし、貪欲に、行と列の操作を交互に31回行って一致すればYes、としてACしているコードがあった。
　確かに、上記のような条件は、min(行の数, 列の数)しか現れないので、n×m≤1000 という制約があるため、これで良い。

　コンテスト中は貪欲方針を書いて、二回しか回さずにWAを出していた。貪欲でいけるかも？　と考えるのは良いけど、正当性も全く思いついていないのでダメですね。
　また、bitずつやらなくても実装できるところを、bitずつやって定数倍が遅い実装になっていたのもまずい。
時刻: 0 件のコメント:
ラベル:

2024年12月30日月曜日

AtCoder Grand Contest 070

　一問も解けず。

コンテスト後のツイート

A - Multiples in the String

　解説AC。

　巡回数に関する知識が必要だった。知っていれば解けるというほどではないが、知らなくて解くのは非常に困難。
　コンテスト中は、X=int("001"*18)のようなとき上手くいかないか？　などと考えていた。

　ただ、ふと、このコンテストはAGCなんだから、何かもっと数学的な構造が背景にあるのでは？　と思ったときもあった。それをもとに検索したりもしたのだが、検索の仕方が悪かったようだ。
　





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

2024年12月24日火曜日

Codeforces Round 995 (Div. 3)

　Fまで六完。Gは、コンテスト後にChatGPTにRUSTに直してもらってACしました。

コンテスト後のツイート




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