devgenjin77’s blog

第四回日本最強プログラマー学生選手権-予選-(AtCoder Beginner Contest 313)参加記

AtCoder 競プロ ABC 企業主催コンテスト

2023/8/5に開催された、第四回日本最強プログラマー学生選手権-予選-(AtCoder Beginner Contest 313)に参加しました。

今回は通常のABCとは異なり、ARC仕様の難易度ということだそうです。

５完狙うのは厳しいのかなという感じですが、とりあえず最善を尽くせば水パフォは取れるかという感じで挑んでみます。

Rated参加します。配点が今までのABCとちょい違う感じですが、水パフォ目標で頑張ります。

第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313） - AtCoder https://t.co/JgLYsvdN11
— devgenjin77 (@devgenjin77) 2023年8月5日

今回の結果

今回も４完を確保！残り30秒での滑り込みACで、なんとか順位を大幅に上げることができました！！

ABC313結果

結果は余裕の水パフォでレートは大幅に上昇。再度、入水までもう少しというところまで来ました。

４完水パフォでした😂😂
devgenjin77さんの第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）での成績：1131位
パフォーマンス：1479相当
レーティング：1141→1180 (+39) :)#AtCoder #第四回日本最強プログラマー学生選手権-予選-（ABC313） https://t.co/MZocgpVERA
— devgenjin77 (@devgenjin77) 2023年8月5日

振り返り

ギリギリの滑り込みでD問題を解き切ることができました。

ABC313提出結果

A問題

A - To Be Saikyo

一瞬、 $P_i - P_1$ の内最大の非負整数を出せば良いかと思ってましたが、これが勘違い。少しタイムロスしました。

$1 \lt i \le N$ について、 $(P_i + 1) - P_1$ の最大値が答え。答えがマイナスの場合は $0$ を出す実装で提出して、問題なくACが取れました。

2分38秒で1完。

提出コード

https://atcoder.jp/contests/abc313/submissions/44256995

B問題

B - Who is Saikyo?

愚直にそれぞれの関係性を整理しようとすると、大分難しい実装が必要かという印象。しかし、結局は誰かより弱いという情報がない限り最強の可能性があるのでは。。

結局、 $B_i$ にいない人が１人だったらその人を答えとし、そうでなければ-1を出す実装で提出。問題なくACが取れました。

8分28秒で2完。

提出コード

https://atcoder.jp/contests/abc313/submissions/44264969

C問題

C - Approximate Equalization 2

操作が完全に終了した整数列の合計は、整数列 $A$ の合計と一致する。
操作が完全に終了した整数列の要素は、全て $A$ の平均値を切り下げした値を設定した後、 $A$ の合計を $N$ で割った余りの要素数について $1$ を加えておけば良い。
後は、整数列 $A$ と操作が完全に終了した整数列をそれぞれソートし、各要素間の差の絶対値の合計を $2$ で割ったものが答え。

こんな感じの実装でACが取れました。18分5秒で3完。

提出コード

https://atcoder.jp/contests/abc313/submissions/44272496

D問題

D - Odd or Even

着手時点で、100AC行ってないぐらいの問題なので、大分手強いかなあという印象でした。

とりあえず、長時間かけて色々考察したりしたので、以下に内容を整理。

$K = 1$ の場合は、質問の結果をそのまま答えに設定すれば良い。
$K \ne 1$ の場合は、質問の出し方を $(i, (i + 1) mod N, ... , (i + k - 1) mod N)$ を全ての $i$ について出すという感じにすれば、 $A_i$ と $A_{i + k mod N}$ が同じがそうでないかが分かる。
$gcd(N,K)=1$ の場合は、上記の質問の後、 $A_0$ を $0$ か $1$ で固定すれば、各要素の値が確定するので、後は質問の結果と矛盾しない方を答えにすれば良い。
$gcd(N,K) \ne 1$ の場合はどうするか？散々悩んだ結果、 $M$ を $GCD(N,M)=1$ となる $N$ 以下の最大の整数と定義することで、先頭から $M$ 個までの要素を前述のやり方で計算。残りは、求めたい要素とすでに確定している要素を交えて質問することで決めていけば良い。

と、上記のような方針で実装してみることに。

これが、実装にやたら時間がかかったのと、テストが大変だったことで、気がつけば終了の時間が迫っていたのですが、残り１分を切ったところで、出来上がったところまでをダメ元で提出。

で、、これがなんとも嬉しい一発ACという結果になりました！！

99分31秒で4完。今までの競プロ経験の中でも、上位に入る会心のAC。最後まで諦めなくて良かったという感じです。

提出コード

https://atcoder.jp/contests/abc313/submissions/44306663

E問題

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

F問題

F - Flip Machines

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

G問題

G - Redistribution of Piles

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

Ex問題

Ex - Group Photo

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

これまでの実績

再度、入水が見えるところまで戻してきました。

コンテスト実績

総括

今回のDは青Diffだったということ。本番で青が解けたのは久しぶりなので、嬉しいです。

念願の入水については、順調に水パフォを取り続けることができれば、後１回か２回で達成できそう。

ここまで、入水間際まで上げてからレートが暴落するということを繰り返していましたが、今回こそ突破できるように日々精進を続けていこうと思います。

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