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

2024年12月21日土曜日

Codeforces Round 994 (Div. 2)

　Cまで三完。

コンテスト後のツイート

D. Shift + Esc

　ツイートした解法でC++なら一応ACできたわけだけど、もっと簡単かつ計算量の良い解法があった。

　shift回数全部試してDPすればsetなど必要ない！

　shift回数を全部試すのは最初に考えたと思うのだけど、その中でDPすることを思いつかなかったのだと思う。累積和をとって全探索のm*mかかると思ってしまった。
　しかし、言われてみるとDPするのは自然で、これをに気付かなかったのはダメ。
時刻: 0 件のコメント:
ラベル:

2024年12月20日金曜日

Codeforces Global Round 28

　Eまで五完。

コンテスト後のツイート

F. Kevin and Math Class

　自力AC。
　コンテスト中の提出を自明な高速化し、答えが0の場合を場合分けしたら通った。これは想定なのか？

→想定じゃなさそう。何回操作したか？　をforループの最初に回すことで二乗になる模様（こたつがめさんの放送の振り返りを参考に）。これに気付いていなかった。



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

2024年12月19日木曜日

HACK TO THE FUTURE 2025 （AtCoder Heuristic Contest 040）

　pretest166位、システムテスト210位。
　かなり時間をかけ、苦労した割には振るわなかった。

コンテスト後のツイート

　うーむ。

　悪い順位というほどではないが、かけた時間を考えると悲しい成績だった。
　解説放送を聞くと（標準偏差を減らす部分以外）似たような考察をしている部分が多く、何が悪かったのか分からず復習しようと考えた。

　しかし、解説放送の方法や、他の人の方法を導入しても（いくつかのテストケースでのスコアは上がるのだが）ほとんど順位を上げることはできず、非常に厳しい気持ちに。

　段差上になっているのを置いたブロックによっていくつか合体させたり、分割させたり、ということをしている（特に実装に苦労した部分）のだが、それと評価値の相性が悪いのかもしれない……などということは思ったが、その頻度を減らしたからといってスコアが上がるわけではなかった（上がったテストケースもあるが、下がったものもあった）。

　コンテスト後も結構頑張ったのだけど明快な結論は出せず。ここを直したら良かった……などと分かるものではなさそうということは分かった。難しい。

　あまりに時間を掛け過ぎているので、この辺で切り上げます。


（12/21追記）

　と思ったけど諦めきれずやってしまった。
　自分より下の段とのmerge処理・分割処理をばっさり切ったら本番60～80位くらいのスコアは出た。

　今回は誤差があるため、（標準偏差を減らす方向で頑張るのでないのであれば）ビームサーチで多様性があることが大事。厳密に、どんな段差になっているか？　を考えるより、多様性がある段差を最後に出力するため、似たような状態が多くならないよう工夫するべきだった。




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

2024年12月18日水曜日

トヨタ自動車プログラミングコンテスト2024#8（AtCoder Beginner Contest 365）

　Eまで五完。

コンテスト後のツイート

G - AtCoder Office

　一応自力AC。

　上手い解法が思い浮かばず、平方分割とかなのかな？　と考えていたら、マージテクみたいにして解く方法に気付いた（物理好きさんの別解と同じ方法）。

　ただ、同じ(x, y)が飛んでくると思わなかったためTLEする提出をしてしまった。そして、それを修正してもPyPyだとTLEしてしまい、ChatGPTにRustに直してもらいAC。ただ、ChatGPTさんが勝手にロジックも変えてしまっていたため、さらに修正しなくてはいけなかった。こういうの気付くの難しい。AtCoderで与えられている書式みたいに、忠実に変えて！　とかお願いした方が良いのかなぁ。
→　RUSTへの翻訳だとコンパイルエラーが出てしまった。C++へ翻訳してもらう方が良いかもしれない。
時刻: 0 件のコメント:
ラベル:

2024年12月17日火曜日

トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）

　Fまで六完。

コンテスト後のツイート

G - Abs Sum

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

　Mo’s algorithmは考えたのだが、差分更新の方法が分からなかった。ソートしてある配列のどこへA[x]を差し込むか？　みたいに考えていたため、平衡二分木がいるのでは？　などと考えてしまった。
　sortedsetが必要そうな問題で、実はBITで事足りるということは良くある。その方針で検討しなくてはいけなかった。

　Mo’s algorithmの分割個数をどうすれば良いかは謎。
　今回は、分割する個数をかなり小さくしたら通ったが、計算上の計算量は増えているはずだし、いつもそれで良いかは分からない。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Round 993 (Div. 4)

　G2まで。

コンテスト後のツイート

H. Hard Demon Problem

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

　何か特殊な方法を使うのかと思い悩んでしまったが、普通に累積和などで解ける問題でした。これは思いつかなくてはいけなかった。
　実装では、添え字を合わせる部分で結構苦戦しました。

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

2024年12月1日日曜日

AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）

　Gが解けなかったのは仕方ないとして、Eが解けないのはまずい。

コンテスト後のツイート


 E - Expansion Packs

　解説放送を途中まで見てAC。

　何度もやっているにもかかわらず「期待値DP」がまともにできていないことを反省。

　「一回でx枚レアを引く確率」はコンテスト中に問題なく求められていた。それを利用して、x回操作したとき、レアをy枚もっている確率をDPしようとしたのが筋が悪い。期待値をそのまま持つ方が自然で、それで答えが出せる。

　さらに、期待値DPといわれても立式できなかったのが情けない。
　DP[i]を、「残り枚数がi枚のとき、ゴールへ至る日数の期待値」と定義すれば、自然に期待値DPできる。

　

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