できない人が Python でやる AtCoder（ABC300 A問題・B問題）

世の中には競技プログラミングというものがあって、レートでもってその力を試す場がいくつかあったりする。そのうちの一つが AtCoder である。

AtCoder

自分は情報学科出身ではあるが、アルゴリズムとなると途端によわよわになるので（―― 否！そういえば他の分野もよわよわであった）どれだけできないかを示しながら問題を解いていこうと思う。

今回挑戦したのは ABC300 である。過去問は膨大にあるが、300 というキリがいい数字が目に入ったので挑戦することにした。なんとも安易なチョイスの仕方である。

UNIQUE VISION Programming Contest 2023 Spring(AtCoder Beginner Contest 300) - AtCoder

A - N-choice question

---

A 問題は入力処理さえできれば勝ったも同然のレベルであるが、自分レベルだとその入力処理すら無理なのだ。というかこれは競技プログラミング初心者あるあるだと思う。

入力処理とかいう難関を越えればあとは足して答えの選択肢を選ぶだけである。出力する選択肢の番号に注意。

n, a, b = map(int, input().split())
c = list(map(int, input().split()))

ans = a + b
for i in range(n):
    if c[i] == ans:
        print(i + 1)
        break

解答後に適当に検索して別解も見たがおおむね同じようなアルゴリズムで一安心。

B - Same Map in the RPG World

---

……

アホくらいわからない

まず行列に対する入力処理がわからないのはお決まりとして、アルゴリズムの前に問題の意味がよくわからない。

こういう時は慌てずに例をじっくり見るとわかる。縦シフトは上方向、横シフトは左方向にマップが動く。直感とは逆に思えるかもしれないが、まぁゲームのマップでも下に入力するとマップ全体が上に動くし、右に入力するとマップ全体が左に動く、みたいな感じ。

あと例 4 の「ABC」に見えるマップと「300!」に見えるマップが同じというのは素直に感心した。というかこれ見せたかっただけだろ！

自分の解答（WA）

WA とは不正解、ということである。書いたプログラムは動くがアルゴリズムが間違っていた、ということである。

方針としては「s 回縦シフト、t 回横シフトを行っても各行、各列の "#" の数は変わらないのではないか」というものだ。

H, W = map(int,input().split())
A = [input() for _ in range(H)]
B = [input() for _ in range(H)]

counts1 = []
for h in range(H):
    counter = 0
    for w in range(W):
        if A[h][w] == '#':
            counter += 1
    counts1.append(counter)

for w in range(W):
    counter = 0
    for h in range(H):
        if A[h][w] == '#':
            counter += 1
    counts1.append(counter)

counts2 = []
for h in range(H):
    counter = 0
    for w in range(W):
        if A[h][w] == '#':
            counter += 1
    counts2.append(counter)

for w in range(W):
    counter = 0
    for h in range(H):
        if A[h][w] == '#':
            counter += 1
    counts2.append(counter)

print('Yes') if counts1 == counts2 else print('No')

結果の詳細を見るとテストケースに対して AC（正解）であったり WA であったりが入り混じっている感じである。

素人目には一見惜しそうではあるが、なんというかアルゴリズムの根本から間違っている気がしたし（というかそう）、他にいい感じのアルゴリズムも思い浮かばなかったのでここでお手上げ。

公式の解答

方針は「s、t の範囲を絞って 4 重ループ」というものである。はじめ問題を理解したとき、自分は「s、t はいくらでもありそうで嫌だなぁ。いい感じのアルゴリズムがあるに違いない」と勝手に決めつけ、前述した「それっぽくはあるが根拠が全くないアルゴリズム」を実装してしまっていた。

一方で、公式の解答は冷静に s、t の範囲を絞り込み、ループ処理で着実に正答を導いていた。

公式の解説を元に書いた Python コードが以下となる。

H, W = map(int,input().split())
A = [input() for _ in range(H)]
B = [input() for _ in range(H)]

for s in range(H):
    for t in range(W):
        ok = 1
        for h in range(H):
            for w in range(W):
                if (A[(h - s + H) % H][(w - t + W) % W] != B[h][w]):
                    ok = 0
        if ok == 1:
            print('Yes')
            exit()

print('No')

全体的な所感

---

いやまさか B 問題でこんなことになるなんて思ってもみなかった。というか自分が明らかにできない人の思考回路を辿っていて恥ずかしくなった。

特に B 問題なんかではいわゆる「エレガントな解法」などはほとんどないのだからもっと冷静になればよかった。

全体としてはもっとこう、競技プログラミング（というか AtCoder）の文化に慣れる必要がある気がした。そのためにはアルゴリズムを学ぶのも大切だが、それ以前に継続的に問題に触れていくのが大切だと思った。特に B 問題までなら多少乱暴なアルゴリズムでも AC で通ったりするはずなので地道にできればなぁと（三日坊主を懸念）。