2022年8月13日開催のAtcoder Beginner Contest 264を、備忘的にギリ茶の私の回答と反省を日記的に残しておきます。
今回はC問題で沼ってしまいました。bit全探索で割と早めに構築はできたのですが、列削除が簡単に書けるnumpyを使ったがばかりにTLE。。。 かつD問題は転倒数の割と定番問題だったのですが、それに気づくのも遅かったです。。悔しいかぎりです。
コンテンツ一覧
A - "atcoder".substr()
問題
文字列 atcoder の L 文字目から R 文字目までを出力してください。
制約と入力形式
- L,R は整数
- $$ 1 \leq L \leq 7 $$
入力は標準入力です。
$$L,R$$
回答アプローチ
l,r = map(int,input().split())
s = "atcoder"
print(s[l-1:r])A問題はいかに早く提出するかが鍵の問題ですね。またPythonは文字列を直接リスト的に扱えるので、こういう問題は書きやすいなぁと感じます。
B - Nice Grid
問題
次の図に示す、各マスが黒または白に塗られた縦 15 行 × 横 15 列のグリッドにおいて、 上から R 行目、左から C 列目のマスが何色かを出力して下さい。
制約と入力形式
- $$ 1 \leq R,C \leq 15 $$
- R,C は整数
標準入力で、R,C が与えられます。
回答アプローチ
15 × 15 なので、上記のグリッドを手書きしても正直良いっちゃ良いですよね。B問題もいかに早く提出するかが大事なので、アプローチが思いつかない際はそういうパワープレーでも良いかもしれません。
15 × 15 のnumpy配列を拾い範囲から徐々に狭い範囲に、0と1で交互に埋めていくのを繰り返してグリッドを表現しました。numpy配列だと、二次元での範囲が指定しやすいというメリットがあります。
import numpy as np
import math
r,c = map(int,input().split())
G = np.zeros((15,15))
for i in range(math.ceil(15/2)):
G[i:15-i,i:15-i] = i%2
if G[r-1,c-1] == 1:
print("white")
else:
print("black")[[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.]]一応この書き方なら、15の部分を変数に置き換えれば汎用性あるものになりますね。
C - Matrix Reducing
問題
H1 行 W1 列の行列 A と、H2 行 W2 列の行列 B が与えられます。
- 1 ≤ i ≤ H1 かつ 1 ≤ j ≤ W1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は Ai,j です。
- 1 ≤ i ≤H2 かつ 1 ≤ j ≤ W2 を満たす整数の組 (i,j) について、行列 B の i 行目 j 列目の要素は Bi,j です。
行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ（ 0 回でも良い）繰り返すことができます。
- A の行を任意に 1 つ選んで削除する。
- A の列を任意に 1 つ選んで削除する。
行列 A を行列 B に一致させることができるかどうかを判定して下さい。
制約と入力形式
- $$ 1 \leq H_2 \leq H_1 \leq 10 $$
- $$ 1 \leq W_2 \leq W_1 \leq 10 $$
- $$ 1 \leq A_{i, j} \leq 10^9 $$
- $$ 1 \leq B_{i, j} \leq 10^9 $$
- 入力中の値はすべて整数
入力形式は以下の順に標準入力で与えられます。
$$ H_1, W_1 $$
行列A
行列B
回答アプローチ
今回TLEで沼った問題です。色々考えて全探索をしようと考えました。
削除する行・列は予め決めてしまえば、どの順番で消しても結果は同じです。なので各行・各列に対してそれを削除するか否かの組み合わせを全探索すれば自ずと答えは出てきます。ここでbit全探索を使って、各行・列を採用するか否かを管理します。
そこで、以下のように、列削除が用意なnumpyを使って書きましたが、TLEでした。。
import numpy as np
h1,w1 = map(int,input().split())
a = []
for _ in range(h1):
a.append(list(map(int,input().split())))
h2,w2 = map(int,input().split())
b = []
for _ in range(h2):
b.append(list(map(int,input().split())))
a,b = np.array(a),np.array(b)
flag = False
for h in range(2**h1):
for w in range(2**w1):
rm_h,rm_w = [] ,[]
for h_t in range(h1):
if (h >> h_t) & 1:
rm_h.append(h_t)
for w_t in range(w1):
if (w >> w_t) & 1:
rm_w.append(w_t)
a_new = np.delete(a,rm_h,0)
a_new = np.delete(a_new,rm_w,1)
if np.array_equal(a_new,b):
flag =True
break
else:
continue
break
if flag:
print("Yes")
else:
print("No")ここで、全探索アプローチは筋が悪いのかなどと、色々錯綜してしまいました。。反省ですし、とても悔しいです。
そもそも、行列Bは固定ですし、削除する行数と列数は最初から決まっているのです。例えば、行列 A が 7 × 8 で 行列 B が 5 × 5 の場合、行列 A の 7 つの行のうち( 7 - 5 = 2 )の2本を削除すれば良く、列は 8 つ中 3 つ消せば良いです。
これらの削除組み合わせを、Pythonの標準ライブラリの itertools の combinations 関数を使って求めれば良く、そもそもbit全探索する必要もないです。combinationsは、辞書順に出力してくれるのも大変使い勝手が良い点です。
この時、削除する行・列は数が大きい方から削除していきます。この時 0 列目を削除した後に、2列目を削除しようとすると、元々削除しようとしていた列とは別のものを削除するためです。
import itertools as it
import copy
h1,w1 = map(int,input().split())
a = []
for _ in range(h1):
a.append(list(map(int,input().split())))
h2,w2 = map(int,input().split())
b = []
for _ in range(h2):
b.append(list(map(int,input().split())))
delh = list(it.combinations(range(h1),h1-h2)) #削除する行の組み合わせ候補
delw = list(it.combinations(range(w1),w1-w2)) #削除する列の組み合わせ候補
flag = False
for dh in delh: #削除する行・列の組み合わせ候補を二重ループ
for dw in delw:
a_new = copy.deepcopy(a)
for h_t in reversed(dh): #候補の行を削除。reversedで数が大きい行から削除
del(a_new[h_t])
for w_t in reversed(dw): #候補の列を削除。reversedで数が大きい列から削除
for a_t in a_new:
del a_t[w_t]
if a_new == b: #行列Bと一致したら、二重ループを抜けて、出力
flag =True
break
else:
continue
if flag:
print("Yes")
else:
print("No")D - "redocta".swap(i,i+1)
問題
atcoder の並べ替えである文字列 S が与えられます。
この文字列 S に対して以下の操作を 0 回以上行います。
- S 中の隣接する 2 文字を選び、入れ替える。
S を atcoder にするために必要な最小の操作回数を求めてください。
制約と入力形式
- S は
atcoderの並べ替えである文字列
入力は文字列が標準入力で与えられます。
回答アプローチ
転倒数を出力してあげれば良い問題です。転倒数は以下のサイトが分かりやすく説明しているかと思います。
”atcoder” は全て異なる文字で構成されているので、”1234567"と番号を付けてあげて、入力された文字列に対して対応する数列を求めます。例えば、”tacoder”の場合は "2134567" ですし、"catredo"の場合は "3127654"です。
転倒数とは、「自身より前にいる自身より大きい数の個数」を各数に対して行なった和です。”tacoder”の場合の "2134567"に関しては、"1" は自分より前に "2"がありますが、それ以外の数は昇順になっているので転倒数は 1 です。
また、"catredo"の場合の"3127654"に関して、"4" に注目すると 4 より大きい数は左側に「7,6,5」の 3 こあります。これを各数に対して行うと合計は 8 となり、これが転倒数になります。
S = input()
A = "atcoder"
L = []
for s in S:
L.append(A.find(s)) #入力された文字列を数列に変換します。ex)”tacoder” → "2134567","catredo" → "3127654"
T = 0
for i in range(len(L)):
T += sum(l>L[i] for l in L[:i]) #各数に対して、自分より左にある自分より大きい数の個数を求めて、Tに加算していきます。
print(T)