れとろのメモ置場

とあるSEのメモ置場

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)に参加しました。

結果

A,B,Cの3問正解でした。

C問題は問題を読むと難しそうな気がしたので先にD問題を見て、解けそうな気がしたからDから先に解いてみたけど失敗だった...
問題を読んだときの第一印象と違ってC問題は簡単だったし、逆にD問題は難しかった。最終的にD問題はACできなかったのでD問題にかけた時間は丸々無駄になったし順位もそこそこ落ちちゃった。

A - Five Integers

入力された整数の種類数を答える問題。

整数をsetに入れていき、setのサイズを答えれば良い。
setを知っているかどうかがポイントな気がするけど、A問題にしては難しい気がする。

B - Prefix?

問題文の通り解いていけば良い。

各文字列の先頭からSの文字数分だけ順番にSとTのi番目の文字が一致するかどうかを確認すれば良い。不一致な文字が出たらNoが確定するし、 Sの末まで確認が終わればYesになる。

ループと文字の比較がわかれば解ける問題。

C - Chinese Restaurant

問題文を読んだ第一印象と少し考察しての難易度が少し違った問題。

愚直に考えると、1ずらした場合はどうなる、2ずらした場合はどうなる、・・・N-1ずらした場合はどうなるを計算して最大値を答えれば良さそう。 ただ、Nが最大2 \times 10 ^ {5}でこの方法だとO(N ^ {2})になるのでTLEになる。

少し考えてみて、ある料理p _ {i}に注目してみると、この料理は位置p _ {i}-1, p _ {i}, p _ {i}+1のどこかの位置にいれば人iは喜ぶことになる。 具体例として料理p _ {i}=4とすると、この料理は3,4,5のどこかに位置にいれば人4は喜ぶ。

つまり、今位置iに料理p _ {i}があるのでp _ {i}-1-i, p _ {i}-i, p _ {i}+1-iの3通りのどれかだけズレせば人iは喜ぶ。 N個の料理全部対して上記を計算して、何回ずらせば喜ぶ人が1番多いかを数えれば答えが求まる。 3通りの計算はO(1)でできるし、料理N個分の処理はO(N)でできる。計算後の結果確認もO(N)でできるので最終的にO(N)で問題が解けることになる。O(N)だとTLEしないのでACできる。

D - Unique Username

簡単そうに見えて難しい問題だった。最終的な解き方の方針は解説と同じだったけどどこかがバグっててWAになった…

順番は自由にN個の単語を1個以上の_で連結した文字列の内、事前に指定された文字列以外のものを1つ出力する問題。 問題文を読んだ思いついた処理の大雑把な流れは以下になる。

  1. 文字列を作る。
  2. 禁止文字列リストに含まれるかどうかを確認する。
  3. 文字列を出力するか1に戻る。

文字列を作る部分では文字列の順番はnext_permutationを使えば全通りの並び順に対応できる。 作った文字列が指定された文字列リストに含むかどうかはリストの最大数が10 ^ {5}になることから線形探索ではなくて2分探索を使うのが良さそうだと思った。

ただ、単語同士は1個以上の_で連結するというのが思っていたよりも厄介だった。 最終的に文字列候補を作る処理を関数として切り出して実装して、用意した文字列1つずつに対して上記の2の処理を行った。

方針は合っているはずなのにいくつかのテストケースでWAになった…