2022/10/2に開催されたAtCoder Regular Contest 149に参加しました。
昨日のABCでは、緑パフォで冷えという残念な結果でした。
今回のARCでは、気持ちを切り替えて、最近停滞気味のレートを一気に上げようということで、目標は高く3完を目指そうという気持ちで臨むこととしました。
Rated参加します。目標は高く、3完目指して頑張ります✊
— devgenjin77 (@devgenjin77) 2022年10月2日
AtCoder Regular Contest 149 - AtCoder https://t.co/DyhnY6pxWg
今回の結果
早いうちに2完を達成できましたが、3完を達成することはできませんでした。
しかしながら、パフォーマンスは水色の中盤あたりまで出てくれまして、最近停滞気味のレートも大きく上昇させることが出来ました。
2完でしたが、水パフォまで出てくれてなんとか勝利😂
— devgenjin77 (@devgenjin77) 2022年10月2日
来週も頑張ります！
devgenjin77さんのAtCoder Regular Contest 149での成績：1063位
パフォーマンス：1330相当
レーティング：1112→1136 (+24) :)#AtCoder #ARC149 https://t.co/QhjDBneKLz
振り返り
C問題を解き切ることが出来ませんでした。
A問題
検討したところ、dpっぽくやれば解けるかもということで、以下のdpを考えてみる。
進数で
を
個並べた数字を
で割った時の余り
遷移は、
の大きい順から見ていき、
となる
あとは実装して、一回でACを取る事ができました。
16分54秒で1完。この時点でAのACが900以上ぐらいだったので、少し出遅れた感あり。
提出コード
https://atcoder.jp/contests/arc149/submissions/35348563
B問題
一読して、問題の意味は分かるものの、解法自体はすぐには思いつかず。。
とりあえず、考えた感じ、並び替えは何回でもできるので、数列のどちらかのLISは
として最大化できるはず。
ということは、全体をソートした時の
のLIS
か、
全体をソートした時の
のLIS
の大きい方が答えになるような気がする。
思いつける解法がこれぐらいしかないという感じだったが、この解法で実装してみたところサンプルまでは通ったので提出。なんとか一発でACを取り切ることができました。
38分18秒で2完。エスパー解法が大当たりで助かりました（笑）
因みに、公式解説によれば、全体をソートした時の
のLIS
だけでよかったようです。
提出コード
https://atcoder.jp/contests/arc149/submissions/35351153
C問題
奇数＋奇数や偶数＋偶数の組は絶対に素数でないことから、この特性を上手く利用するのかなあと思ったが、上手い使い方が全く思いつかず。
とりあえず、全く解法が思いつかないので、苦し紛れの実装でなんとかならないか試してみる。
～
の数字をランダムソートしてキューに突っ込み。左上のマスから順番に値を決めてみて、隣接するマスの値との和が素数なら、キューから取り直してみるという、いわば運試しのような実装。
が、、のケースを走らせてみると、てんで通らないので、適当に決めたらどうもダメみたいという知見だけを得て終了。
その後も、色々試行錯誤しましたが、結局解き切ることはできずで、時間切れとなりました。
コンテスト終了後、解説を見たところ、やはり冒頭の特性を使うのが正解だったようだが、使い方が全く思いつかなかったものでした。結局考察力が足りなかったということですな。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
大きくレートは上昇。水色への道を着々と進んでおります。
総括
今回は、エスパー解法が当たってくれたおかげで、大きなレート上昇を勝ち取りました。
しかし、これで満足していては、次回のARCで大負けをしかねないですな。
10月はARCが連続であるようなので、ここで大きくレートを上げられるように準備していきたいと思います。
ということで、また次回も頑張ります。
