AtCoder Beginner Contest 279 A～Cのメモ

トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)に参加したので、参加記を残しておきます。
https://atcoder.jp/contests/abc279

A - wwwvvvvvv

なにわろてんねん

vを1、wを2として合計値を求めればOKです。

fun main() {
    val s = readLine()!!
    println(s.map { if(it == 'v') 1 else 2 }.sum())
}

B - LOOKUP

SがTを含むかというのを標準ライブラリを使って判定すれば楽です。

fun main() {
    val s = readLine()!!
    val t = readLine()!!

    if(s.contains(t)) {
        println("Yes")
    } else {
        println("No")
    }
}

C - RANDOM

入れ替えて一致させられるかどうかは、ソートして比較すればいいというのはすぐに思いつきました。
列単位でソートする必要がありますが、行単位でデータを受け取るので、これを転置させる必要があります。
ただ制約が大きいため、単純な実装で転置させるともう間に合わない…と勘違いしていました。
$1 ≤ H, W ≤ 4 × 10 ^ 5$だと思ってました。そうなると$O(HW)$だともう全然間に合わないと。そもそもその場合、二次元配列で保持した状態で一致するかどうかの判定だけでも間に合わない気がするので、根本的に発想が間違っているんだな、なんか全然自分には理解できない方法でないと解けないんだな、と諦める寸前までいきました。

しかし、どれくらいの人数が解けているのか見てみると、けっこう普通にみんな解けている印象を受けました。自分の理解では相当な難問であるはずなので、これはおかしい。
ということで勘違いに気づきました。
$1 ≤ H, W ≤ 4 × 10 ^ 5$ではなく、$1 ≤ H × W ≤ 4 × 10 ^ 5$でした。HとWのそれぞれの最大値が$4 × 10 ^ 5$なのではなく、HとWを掛けた値の最大値が$4 × 10 ^ 5$でした。
じゃあ最初に思いついた解法で全く問題なく通るんじゃないでしょうか……

fun main() {
    val br = System.`in`.bufferedReader()

    val (h, w) = readLine()!!.split(" ").map { it.toInt() }

    val transposeS = MutableList(w) { CharArray(h) }
    val transposeT = MutableList(w) { CharArray(h) }

    repeat(h) {
        val input = br.readLine()!!
        for(i in input.indices) {
            transposeS[i][it] = input[i]
        }
    }

    val t = List(h) {
        val input = br.readLine()!!
        for(i in input.indices) {
            transposeT[i][it] = input[i]
        }
    }

    if(transposeS.map { it.joinToString("") }.sorted() == transposeT.map { it.joinToString("") }.sorted()) {
        println("Yes")
    } else {
        println("No")
    }
}

うん……

実装自体はすぐにできましたので、勘違いにより1時間近く無駄にしました。若干レーティングが下がったので残念です。

反省

制約は重要なのでちゃんと見ましょう…

あとは「全然自分には理解できない方法でないと解けないんだな」などと考えて気づくのが遅れたのは実力不足の結果でしかないので、まあこれからも少しずつ力をつけていきましょうということですね。

変な話、昔の自分なら計算量とか全然わからずそのままポンっと提出して早々に通してたと思うんですよね。なので、知識がついたことで逆に成績が落ちたということになります。生兵法は大怪我のもとというか。
もちろん計算量を考えるべきでないかというと、そんなわけがありません。計算量を考えることは必須ですが、今回のようにそもそも制約を見間違えていたり、もしくは計算ミスで誤った認識になったりすると逆効果になります。知識をつけるならちゃんと関連する力（制約を正確に把握する力、アホな計算ミスをしない程度の計算力）を身に着けないといけないということですね。現状はそれができていないということですね…

まあ今回の失敗によって今後は同じミスは減るかなとは思うので、少し強くなったはずです。たぶん。

他の人がどれくらい解けているかを確認するといいかもしれないというのは以前のコンテストで得られた知見なので、これがなかったらたぶん気づくことはなく2完で撤退していたと思います。なので、以前の反省を活かせたという良い点も一応ありました。

ちなみに、D問題を見てみるくらいの時間は残ったので見てみましたが、全然自分の手に負える問題ではなさそうで、C問題を早く解けたとしてもDは解けなかったと思います。そういう意味だと、D問題も考察の取っ掛かりくらいは把握できる程度の力をつける必要はありますね。

あれも身につけなきゃ、これも身につけなきゃ、なので沼ですねーｗ
まあ同時にいろいろ身につけるのは無理なので、現状から何か一つでも加点されればいいかなくらいのノリでいきます。