[ABC264]freee プログラミングコンテスト2022（AtCoder Beginner Contest 264） A～C問題Python解説

2020/8/13に行われました、ABC264の解説記事です。
ご質問・ご感想・ご要望等はぜひコメントにお願いいたします。
返信もさせていただきますので、返信もご確認のほどよろしくお願いいたします。

A問題

A - "atcoder".substr()

L, R = map(int, input().split())
a = "atcoder"
print(a[L-1:R])

問題文のとおりにできる基礎的な問題ですが、
indexについては注意しておかなければいけません。

問題文からL文字目からR文字目までを出力させるわけですが、
Pythonで扱う所謂index番号とは違いがあります。

ふつうは1番初めの文字は“1文字目”としますが、
Pythonの1番はじめの文字はindex = 0です。

実際にLとRを設定した後ご自分で、入力例などを使って一度出力結果を確認することで、ミスを減らすことができます。

B問題

B - Nice Grid

R, C = map(int, input().split())

a = [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,0,0,0,0,0,0,0,0,0,0,0,1,0],[0,1,0,1,1,1,1,1,1,1,1,1,0,1,0],[0,1,0,1,0,0,0,0,0,0,0,1,0,1,0],[0,1,0,1,0,1,1,1,1,1,0,1,0,1,0],[0,1,0,1,0,1,0,0,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,0,0,1,0,1,0,1,0],[0,1,0,1,0,1,1,1,1,1,0,1,0,1,0],[0,1,0,1,0,0,0,0,0,0,0,1,0,1,0],[0,1,0,1,1,1,1,1,1,1,1,1,0,1,0],[0,1,0,0,0,0,0,0,0,0,0,0,0,1,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
if a[R-1][C-1] == 0:
    print("black")
else:
    print("white")

かっこよく解きたい方は、チェビシェフ距離というものがあるみたいですね。(以下解説記事がありましたので、興味ある方は飛んでみてください)

Editorial - freee Programming Contest 2022（AtCoder Beginner Contest 264）

ただ、これを知らなくても縦15行×横15列のマス目を自分で書けば、解くことができます。

まずは、問題文の絵をコード上に起こしていきます。
私は黒を0、白を1としました。
リストaはマス目を表しています。
例えばa[0][0]は上から1行目、左から1行目つまり左上の1マスを指します。
(先ほども言いましたが、inedexは0からなので注意です！)

後は入力されたRとCを使って、マス目の色を出力します。

C問題

C - Matrix Reducing

import itertools

H1, W1 = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H1)]

H2, W2 = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(H2)]

h = [_ for _ in range(H1)]
w = [_ for _ in range(W1)]

for i in itertools.combinations(h, H2):
    for j in itertools.combinations(w, W2):
        # print(i, j)
        lis = []
        for k in i:
            li = []
            for l in j:
                # print(k, l)
                li.append(A[k][l])
            lis.append(li)
        if lis == B:
            print("Yes")
            exit()
print("No")

問題文には削除すると書いてありますが、
「どの部分を使うか」に着目して解いていきます。

ここからはYesつまり行列Aを操作することで、行列Bに一致することができる前提で話します。
（もしも条件を満たさなければ最後にNoと出力します。)

問題文や入力例を読んでいくと、行列Aの行や列を削除することで最終的にはH2×W2の行列になります。
つまり、使うH2個の行、W2個の列をそれぞれ選んで、
総当たりをすることで、
作ることが可能なすべてのH2×W2の行列を列挙することができますね。

組み合わせをPythonで使うには
itertools.combinatitonsを使います。
個人的におすすめのライブラリですし、ABC頻出なので、
ぜひはじめましての方、習得をお勧めします。
以下の記事が分かりやすいですよ！

Pythonで階乗、順列・組み合わせを計算、生成 | note.nkmk.me

行と列の候補はhとwにそれぞれ置いておきます。
もちろん、hは0～H1、wは0～W1です。

行をH2分、列をW2分取ってきて、
座標を当てはめることで、実際に取ってくる要素を決めることができます。
その要素を使って行列を作成し、Bと一致するかどうかを調べることで答えを導き出すことができます。

ここまで読んでいただきありがとうございました。
来週もぜひご覧ください。