2020/10/11に開催されたAtCoder Regular Contest 105に参加しました。
ARCの参加は先週に続いて2回目になります。
前回の感想としては、最初の2問ぐらいがABCの前半レベルで、あとはめっちゃ難しいという感じなんで、今回は2完ノルマで臨んでみることにしました。
AtCoder Regular Contest 105 - AtCoder https://t.co/z5g6mQp9Zh
— devgenjin77 (@devgenjin77) 2020年10月11日
参加します。最低2完、出来れば3完以上てな感じの目標で。
今回の結果
で、今回の結果はノルマ通りの2完終了となりましたー。
緑パフォだったので、レーティングはプラス。連日のHighest更新となりました。
devgenjin77さんのAtCoder Regular Contest 105での成績：1746位
— devgenjin77 (@devgenjin77) 2020年10月11日
パフォーマンス：900相当
レーティング：626→659 (+33) :)
Highestを更新しました！#AtCoder #ARC105 https://t.co/h6gaKvhdwQ
この土日でそこそこ上がりました。もっと上にいけるように精進します。
振り返り
前回と同じく、C問題以降は歯がたたずでした。
A問題
が与えられる。そこから1つ以上の数を選んだとき、選んだ数の和と選んでいない数の和が同じになることがあるかという問題。
一目上手い解法が思いつかないので、とりあえず愚直でやることに。
もらったを配列につっこんでソートしてから、以下の判定をしました。
- 一番大きい数と、残りの数の和が一緒ならYES
- 一番目と二番目に大きい数の和と、残りの数の和が一緒ならYES
- 一番目と三番目に大きい数の和と、残りの数の和が一緒ならYES
- 一番大きい数と一番小さい数の和と、残りの数の和が一緒ならYES
- 上記の条件にあてはまなければNO
他の上手いやり方もあるかと思ったが、考えてる時間もないので、ゴリ押しで実装してAC。
B問題
これも上手いやり方がわからんので、愚直にシミュレーションすることに。
配列を読んでいって、数字とその個数をそれぞれTreeMapのKeyとValueで管理していく。最大値
はlastKey()、最小値
はfirstKey()でそれぞれ取得できるので、あとは、問題にある通り随時最大値のカードを
に書き換えていく。
この処理を続けて行って、Mapのサイズが1になったら終了。
大分愚直な実装で、実際提出したら、結構反応が鈍い。あわやTLEあるかとヒヤヒヤしましたが(笑)、なんとか1.7秒台で終わってくれました。
後日もっといい解法がなかったか調べたいと思います。
C問題
この問題から全く歯がたたず。
考察としては、ラクダの数の最大が8とかなので、橋のパーツの数とラクダの数で2次元配列作ってDPすればいいんじゃね？的な雑な考えしか浮かばずでした。
結局、それっぽい実装をしたものの、サンプルの4分の2しか通らずで結局提出できず。
他の問題もチラ見しましたが、そのままCに時間を費やしてタイムアップとなりました。
D問題
Nimというのは、以前のコンテストでも題材に上がって居たやつで、全部の山の数のXORをとって結果が0だとどっちかが必勝(うろ覚え)という知識ぐらいしかありません。
問題文に少し目を通しましたが、これならCの方がやれそうかな？という根拠のない自信が出てきたので、パスしました。
E問題
問題文だけチラ見して退散しましたー。
F問題
F - Lights Out on Connected Graph
Eと同じです。
これまでの実績
一応Highestですが、今の実力だと、いいとこ緑←→茶を行ったり来たりする未来しか見えないです。
総括
ゴリ押しでなんとかなる問題ぐらいしか解けてない感があります。
高レベルの問題もコンテスト中に解けるように精進していくしかないですね。
また、次回も頑張ります。
