AtCoder Beginner Contest 278 参加記

2022/11/19に開催されたAtCoder Beginner Contest 278に参加しました。

先週のABCは、D問題でバグらせたり、E問題で時間がなかったりと散々な内容で爆死しました。今回はその負け分をすこしでも取り戻そうという気持ちで臨みました。

Rated参加します。前回3完という残念な結果だったので、今回は取り返せるように頑張ります。

AtCoder Beginner Contest 278 - AtCoder https://t.co/PxgcGNqcmJ
— devgenjin77 (@devgenjin77) 2022年11月19日

今回の結果

なんとか5完を確保！しかし、順位表からみると少しイマイチという感じの結果でした。。

なんと5完でもパフォーマンスは緑色。。レートは微増しましたがパッとしない結果でした。

なんとも昨今の参加者のレベルの上がり方がすごいなあという感想しかありません。

5完緑パフォで、レーティングは微増しました😅
最近、参加者のレベルが上がっているのを感じます。もっと頑張らねば。

devgenjin77さんのAtCoder Beginner Contest 278での成績：1724位
パフォーマンス：1151相当
レーティング：1105→1110 (+5) :)#AtCoder #ABC278 https://t.co/dfJuQvb7qW
— devgenjin77 (@devgenjin77) 2022年11月19日

振り返り

時間があれば6完行けるかという感じでしたが、及ばず。

A問題

A - Shift

A問題にしては、だいぶややこしい問題を持ってきたなあという印象。

実装方法は色々考えられるが、とりあえず、配列 $A$ を先頭から最大 $K$ 個分を読み飛ばしてから同サイズ配列に入れ直すというやり方で提出。

少し実装に時間をかけてしまいましたが、無事ACが取れました。

5分12秒で1完。

提出コード

https://atcoder.jp/contests/abc278/submissions/36602946

B問題

B - Misjudge the Time

問題の意図を把握するのに少し時間がかかったものの、やることは時刻を1分ずつ進めて、それが見間違えやすい時刻になるかというのを全探索すれば良いだけ。

こちらも、提出1回で問題なくACが取れました。

13分52秒で2完。

提出コード

https://atcoder.jp/contests/abc278/submissions/36609023

C問題

C - FF

グラフ問題にするのかと思ったが、制約を見てみると、 $N \leq 10^{9}$ なので、Mapで管理するような感じになるのかという印象。

//キー：ユーザーID、値：フォローしているユーザーIDの集合
HashMap<Integer, HashSet<Integer>>

上記のマップオブジェクトでフォロワーを管理。クエリ $1, 2$ の時に更新を行い、クエリ $3$ の時に相互フォローしているかチェックする。

この実装でなんとかACを取り切ることができました。

24分38秒で3完。

提出コード

https://atcoder.jp/contests/abc278/submissions/36615660

D問題

D - All Assign Point Add

当初クエリ $1$ は、 $A$ の全要素に $x$ を足すものと誤読したので、余計な時間を取られてしまいました。。

で、配列のすべての要素に代入するということで、遅延セグ木を使うような問題かと一瞬思いましたが、それは流石にオーバーかと。

ということで、とりあえず以下の解法で実装してみることに。

クエリ $1$ が現れた回数と、直近のクエリ $1$ で与えられた $x$ を覚えておく。
長さ $N$ の配列 $B$ を用意し、 $A_{i}$ はクエリ $1$ の何回目の値に基づくのかを管理する。
クエリ $2,3$ では $A_{i}$ を参照する時に、 $B_{i}$ をチェックし、クエリ $1$ の出現回数と合う場合はそのまま計算。合わない場合は、直近のクエリ $1$ の値を元に計算しなおす。