📌
AtCoder Beginner Contest 266 A～Cのメモ
AtCoder Beginner Contest 266に出たのでメモを残しておきます。
A - Middle Letter
言語によって異なりますが私が使っているKotlinも含めて多くの言語では割り算は小数点以下は切り捨て、配列は0オリジンなので、単純に長さを2で割れば中央を指す添字になります。
fun main() {
val s = readLine()!!
println(s[s.length / 2])
}
B - Modulo Number
xは0以上998244353未満なので、これを全部チェックすれば解けちゃいます。
けっこう大きな数なので間に合わないかなと思いましたが、普通に間に合いました。（言語によっては間に合わないかもしれません）
fun main() {
val n = readLine()!!.toLong()
for(x in 0 until 998244353) {
if((n - x) % 998244353 == 0L) {
println(x)
return
}
}
}
だいたい10 ^ 9のループで1秒というざっくり指標があり、実際にだいたいその通りになっています。
この指標はC++を念頭に置いたものだと思うので、Kotlinもなかなかやるじゃーんって思いました。
当初は計算で求めようとして時間を遣ってしまいましたが、私には無理でした。なんで余りを求める程度のことがわからなかったのかわからないですが、まあその程度の計算力ということですね…
全部チェックだと間に合わなそうだとなんとなく思って計算で求めようとしましたが、制約をちゃんと見れば間に合うことが理解できたはずなので、時間を無駄にしてしまいました。
C - Convex Quadrilateral
すみません、ぶっちゃけこれは自力で解いていません。ググったらまさにそれというのが見つかったので拝借したら通ってしまいました。まあ、検索力の勝利ということで一つ…
fun main() {
val (ax, ay) = readLine()!!.split(" ").map { it.toInt() }
val (bx, by) = readLine()!!.split(" ").map { it.toInt() }
val (cx, cy) = readLine()!!.split(" ").map { it.toInt() }
val (dx, dy) = readLine()!!.split(" ").map { it.toInt() }
if(isConcave(listOf(ax, bx, cx, dx), listOf(ay, by, cy, dy))) {
println("No")
} else {
println("Yes")
}
}
fun isInside(ax: Int, ay: Int, bx: Int, by: Int, cx: Int, cy: Int, tx: Int, ty: Int): Boolean {
val abXat = (bx-ax)*(ty-ay) - (by-ay)*(tx-ax)
val bcXbt = (cx-bx)*(ty-by) - (cy-by)*(tx-bx)
val caXct = (ax-cx)*(ty-cy) - (ay-cy)*(tx-cx)
if(( abXat > 0 && bcXbt > 0 && caXct > 0) || ( abXat < 0 && bcXbt < 0 && caXct < 0)) {
return true;
} else if(abXat * bcXbt * caXct == 0) {
return false
}
return false
}
fun isConcave(px: List<Int>, py: List<Int>): Boolean {
for(i in 0 until 4) {
if(isInside(px[i%4], py[i%4], px[(i+1)%4], py[(i+1)%4], px[(i+2)%4], py[(i+2)%4], px[(i+3)%4], py[(i+3)%4])) {
return true;
}
}
return false
}
これは四角形が凸であるかどうかではなく、凹であるかどうかを判定しています。
ただ、計算の意味が全然わかっていません。いつかわかるように頑張ります…
追記
ちゃんと読めていないですが、交差判定の一種っぽい気がします。
教訓
- 現状としては数学力は低いので、できるだけ計算しなくて済む方法（ゴリ押し、検索etc.）で頑張る
- とはいえ、そのような方法ではおそらく灰色止まり。結局のところは数学力をつけていくしかない
Discussion