AtCoder Beginner Contest 359参加記
ユニークビジョンプログラミングコンテスト2024 夏（AtCoder Beginner Contest 359）に参加したので記録を残します。
今回は2完です。C難しい。というかユニークビジョンコンテストはだいたい難しい印象…
A - Count Takahashi
filterで瞬殺です。
fun main() {
val n = readln().toInt()
val s = List(n) {
readln()
}
println(s.filter { it == "Takahashi" }.size)
}
B - Couples
各indexOfFirstとindexOfLastでサクッと求めます。
fun main() {
val n = readln().toInt()
val a = readln().split(" ").map { it.toInt() }
var ans = 0
for(i in 1..n) {
val p1 = a.indexOfFirst { it == i }
val p2 = a.indexOfLast { it == i }
if(p1 + 2 == p2) {
ans++
}
}
println(ans)
}
この時点だと3桁順位でした…ｗ
Kotlinはわりとこういう問題には強いです。
C - Tile Distance 2
これが解けずじまいでした。まず問題文とイラストで怯みましたが、なんとかかじりつきます。
なんか数式がありますがこれは座標の集合で、要素数は4つ、それらの座標が面積1の正方形を構成するということでした。まあ、このあたりはイラストを見れば想像つくのですが。
移動距離は任意の距離を選べますが、これは1しか移動できないと考えても同じことですね。
制約がでかいので、グラフとして探索ではなく計算で求めるとわかりました。もし2つつながった長方形ではなく全部面積1の正方形だった場合は、通行料は単純に移動回数となります。それに比べると、今回の問題では長方形内の移動は通行料がかからないので、その場合は移動回数としてカウントしないと考えると、横移動の回数はいくらか減らせると考えられます。縦移動の回数は減らないので、横移動の回数を何回減らせるか求める問題ということになりますね。
例1のように、左移動、かつ初期位置が右側、かつ横移動の回数が縦移動の回数以下なのであれば、横移動の回数は0回と考えても問題ないというのはわかりました。左右どちらに向かうのかと、長方形の左右どちらにいるのかの組み合わせで答えが1だけ増減します。
じゃあ横移動の回数が縦移動の回数より多い場合はどうなるかというと、ここでシンプルに考えることができませんでした。ややこしい考え方としては、まず向かう方向と長方形の左右が異なるなら1減らせる、そこから縦移動の回数分も減らせる、その分だけ移動したと仮定して、その位置において向かう方向と長方形の左右が異なるならさらに1減らせる、そこからは横の移動距離の半分だけ減らせる、みたいになります。自分でも何を書いているのかよくわかりません…
この方針で突っ切ったら解けるんじゃないかとは思ったもののややこしすぎて、時間も残り少なかったので実装が間に合わず終わりました。まあ、本当にこの方針で突っ切れるのかわからないのですが。試したいけどこのままだとさすがにつらいですね。もう少し簡略化できないか考えます…
感想
2完だけどAB早解きにはまあまあ成功したので軽症で済みました。ちょっと今は精進できないので、この程度で済むならむしろ実質勝ちです。（？）
でも実際、最初は解ける気がしなかったCについて、一応の方針を立てられるところまで粘れたのはけっこう嬉しかった。なので今回はそれなりに満足ですね。
それにしても、Cってかなり難しいと思ったのですが4000人以上が解いているんですね。皆さんすごすぎる…
（執筆時間: 21分49秒）
Discussion