AtCoder Beginner Contest 282 A～Dのメモ
HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)に参加したので記録を残します。
A - Generalized ABC
1からKまでのリストを作ってそれを半角英大文字に変換して結合します。
fun main() {
val k = readLine()!!.toInt()
val ans = (1..k).map { it.plus(64).toChar() }.joinToString("")
println(ans)
}
ASCIIコードとしてはAが65でそこから連続しているので、各数値に64を足したものをCharに変換すればいいです。そのAが65というのを覚えていなかったので慌ててググりました。
しかし、今思えばそんなことせずとも普通にCharのRangeを作ればよかったのでは…
fun main() {
val k = readLine()!!.toInt()
val ans = ('A'..'Z').toList().subList(0, k).joinToString("")
println(ans)
}
B - Let's Get a Perfect Score
まず二重ループで組み合わせを列挙し、その上で一文字ずつ見ていって少なくともどちらか一方が'o'かどうかを判定しました。
fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInts() = readStrings().map { it.toInt() }
fun main() {
val (n, m) = readInts()
val s = Array(n) {
readString()
}
var ans = 0
for(i in 0 until n) {
for(j in 0 until n) {
if(i == j) {
continue
}
var flg = true
for(k in 0 until m) {
if(s[i][k] == 'o' || s[j][k] == 'o') {
} else {
flg = false
break
}
}
if(flg) {
ans++
}
}
}
println(ans / 2)
}
逆の条件を書いてelse節のほうに処理を書くという酷いコードになりましたが、急いでいたのでそのまま提出！
両方とも'x'だったらfalseにする、にすればよかったですね。
また、これだとペアの順番が逆になったものを区別して二重にカウントしてしまっているので2で割りました。
うーんこれはひどい…ｗ
C - String Delimiter
"の出現の状態をフラグで管理します。初期値falseで、"が出現するたびに反転します。falseの時に出現した"以外の文字は括られていない、trueだと括られているということになります。
条件に応じた文字をStringBuilderに追加していきました。括られていない,だけ置き換えて、それ以外はそのまま追加します。
fun main() {
val n = readLine()!!.toInt()
val s = readLine()!!
var flag = false
val sb = java.lang.StringBuilder(n)
for(i in s.indices) {
if(s[i] == '"') {
flag = !flag
sb.append(s[i])
} else {
if(flag) {
sb.append(s[i])
} else if(s[i] == ',') {
sb.append('.')
} else {
sb.append(s[i])
}
}
}
println(sb)
}
できればsb.append(s[i])はまとめたかったけど…
さらに、s.indicesじゃなくて普通にsを列挙すればよかったという。
D - Make Bipartite 2
これは解けませんでした。
グラフの問題ですね。二部グラフという言葉は知らなかったですが、DFSとかで走査すれば二部グラフかどうかの判定はわりと簡単にできるということはわかりました。
愚直にやるなら、一回走査して繋がっていないペアを列挙、その後に各ペアごとに二部グラフかどうかを判定していけばいいのですが、何回走査するんだよということで間に合うわけがありません。
方法があるとしたら、一回の走査で全部判定できるようにするか、なんかいい感じのデータ構造を作って二部グラフかどうかの判定を対数時間とかで判定できれば解けるんじゃないかと雑に思いました。もちろんそんなデータ構造が実在するのかどうかわからないので一応調べましたが、少なくとも自分の検索力と理解力の及ぶ範囲では見つかりませんでした。
これってもしかしてすごく難しいのではと思って順位表を見てみましたが、明らかに解けている人が少ないので色々察しました。
解説を見て
ちょっと解説ACする気力がありませんが、可能な範囲だけでも理解しておこうと思います。
まずは入力されたグラフがそもそも二部グラフかどうか判定します。それで、それが二部グラフでなければどのように辺を足しても二部グラフになることはないので答えはゼロで確定すると。なるほど。
二部グラフでないグラフに辺を足すことによって二部グラフになることはなく、辺を足したせいで二部グラフでなくなってしまわないかどうかを判定するということだったのですね…
もう初っ端から気づきが足りませんでした。厳しい。
そもそも例1のようなわかりやすいグラフ
↑こういうやつ（つまり木）も二部グラフってことですね。たしかにそうだ。その認識が既にありませんでした。
それで、二部グラフかどうかの判定は色を塗り分けることによって行います。二部グラフだった場合は、辺を足しても二部グラフであり続けるかどうかを判定するわけですが、これは単にその辺によって結ばれる頂点が別の色であればよいと。た、たしかに……
なので答えとしては全体のペア数から同じ色同士のペア数を引き、さらに最初から辺で結ばれているペア数を引けばいい…と。なるほどー
ただ、このペア数の計算がよくわからなくて頭痛がします。数学ができません。
あとは入力のグラフが連結でない可能性もありますがその場合も基本的な考え方は同じです。全て二部グラフであることが前提で、一つでも二部グラフでない連結成分があれば答えはもう0だと。
（これは少し悩みました。二部グラフの連結成分内で二部グラフであり続ける辺の追加方法はありうるはずと思いました。しかしその連結成分だけ二部グラフでもダメで、全体が二部グラフでなければならないということですね。つながっていなくても一つのグラフ）
別の連結成分に属する頂点同士を結ぶ辺のせいで二部グラフでなくなることないので、一つ一つの連結成分を考えればいいのですね。
まあ解説を見ればなるほどーと思いましたけど、この問題を解くために必要な気付きを自力では一つも得ていませんでしたし、計算部分はよくわからないし、理解したとしても実装が重そうでWA連発しそうだしってことで、全く手に負えない問題だと思いました。
いつか再挑戦…できる日は来るのかなあ（）
感想
一応Cまでは早めに解けたのでレーティングとしては伸びましたが、まだもうちょっと素早く解けるはずだと思いました。というかDのハードルが高すぎるので、現状は早解き力を鍛えるほうが手っ取り早そうという感じ…
なのでDを解くための力を徐々につけていきつつも、早解きのほうも鍛えるのがよさそうです。Twitterで頻繁にバチャを開催している方がいらっしゃるので、可能な範囲で参加させてもらおうと思いました。
Dについては解けるはずのない問題だったので解けなかったのは仕方ないのですが
なんかいい感じのデータ構造を作って二部グラフかどうかの判定を対数時間とかで判定できれば解けるんじゃないかと雑に思いました
このような思考に陥ったら負けだなと感じました。こうなると、それっぽいものを探す旅に出かけてしまって思考が止まります。それは実に良くない。検索力の勝利ってのも稀にならいいですけど、そればっかりで自分で考える力が衰えたら色々と絶望的になります。
ざっと調べるくらいはやってもいいですが、それで見つからなかったら頑張って探し続けるのではなく、解けないなりに考察を深める努力をしたほうが良い結果になる気がしました。
どうせ解けないなら考察しても意味がないなんてことはなく、コンテストが終わって解説を見た時に、考察が途中までは合っていたとわかれば嬉しいので自分の気持ち的には部分点を得られたように感じられますし、解説を理解するための労力も減ります。
なので、解けないなりの考察というのも良いものだよと自分に言い聞かせたいところです。
（今回その点は全然ダメでしたね…）
Discussion