AtCoder Beginner Contest 269 A～Cのメモ
UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)に参加したので記録を書いておきます。
A - Anyway Takahashi
問題文の内容をそのまま実装すればいいです。2行目のTakahashiが謎ですね。
fun main() {
val (a, b, c, d) = readLine()!!.split(" ").map { it.toInt() }
println((a + b) * (c - d))
println("Takahashi")
}
B - Rectangle Detection
A,B,C,Dそれぞれを一つずつ分解して考えればわかりやすいと思います。二次元のデータ構造として考える必要はありません。
文字列のうち、#を含む最初の文字列の位置がAです。
Bは#を含む最後の文字列の位置ですが、そう考えるとちょっとやりづらいです。末尾から見ていった時、#を含む最初の文字列の位置がBと考えるといいです。
それで#を含む行はB - A + 1行ありますが、どの行も#が含まれる個数と位置は全く同じであることが制約からわかります。なので、#が含まれる行のどれか一つを取り出してCとDの位置を調べればいいです。
Cは取り出した行（文字列）のうち#が最初に出現する位置、Dは文字列を末尾から見ていったときに#が最初に出現する位置です。
fun main() {
val s = (0 until 10).map {
readLine()!!
}
val a = s.indexOfFirst { it.contains("#") } + 1
val b = s.indexOfLast { it.contains("#") } + 1
val ss = s[a - 1]
val c = ss.indexOf("#") + 1
val d = ss.lastIndexOf("#") + 1
println("$a $b")
println("$c $d")
}
ゼロオリジンの言語の場合は補正する必要があります。CとDの位置を調べるための行はA番目かB番目を取得すればいいのですが、ゼロオリジンで補正後のAやBを使って取り出すとずれるという点に注意が必要です。
ちょっとそれで危うくミスりかけたので、余分なデータを入れて1オリジンに補正するとかしたほうがいいんですかね…
C - Submask
2進数なのでビット演算ですね。Nが非常に大きいので、全探索だと全然間に合いません。
正直、これは一つの定石っぽかったのでネットの力を借りてなんとかしてしまいました。
fun main() {
val n = readLine()!!.toLong()
var x = 0L
while (true) {
println(x)
if(x == n) {
break
}
x = (x - n) and n
}
}
自力でこれを導き出すのは無理だったでしょうし、理解しているとも言い難いですが、ビット演算についてわかればとりあえず何が起こっているのか把握することならできます。
大雑把に言えば、ビット演算の性質を利用することで、答えとして欲しい数字をピンポイントで全列挙することができるということですね。
ピンポイントに列挙しても、列挙する対象が非常に多ければやはり間に合わないのですが、この問題には「N を 2 進数として表記した時、 1 となる位は 15 個以下である」という制約があるためセーフです。
ビット演算は全部そうですが、10進数で考えると意味不明なので2進数で考える必要があります。
xからnを引いていますが、多くの言語では引き算は負の数を足すという形で実現されていると思います。（たぶん）
それで負の数は2の補数で表現されるのが一般的です。2の補数は、元の数のビットを全て反転してから1を足すことで得られます。
実際には64ビット整数が必要ですが、面倒なので8ビット整数として考えてみます。
例として出ている11で考えます。11を2進数で表すと00001011ですので、11の2の補数は11110101です。11110101は10進数の-11を表しているということなので、これをnと足すことでx - nの結果を得られます。
xの初期値は0なので演算結果はそのまま11110101です。それとnとのANDをとります。nは前述の通り00001011です。
11110101
AND
00001011
AND演算はビットが両方立っている桁だけ残りますので、結果は00000001です。これは10進数の1です。これが次のxとなります。
同様に繰り返していきます。
00000001 + 11110101 = 11110110
11110110
AND
00001011
-> 00000010（10進数の2）
00000010 + 11110101 = 11110111
11110111
AND
00001011
-> 00000011（10進数の3）
00000011 + 11110101 = 11111000
11111000
AND
00001011
-> 00001000（10進数の8）
00001000 + 11110101 = 11111101
11111101
AND
00001011
-> 00001001（10進数の9）
00001001 + 11110101 = 11111110
11111110
AND
00001011
-> 00001010（10進数の10）
00001010 + 11110101 = 11111111
11111111
AND
00001011
-> 00001011（10進数の11）
見づらくてすみません。こんな感じで、2、3、8、9、10、11を列挙できました。初期値の0も入れると問題の出力例1と完全に一致することがわかります。
コードを再掲します。
fun main() {
val n = readLine()!!.toLong()
var x = 0L
while (true) {
println(x)
if(x == n) {
break
}
x = (x - n) and n
}
}
答えはIntをはみ出す可能性があるためLongにします。
Nがいかなる数にせよ、0は答えになりますのでxから0から始めます。答えとなる値をピンポイントで列挙できるため、得られたxはそのまま出力してよいです。ループを抜けるかどうかの分岐だけ必要になります。N自身も必ず答えとして列挙されるので無限ループにはなりません。
なお、これにはfor文を用いるのが定石のようですが、Kotlinには従来型のfor文がないためwhile文で代用しています。
Do use hexagon grid
Cが解けたのでチラ見しましたが、あまり熱心に考察はしていません。グラフとして扱ってDFSとかで解けるっぽいということまでわかりましたが、バグらせずに実装する自信がなく諦めました。
解説ACはしていません。Cが普通に解けるようになってきたらまた挑戦します。
感想
bit全探索は使ったことがありましたが、文字通りの全探索パターンしか知りませんでした。このようにビットが立っているところだけピンポイントに列挙する方法があるのですね。覚えておきたいと思います。
Discussion