devgenjin77’s blog

Toyota Programming Contest 2023 Spring Qual B(AtCoder Beginner Contest 290)参加記

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

2023/2/20に開催された、Toyota Programming Contest 2023 Spring Qual B(AtCoder Beginner Contest 290)に参加しました。

どうも今回の難易度は、前回の予選A(ABC288)と同じ傾向ということらしいですね。よって、D問題以降が激ムズの予感。

ということで、今回は3完まではなんとか早解きし、D問題を全力で解こうという感じで臨むことにしました。

Rated参加します。前回予選Aでは3完終了だったため、今回は4完できるように頑張ります✊

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290） - AtCoder https://t.co/aiwYea89AZ
— devgenjin77 (@devgenjin77) 2023年2月19日

今回の結果

で、宣言通りなんとか4完達成しました。最近、有言実行ケースが多いような。。

ABC290結果

今回のパフォーマンスは、水色の中ぐらいといった感じ。昨日のARCで結構レートを落としたレートを大分戻すことに成功しました。

4完水パフォでした😃

devgenjin77さんのToyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）での成績：1171位
パフォーマンス：1353相当
レーティング：1118→1144 (+26) :)#AtCoder #ToyotaProgrammingContest2023SpringQualB（ABC290） https://t.co/3rtD1T46df
— devgenjin77 (@devgenjin77) 2023年2月19日

振り返り

Dが意外なほどあっさり解けたのは良いのですが、E問題を解き切ることができなかったのは残念です。

ABC290提出結果

A問題

A - Contest Result

一見した感じ、 $\sum ^{M}_{i=1}A_{B_i}$ を出力すれば良さそうということで、さっさと実装。問題なくACが取れましたとさ。

1分44秒で1完。

提出コード

https://atcoder.jp/contests/abc290/submissions/39011007

B問題

とりあえず、 $S_i$ がxの場合は、出力もx。先頭から数えて $K$ 個目までのoは、そのままoを出力し、以降はxを出力という感じ。

こちらも、特に問題なくACを取ることができました。

4分58秒で2完。

提出コード

https://atcoder.jp/contests/abc290/submissions/39015745

C問題

問題を一読したところ、数列 $A$ に対して、要素 $K$ 個の連続部分列としてありうる数列全てに対して $MEX$ を求めるのかと思いきや、サンプルをみたらそんなことは無く一安心という感じでした。

配列 $A$ の中に、 $0,1,...,K - 1$ が含まれるかを順にみていき、無い数字が存在したら、それが答え。全部ある場合は $K$ が答えという感じで実装。こちらも問題なくACが取れました。

10分57秒で3完。こんなタイムで、1200ぐらいの順位でした。

提出コード

https://atcoder.jp/contests/abc290/submissions/39021012

D問題

一読してみて、やはり少し難しめかという印象の問題。とりあえず、制約を見てると各テストケースごとに $O(1)$ か $O(logN)$ ぐらいで答えないとダメな感じだなあと。

愚直にシミュレーションするのは無理なので、どうすれば高速化できるかを考えないといけない。とりあえず、足がかりを見つけるため、小さいケースをノートで手計算してみることに。

すると、 $N=10,D=7$ など互いに素であるようなペアでは、 $N$ 回の操作で既に印が付いた場所を踏むことは無い模様。 $N=10,D=2$ とかだと、 $5$ 回ごとに既に印が付いた場所を踏む感じになるので、もしかすると $GCD$ がカギになるのではないかと推測。

結局、 $K$ 回の操作で、 $D(K-1)$ 分進み、且つ $(K-1) \div GCD(N,D)$ 回分既に印が付いた場所を踏んで1回前に進むので、これを足し算して $N$ で割った余りを出力することに。

これでサンプルが通ったので出してみたら、見事ACを取り切ることができましたとさ。

34分6秒で4完。スムーズに考察と解法を繋げることができ、個人的には会心のACでした。

提出コード

https://atcoder.jp/contests/abc290/submissions/39030294

E問題

E - Make it Palindrome

だいぶややこしい問題が来たなという印象。だが、時間は大分あるので、一発通してみたい所でもある。

とりあえず、手元のノートで愚直に解いた絵を書いてみることにする。すると、どうもある区間に対する $f(X)$ を求めるとき、両端を除いた $f(X)$ の値に対して１足すかどうかという具合になるのではと推察。

例えば、下の図でいうと、0-indexedで区間 $\lbrack 1,4 \rbrack$ に対する $f(X)$ を計算するときは、区間 $\lbrack 2,3 \rbrack$ に対する $f(X)$ に対して、両端が同じなので１足さないという具合になる。

ABC290E考察

すると、この問題では、2階層下の結果に対して、DPっぽく計算するのが想定ではということで実装。これがサンプルが通ったので出してみると、途中までいい感じで進みましたが、結局TLEしてしまうというオチでした。

WAが無かったので、答えはあっているようだが、計算量が $O(N^{2})$ になるとダメということか。。だいぶいい線行ってると思いましたが、ぬか喜びでした。

結局、効率よく計算しないといかんと言うわけだが、どうにも方法が思いつかず。結局、この問題で時間切れになりました。

F問題

F - Maximum Diameter

チラ見しましたが、何も分かりませんでした。

G問題

G - Edge Elimination

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

Ex問題

Ex - Bow Meow Optimization

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

これまでの実績

1100近辺で行ったり来たりを繰り返しております。早くこの停滞モードを抜けて入水したいところです。

コンテスト実績

総括

結局、今回のD問題は緑Diffぐらいというところで、解けなくてはいけない問題だったようです。またE問題は水Diffで、上を目指すには克服していかないといけない課題というところ。

来週もARCとABC、また平日はAHCの考察と実装という大変忙しいスケジュールですが、いい結果が出せるよう、できる限りの準備をしていこうと思います。

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