AtCoder Beginner Contest 275 A～Dのメモ

AtCoder Beginner Contest 275に参加したので記録を残しておきます。
Dまで書いていますがコンテスト中に解けたのはAとBのみです。C、Dはコンテスト終了後に解けました。

https://atcoder.jp/contests/abc275

A - Find Takahashi

全て高さが異なりかつNが小さいので、最大値を求めてからその最大値で再度探索でOKです。

fun main() {
    val n = readLine()!!.toInt()
    val h = readLine()!!.split(" ").map { it.toInt() }
    println(h.indexOf(h.max()) + 1)
}

B - ABC-DEF

普通にやるとオーバーフローするので随時modをとる必要がありますが、オーバーフローしない型を使えば単純に計算するだけでOKですｗ
modは苦手なのでBigIntegerを使う方針を早々に決めました。

import java.math.BigInteger

fun main() {
    val input = readLine()!!.split(" ").map { it.toBigInteger() }
    val a = input[0]
    val b = input[1]
    val c = input[2]
    val d = input[3]
    val e = input[4]
    val f = input[5]

    println(((a * b * c) - (d * e * f)) % BigInteger("998244353"))
}

Kotlinだと6つとかになってくると分割代入できなくなるので若干面倒でした。
しかし演算子オーバーロードのおかげでBigIntegerを演算子で扱えるのは便利です。

C - Counting Squares

コンテスト中粘ったけど解けませんでした。頑張れば解けそうな感じがして悔しかったです。
あまりに悔しかったので、コンテスト後もさらに粘りました。7WAを出しながら最終的には通せたのでよかったです。
斜めになっているパターンがあるのが厄介ですね。それがないとB問題レベルになってしまうので仕方ないのですが。

なかなか酷いコードですが、なるべくコメントで補足しました…

import kotlin.math.abs
import kotlin.math.pow
import kotlin.math.sqrt

const val eps = 1e-9

fun main() {
    val s = List(9) {
        readLine()!!
    }

    // 同じ正方形を重複して数えるので重複除外用のSetに詰めて、その件数を出力する
    val set = mutableSetOf<List<Pair<Int, Int>>>()

    // 4点をバラバラに列挙
    for(i in 0 until 9) {
        for(j in 0 until 9) {
            for (k in 0 until 9) {
                for(l in 0 until 9) {
                    // 2点が決まったので距離を求める
                    val d1 = distance(i, j, k, l)
                    for(m in 0 until 9) {
                        for(n in 0 until 9) {
                            // 3点が決まったのでもう一辺の距離を求める
                            val d2 = distance(k, l, m, n)
                            // 距離が異なれば正方形ではない（誤差を考慮し、差が許容範囲内なら一致と判定する）
                            if(abs(d1 - d2) > eps) {
                                continue
                            }
                            // 角度を求めるため、三角形の斜辺の長さを求める
                            val d3 = distance(i, j, m, n)

                            // 直角でなければ正方形ではない
                            if(!isRightAngle(d1, d2, d3)) {
                                continue
                            }

                            for(o in 0 until 9) {
                                for(p in 0 until 9) {
                                    // 最後の4点目が決まったので距離を求める
                                    val d4 = distance(m, n, o, p)
                                    val d5 = distance(o, p, i, j)
                                    // 距離が異なれば正方形ではない（誤差を考慮し、差が許容範囲内なら一致と判定する）
                                    if(abs(d2 - d4) > eps || abs(d4 - d5) > eps) {
                                        continue
                                    }

                                    // 同じ点を指してしまっていることがないかどうかチェック
                                    if(setOf(i to j, k to l, m to n, o to p).size != 4) {
                                        continue
                                    }

                                    // ここまで来れば確実に正方形なので、4点全てにポーンがあるかどうかを判定
                                    if(s[i][j] == '#' && s[k][l] == '#' && s[m][n] == '#' && s[o][p] == '#') {
                                        // 同じ正方形を重複して数える場合の考慮
                                        // 文字列として結合してソートすれば等価
                                        set.add(listOf(i to j, k to l, m to n, o to p)
                                            .sortedBy { "" + it.first + it.second }
                                        )
                                    }
                                }
                            }
                        }
                    }

                }
            }
        }
    }
    println(set.size)
}

// 2点間の距離を求める
fun distance(y1: Int, x1: Int, y2: Int, x2: Int): Double {
    // 9から引くのは、本来の座標は下から上なので向きをそちらに揃えるため（不要？）
    return sqrt((x2.toDouble() - x1).pow(2.0) + ((9-y2).toDouble() - (9-y1)).pow(2.0))
}

// 三平方の定理により、三点が直角三角形をなすかどうか判定する（直角かどうかの判定）
fun isRightAngle(a: Double, b: Double, c: Double): Boolean {
    val list = listOf(a, b, c).sorted()

    return abs(list[2].pow(2.0) - (list[0].pow(2.0) + list[1].pow(2.0))) < eps
}

コンテスト中は2点だけ探索して、残り2点は計算で求める方針でやろうとしていましたがうまく実装できませんでした。
4点を全部探索しても実は間に合うんじゃない？とコンテスト後に思ってそれで実装しなおしました。それなりに枝刈りして、定数倍が重い処理も避けないと微妙に間に合わなそうな処理時間になったのでけっこうギリギリの線でしたが。

正方形かどうかの判定ですが、長さが全部同じであることと、そのうち3点が直角三角形をなすかどうかを判定する必要があります。後者を失念していて沼りました…

長さは整数になるとは限らないのでDoubleで扱いますが、ここで問題になるのが誤差です。一致するかどうかを単純に比較すると、本来は一致するはずなのに誤差により不一致と判定される可能性があります。
それの回避方法として、長さが完全一致かどうかを判定するのではなく、長さの差をとってそれが非常に小さい範囲に収まるかどうかで判定しています。差が非常に小さければ一致と判定してしまいます。
このテクニックは以前読んだ本にありました。
BigDecimalを使えば誤差は避けられますが、TLEになるくらい遅くなったので上記の方針でいきました。

正方形を見つけることができたら、4点全てにポーンがあるかどうかを判定します。
同じ正方形を重複して数える可能性があるので、Setで重複を除外しています。

D - Yet Another Recursive Function

コンテスト中は開きもしなかったのですが、コンテスト後のTwitterのTLを見て、なんか簡単そう？と思ってやってみました。
結果をキャッシュしつつ必要に応じて再帰するだけなので、特に苦労することはありませんでした。D問題がこのレベルってこともあるのですね。C問題は無視してD問題をやったほうがレートは稼げましたね…
ただ、茶diffのようなので、再帰に慣れていない人だとけっこう難しかったりするのでしょうか？

val map = mutableMapOf<Long, Long>()

fun main() {
    val n = readLine()!!.toLong()
    println(f(n))
}

fun f(k: Long): Long {
    if(k == 0L) {
        return 1
    }

    val k2 = k / 2
    val a = if(map.containsKey(k2)) {
        map[k2]!!
    } else {
        val ret = f(k2)
        map[k2] = ret
        ret
    }

    val k3 = k / 3
    val b = if(map.containsKey(k3)) {
        map[k3]!!
    } else {
        val ret = f(k3)
        map[k3] = ret
        ret
    }
    return a + b
}

こういうのはメモ化再帰というそうです。普通は連想配列ではなく配列（バケット）を使うようですが。

感想

C問題がコンテスト中に解けなかったのは残念だったのと、C問題を捨ててD問題をやっていればレーティングがもっと上がっていたというのはありますが、コンテスト後とはいえCとDの両方を解けたのでよかったです。

C問題については、4点全てを探索する方針をコンテスト中に思いついていれば解けた可能性はありましたね。計算が苦手なくせに2点を計算で求めようとしてしまったのが誤りの元でした。
4点の全探索で間に合うはずがないという思い込みのせいですね。ちゃんと見積もるべきでした。
計算量を見積もる、短期的には計算を避ける、長期的には計算力を鍛える、あたりが教訓です。なんか、以前も全く同じことを書いた気がしますが。まるで成長していない…

D問題はコンテスト中に見ていれば確実に解けていたので、もったいなかったです。今後はD問題も一応目を通すことにしようと思います。

ただ、C問題について完全に諦めモードになれば自ずとそうするのですが、今回みたいに解けそう！解きたい！！ってなっているとなかなか難しいんですよね。今回はコンテスト終了直前にもヤケクソ提出をしたりして最後まで粘り、それどころかコンテスト終了後にも粘着し続けて解いたので…
コンテスト終了後にも粘着するパターンは珍しいですが、最後まで粘るのはけっこう毎回なんですよね。最近はコンテスト中にC問題が解けることも増えてきましたが、D以降は無視してC問題に全力投球することでなんとか達成しているという感じです。
Dのほうが実は簡単かもと思って意識を分散させると、意識を集中させていれば解けたかもしれないC問題を落とすことに繋がるかもしれず、なかなか難しいと思います。

まあ他の人がどれくらい解けているか？といった情報は普通にコンテスト中に確認できるので、他の人はけっこうCを捨ててDを解いていそうだということでそれに倣った人も多かったみたいです。
今後はそういうのも頭に入れて動いたほうがいいかもしれませんね。

とはいえそういうのはやっぱりおまけで、普通にC問題を早く解けるくらい力をつけるのが王道だと思います。これからも少しずつ力をつけていきます。