第三回日本最強プログラマー学生選手権-予選-（ABC262）参加記

AtCoder 競プロ ABC

2022/7/31に開催された、第三回日本最強プログラマー学生選手権-予選-（ABC262）に参加しました。

atcoder.jp

昨日のARCは所用で出れず。よって今週はこのABCのみでレートが動くということになるので、今回はなんとしてもレートを上げていきたいところ。

とりあえず、目標水パフォで臨むこととしました。

今回の結果

なんとか4完を確保しました。

ABC262結果
ABC262結果

で、なんとかギリギリでしたが、宣言通り水パフォを取得することが出来、レートを上げることに成功しました。

振り返り

凡ミスでペナルティを重ねてしまい、大分パフォーマンスを落としてしまいました。

ABC262提出結果
ABC262提出結果

A問題

A - World Cup

めっちゃ効率的な解き方があるかもしれないかと思ったが、とりあえず早く解くために愚直に実装することに。

Yのmod 4をとって、あとは普通に場合分けをする実装を行い、提出。問題なくACが取れました。

2分7秒で1完。

提出コード

https://atcoder.jp/contests/abc262/submissions/33658725

B問題

B - Triangle (Easier)

グラフ上の連結を隣接リストで扱い、あとは3重ループでカウントしていけば良い。

実装方針は早めに固まったため、問題なくACを取り切ることができました。

6分14秒で2完。

提出コード

https://atcoder.jp/contests/abc262/submissions/33663510

C問題

C - Min Max Pair

iを左から順に固定して考えていくとして、a_i = iの場合は、それより右に存在するa_j = jとなるjが対象となる。

よって、前計算で、i = a_iとなる項をあらかじめカウントして累積和をとっておき、計算することで対処する。

a_i \ne iの場合は、a_{a_i} = iかどうかを判定し、Trueならカウントにプラス1する。

上記のような感じで、問題なくサンプルが通ったので提出したら、結果はWA。。。

原因が全く分からずで、10分近くあれこれ悩みましたが、結局カウント用の変数宣言をintからlongに変えてみることで、AC。。。

29分17秒1ペナで3完。もう2年近く競プロやっているが、こんな凡ミスがまだ治らないのかと、少しショックを受けました。。

提出コード

https://atcoder.jp/contests/abc262/submissions/33673610

D問題

D - Jumping Takahashi 2

大分難易度が高そうだが、modの合計を管理してDPすることで、なんとかやっていけそうな感じがする問題。

ということで、Aの項を何個選ぶかというのを固定して、以下のDPを考えてみる。

  • \ dp\lbrack i\rbrack \lbrack j \rbrack :=M個選ぶ時、Aの項をi個採用して、mod Mがjになる時の通り数。

このDPを、M =2からNのケースでそれぞれ実行していく。

あとは、各DPで、Aから取得した値を選ぶかどうかや、最初の一つ目として選ぶ場合の遷移を実装。とりあえずサンプルまでは通るプログラムができました。

で、ジャッジに投げてみると、半分以上がWA。。。

本気で何が間違っているのかが全然分からずで、あれこれ試行錯誤してみるも、WAが取れずで傷口を広げるばかり。

で、ふと問題文をじっくり読んでみると、 998244353で割った余りが答えになるやつだと今更気づく！

んで、modの計算をまじめにやってみたら、無事ACを取ることが出来ましたとさ。。

C問題の凡ミスもショックでしたが、これは問題文をちゃんと読めば防げるミスなので、ショックを通り越して自分でも呆れてしまいました。。

84分20秒4ペナで4完。とりあえず、順位は1400台に乗ったので、なんとかレート上昇は望めそうなのが、せめてもの救い。

提出コード

https://atcoder.jp/contests/abc262/submissions/33685786

E問題

E - Red and Blue Graph

順位表のAC数をみると、多分青パフォぐらいの難易度かと。

問題文を一読しましたが、何も分からずで降参。このまま時間切れとなりました。

F問題

F - Erase and Rotate

問題すら見れておりません。

G問題

G - LIS with Stack

問題すら見れておりません。

Ex問題

Ex - Max Limited Sequence

問題すら見れておりません。

これまでの実績

一応、レートは上昇しましたが、ここから上に抜けるのが、しんどいんだよなあ。

コンテスト実績
コンテスト実績

総括

今回は、ギリ水パフォが取れましたが、CとDの凡ミスがなければ、もっと上のパフォーマンスが取れていたはず。実力不足というよりは、注意不足が原因でパフォーマンスを落とすのは大分勿体無い感じがしますね。

この手のミスは、以前から、ちょくちょくやらかしているのですが、どうすれば無くせるんだろうか。次回に向けて、少し考えてみたいと思います。

ということで、また次回も頑張ります。