2022/9/24に開催された、トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)に参加しました。
前回のABCでは、なんとか連敗を止めることができたものの、増加幅は1桁程度という体たらく。ここ最近は大きくレートを上げることができておりません。
というわけで、今回はなんとか水パフォを突破して、レートを大きく上げていこうという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年9月24日
ここのところ、パッとしない結果が続いているので、ここいらで水パフォ取れるように頑張ります✊
トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) - AtCoder https://t.co/zglZfR5VXt
今回の結果
で、今回はなんとか4完を確保するのが精一杯でした。。
パフォーマンスは、なんとかギリギリ水色に到達。レートは上がりましたが、上昇幅は1桁程度ということで、今回もパッとしない結果になりましたとさ。
まあ、負けるよりはだいぶマシですが。
4完水パフォで勝ち😂
— devgenjin77 (@devgenjin77) 2022年9月24日
次も頑張ります
devgenjin77さんのトヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)での成績：1594位
パフォーマンス：1209相当
レーティング：1119→1128 (+9) :)#AtCoder #トヨタ自動車プログラミングコンテスト2022(ABC270) https://t.co/EdpXJu8XMh
振り返り
Dで方針を誤ってしまい、だいぶ時間をロスしました。
A問題
問題文の言っていることが、すぐには理解できなかったが、配点のパターンを見る限り2進数のビットを表現したもののように見える。
おそらく答えは、をなんらかのビット演算したものと推定。サンプルを試すと、OR演算で行ける模様。
あとは実装して、一発でACを取ることができましたとさ。
2分2秒で1完。
提出コード
https://atcoder.jp/contests/abc270/submissions/35092599
B問題
数直線上の位置関係で分岐させる問題。工夫すれば、シンプルに実装する方法もありそうだが、とりあえず普通に分岐を実装してく方法とってみる。
が正の場合と負の場合、ハンマーが取れる場合と取れない場合、ハンマーが、ゴールと反対方向にある場合とそうでない場合という感じで愚直に実装。だいぶ時間が掛かりましたが、なんとか一度の提出でACが取れました。
10分30秒で2完。ちょっと遅めのタイムという印象。
提出コード
https://atcoder.jp/contests/abc270/submissions/35098743
C問題
根付き木を、頂点からDFSし、途中で通った頂点を記録していくと、頂点
にたどり着いた時に、取っていた記録がそのまま答えとなる。
実装に少し手間取りながらも、一度の提出でACを取り切りました。
27分14秒で3完。
提出コード
https://atcoder.jp/contests/abc270/submissions/35109722
D問題
問題の見た目上、現時点で一番取れる最大の数を取り続ける戦略をとればいいような気がするが、制約の見た目上、そうでもないような気もする。。
とりあえず、最大を取り続ける方針で実装してみる。が、、これはあえなくWA。。。
最大を取り続ける戦略がダメということと、制約から、計算量がになるDPをすれば良いのかと思ったが、DPの方針が思いつかず。
とりあえず、残り40分を切ったあたりで、この問題は一旦諦めました。
E問題
10分以上解法が思いつかずでしたが、あれこれ試行錯誤しているうちに、なんとか解法が降りて来てくれました。
個食べるまでに、かごを何周できるかを二分探索で求め、最後に残った1周分に満たない余りを愚直に計算していけば解けそう。
ということで、あとは実装。当初、二分探索の下限を間違えてしまい、1週未満で個食べ切ってしまうケースでWAを食らってしまいましたが、終了間際でなんとか修正。時間内にACを取り切ることができました。
97分46秒2ペナで4完。3完止まりだと爆死するところでしたが、なんとかギリギリ持ち堪えました（笑）
提出コード
https://atcoder.jp/contests/abc270/submissions/35135836
F問題
問題すら見れておりません。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
前回に続いて、レートは微増。着実に水色への道を進んでおります（笑）
総括
今回は、あわや爆死という場面もありましたが、なんとか持ち堪えることができました。
特に、今回のE問題は水Diffだったようですが、本番でこのぐらいのDiffの問題を通せているのも、最近の地道な精進の成果がでているというところでしょうか。
逆に、D問題の貪欲にみせかけた引っかけにつまづいたのが反省点。もうすこしDPの過去問を解いていくことをしないとなあというところです。
ということで、また次回も頑張ります。
