AtCoder Beginner Contest 268 A～Cのメモ
ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)に参加したのでメモを残しておきます。
A - Five Integers
重複を排除した後の配列の要素数が答えになります。重複排除はおとなしく言語の機能に頼ります。
fun main() {
val list = readLine()!!.split(" ").map { it.toInt() }
println(list.distinct().size)
}
B - Prefix?
これも言語の提供する機能に頼ればそのまんまです。
fun main() {
val s = readLine()!!
val t = readLine()!!
if(t.startsWith(s)) {
println("Yes")
} else {
println("No")
}
}
C - Chinese Restaurant
さて個人的に鬼門のC問題です。とりあえず思考の過程を書いてみます。
（※以下はコンテスト中に書いた文章を、コンテスト終了後に公開しています）
要するに、自分の番号と同じ番号の料理が目の前か斜め前にあれば喜びます。その最大人数を求めます。
目の前はともかく、斜め前でも喜ぶなんて変わった人たちですね。それはともかく、わざわざmodなんて書いてあるので、配列の値を実際に見て判定するというよりは、計算で求めるのだろうなとは思いますが。
テーブルを回転させていい回数は0回以上なので、回さないことも可能です。初期位置の状態が最大人数になる可能性もあります。
全探索すればもちろん求められますが、O(N^2)になるのでダメそうです。
数列が来たらソートしたくなりますが、今回の問題では意味なさそうに思いました。料理番号は0～(N-1)で確定しています。
計算量がO(N)なら十分間に合いますが、どうしたらいいでしょうか。初期位置の状態でスキャンして、その時点でそれぞれの人が喜ぶかどうか判定するくらいなら問題なさそうです。その後、テーブルを回転させた時にそれがどのように変動するか、という感じで考えてみます。
まず、実際に回転をシミュレーションする方法で考えてみます。実際に配列の要素を動かしてしまうと計算量がO(N)になりとても間に合わないので、以前見たようなインデックスだけを更新する手法でO(1)で回転をシミュレーションできます。
回転全体の計算量はO(N)ですが、喜ぶ人数の変動の計算をO(1)でできれば間に合うはずです。とはいえ、方法が思いつきませんでした。なんか回転をシミュレーションという発想自体がなんかダメそうな雰囲気を感じます。
となると、計算で求めるということになります。たぶん最初に一回スキャンして計算に必要な情報を取得して、それをもとに計算するのだとは思いますが、どのような情報を取得してどのような計算を行えばいいのかわかりません。
初期位置で喜ぶ人数が絶対答えなら計算しなくていいのですが、全然そうとは限りません。ただ、答えはそれ以上なのは間違いありません。回転によって喜ぶ人数が減ることはありますが、その時の人数が答えになることはありません。その辺りがヒントになるのでしょうか…わかりません。
なんとなくこの問題を想起しましたが、今回は（たぶん）ソートできないので同じ方法で解けるわけではありません。
何個ずらせば喜ぶようになるのかという情報が重要そうではありますが、ここの辺りから計算が必要になりそうなので思考が止まりました。なのでこれ以上考察は進まず断念…
解説を見て
（※ここからはコンテスト終了後に解説を見て書いた内容となります）
ずっと人に着目していましたが、結果としては料理のほうに着目すればよかったようです。料理iで喜ぶのは人iだけです。そして喜ぶ場所は3箇所だけなので、ある料理が誰かを喜ばせる場所は絶対3箇所だけということになります。なので計算が楽だと。なるほど…
それで、人は0から順番通り並んでいることがわかっているので、料理を何回転させたら人が喜ぶかは計算で求められます。擬似コードでいうと、とりあえず料理番号と人番号が一致するまでの回転回数は(Pi - i) mod N です。料理番号のほうが大きいなら単純にPi - iですが、逆かもしれないのでmodをとります。実際には±1も別途計算する必要がありますが。Piやiの最大値はNではなくN-1である点に注意です。
これは頭の中で考えて発想するのはなかなか大変ですが、逆に図でも描けば気づきやすかったかもしれないので、そうすればよかったかな…
喜ばせる回転回数がわかれば、その回転回数の時に喜ぶ人が増えるということになります。なので回転数ごとの喜ぶ人数リストを作って、料理を全部見てその料理が人を喜ばせる回転数に対応する数を1ずつ増やしていって、最後のそのリストの最大値を取ればそれが答えということになります。
提出コードはこちら。
fun main() {
val n = readLine()!!.toInt()
val p = readLine()!!.split(" ").map { it.toInt() }
// 回転回数ごとの、喜ぶ人数を保持する配列
val countTable = IntArray(n)
// 料理に着目して、喜ばせる回数を計算
for(i in p.indices) {
for(j in -1..1) {
val rotate = (p[i] - i + j + n) % n
countTable[rotate]++
}
}
println(countTable.max())
}
countTableはただの配列ですが、意味のある回転回数は0～N-1回なので、ちょうど添字と対応します。
二重ループになっていますが、中のループ回数は3で固定なので誤差で、計算量はO(N)と考えられます。別に3つ並べて書いてもいいです。
注意が必要なのはmodです。負の数に対してmodをとった時の挙動は言語によって異なります。Kotlinの場合はそのまま負の数が返ってきてしまいますが、ここで正の数が返ってきてほしいのでnを足して補正します（足される数が0以上の場合は、nが足されてもmodの結果は変わりません）
あとは最大値をとって終わりです。最大値をとるのもちょっと時間がかかりますがO(N)なので十分間に合います。
感想
Cは解けなかったし、自力で解くにはまだ全然実力が足りないと思いましたが、普段よりは考察が進んだような気がします。以前の自分なら回転のシミュレーションに固執したと思いますので、それだとダメそうと気づいただけでも前進しています。なんともレベルの低い話ですが、まあ前進は前進なのです。
しかし料理のほうに着目すればよかったとは思いもよりませんでした。こういう発想が全然できないです。それとmodの使い方。今回ヒントとして露骨にmodが推されてたのに、それでもmodを使えばいいというのがピンときませんでした。
とりあえず、たくさん問題を解いて感覚を養っていくしかないのでしょうね。
Discussion