0 はじめに
0-1 記事について
AtCoder Beginner Contest 268の解説です。
Pythonで書きます。
公式な解説とは異なる場合がありますがご了承下さい。
ミス等ございましたらコメント欄よりお知らせ頂ければ幸いです。
1 ABC268 解説
1-1 個人的な感想
今回は珍しくDが水Diffと、高難易度でした。
Diffは、AとBが灰前半、Cが茶後半、Dが水前半、掛け離れてEFが青後半といった感じです。
私は三冠でしたが、なんとBでFAを取ることが出来ました!!
独り佇んでいる緑コーダーが私です。
爆速三冠(8分半)したのでDiffは緑と水の間くらいで、Ratingは+3でした。
まあ満足といった感じです。
Dは通したかったですが...
1-2 A問題 Five Integers
問題
整数$A,B,C,D,E$が与えられます。
その中に何種類整数が含まれるか出力して下さい。
解説
A,B,C,D,Eを配列として受け取ってソートするなど、色々な方法が考えられますが、ここではset型を使います。
set型とは、集合を扱う型です。使い方についてはネットで調べてみましょう。
配列[A,B,C,D,E]をset型にした時の要素数(長さ)を出力すればよいです。
実装
L=list(map(int,input().split()))
S=set(L)
print(len(S))
1-3 B問題 Prefix?
問題
英小文字のみから構成される二つの文字列$S,T$が与えられます。
$S$が$T$の接頭辞か判定して下さい。
解説
接頭辞とは、簡単に言えば「その文字列の先頭からi文字」です。
例えば、pythはpythonの接頭辞ですが、pppはpythonの接頭辞ではありません。
文字列SがTの接頭辞であるということは、「Tの先頭len(S)文字がSと一致している」と言い換えられます。
それを判定すれば良いです。
ここでは、Pythonのスライスというものを使えば短く書けます。
スライスとはS[a:b]などといったもので、この場合、Sのa文字目からb-1文字目と同じです。
スライスについてはこちらの記事で詳しく説明されています。
実装
S=input()
T=input()
head=T[:len(S)]
if S==head:
print("Yes")
else:
print("No")
スライスは短く書けるのでとても便利ですが、スライスの一回当たりの計算量は、取得するスライスの長さをkとして$O(k)$です。
TLEの可能性があるので、容易にfor文の中で使わないようにしましょう。
(スライスでは、指定した範囲の中に範囲外参照となるものがあればそれを無視しますので、エラーによるREは心配しなくて結構です。)
(2022/09/11 18:16追記)startswith関数というものがあります。
A.startswith(B)で、文字列Aが文字列Bで始まっているかを判定できます。即ち、今回の問題はstartswith関数を使えば工夫を施すことなく解けます。
@Kentuc-oh さん、ご指摘ありがとうございます。
startswith関数での実装
S=input()
T=input()
if T.startswith(S):
print("Yes")
else:
print("No")
1-4 C問題 Chinese Restaurant
問題
回転テーブルの周りに人$0$,人$1$,...人$N-1$が等間隔に並んでいます。
人$i$の前には料理$P_i$が置かれています。
あなたは次の操作を何回でも行う事ができます。
回転テーブルを一周の$N$分の$1$だけ回し、人$i$の前にあった料理を人$(i+1) mod N$の前に移動させる。
操作を終えた後に、人$i$は、料理$i$が人$(i-1)modN$か人$i$か人$(i+1)modN$の前にあると喜びます。
喜ぶ人数の最大値を求めて下さい。
解説
(喜ぶ人数の最大値をスコアとします)
愚直に、操作を$N$回行った時のそれぞれのスコアを求めるとどうなるでしょうか。
操作は$N$回行われ、$N$人の人を喜んでいるか判定するので、計算量は$O(N^2)$となり、TLEが出てしまいます。
どうすれば良いでしょうか。
考えてみれば、$N$通りのテーブルの状態に対して、$N$人の人が喜ぶ回数の合計は丁度$3N$回しかありません。
$N$人それぞれが、$3$通りの状態で喜ぶので当然ですね。
配列cntを次のように定義します。
cnt[i]は、テーブルがi回操作された時に喜ぶ人数
そして次のように工夫して計算します。
$N$人それぞれについて、人
iが喜ぶ時の操作の回数を求め、それぞれa,b,cとする。cnt[a],cnt[b],cnt[c]を1増やす。
人iの喜ぶ時の操作回数は$O(1)$で求まり、それを$N$回計算するので計算量は$O(N)$となり、これなら間に合います。
最後にLの最大値を出力すればよいです。
実装
N=int(input())
P=list(map(int,input().split()))
L=[0]*N
for i in range(N):
a=(P[i]-i-1)%N; b=(P[i]-i)%N; c=(P[i]-i+1)%N
L[a]+=1; L[b]+=1; L[c]+=1
print(max(L))
このように、愚直な計算だと$O(N^2)$掛るものをなんとか$O(N)$に抑えるという技法は高難易度でもよく出題されるので慣れておきましょう。
3問だけで低難易度ですが例題(?)を貼っておきます。
ABC262-C Min Max Pair
ABC210-C Colorful Candies
ABC186-D Sum of difference
1-5 D問題 Unique Username
問題
以下の条件を全て満たす文字列$X$を一つ出力して下さい。
$X$は以下の手順で得られる文字列である。
$N$個の文字列$S_1,S_2,...S_N$を好きな順番に並べたものを$S'_1,S'_2,...S'_N$とする。そして、$S'$のそれぞれの要素の間に一つ以上の
_を並べたものを$X$とする。$3\leq|X|\leq16$である。
$X$は、$M$個の文字列$T_1,T_2,...T_M$のいずれにも一致しない。
そのような文字列が存在しないならば-1を出力して下さい。
解説
$X$としてあり得る文字列を全探索してもよさそうです。
1つずつあり得る文字列を探索し、もし$T$に含まれず、条件を満たしていればそれを出力して終了、$T$に含まれるならば続行、という風に全探索できます。
何故全探索できるか?
見ている文字列が$T$に含まれず条件を満たしていれば出力して、含まれれば続行する訳ですが、その「探索」は最悪の場合でも$M$回しか行われません。
「探索の続行」は、今見ている文字列が$T$に含まれている時に限って行われる訳ですから、そのような文字列が存在すれば、遅くとも$M+1$回目には目当ての文字列を見つけられます。
そのような文字列が存在しない場合でも、探索は$M+1$回以下で済みます。
では、あり得る文字列をどのように全探索すればいいか考えてみましょう。
まず、$N$個の文字列を並べる、というのはitertools.permutationsを使えばよいです。
問題は、$N$個の文字列の間の_の個数の組の探索です。
個数の組は、$N$個の文字列の順番に関係ありません。
又、個数の組は次のような条件を満たしている必要があります。
個数の組を$L$とすると、$L$の総和は、$16-(Sの文字列の長さの総和)$以下
$L$の要素は全て$1$以上
このような「個数の組」としてあり得る組を探索する訳ですが、メモ化再帰を使って実装します。
DFSの引数に、残りの'_'の個数と探索中のindexを持たせます。
個数の組の探索
memo=[[[] for _ in range(17)] for _ in range(17)]
def DFS(rem,depth):
if memo[rem][depth]:
return memo[rem][depth]
if rem<=0:
return []
if depth==0:
return []
if depth==N-1:
return [[i] for i in range(1,rem+1)]
ret=[]
for i in range(1,rem+1):
for j in DFS(rem-i,depth+1):
ret.append([i]+j)
memo[rem][depth]=ret
return ret
su=16-sum(len(i) for i in S)
L=DFS(su,1)
これで個数の組を全列挙できたので全探索しましょう。
permutations(S)とLで二重ループを回します。
$T$に含まれずかつ条件を満たすものがあれば出力して終了、そうでないならば続行します。
あり得るものが見つからなければ-1を出力すればいいです。
しかしこれだけではコーナーケースに引っ掛かってしまいます。
何が罠となっているのでしょうか。
その罠とは、$X$の文字数制限です。
例えばこのような時にも-1が出力されてしまいます。
コーナーケース
1 0
aaaaa
$N=1$の時、_の「個数の組」が一つもないので、二重ループでの全探索で何も探索できていないことが原因です。
このコーナーケースはこのようにif文を書けば解決できます。
コーナーケースKiller
if N==1:
if 3<=len(S[0])<=16 and S[0] not in T:
print(S[0])
else:
print(-1)
最後に全体の実装を載せます。
特に注意すべき点はありませんが、Tに要素が含まれるかの判定を頻繁に行うので、Tをset型として受け取っておきましょう。
要素検索は、setだと$O(1)$ですがlistだと$O(M)$掛ってしまうので注意。
また、sys.setrecursionlimit(10**9)で再帰呼び出し制限を緩和(?)するのも忘れずに。
全体の実装
import sys
sys.setrecursionlimit(10**9)
from itertools import permutations
N,M=map(int,input().split())
S=[input() for _ in range(N)]
T=set([input() for _ in range(M)])
if N==1:
if 3<=len(S[0])<=16 and S[0] not in T:
print(S[0])
else:
print(-1)
exit()
memo=[[[] for _ in range(17)] for _ in range(17)]
def DFS(rem,depth):
if memo[rem][depth]:
return memo[rem][depth]
if rem<=0:
return []
if depth==0:
return []
if depth==N-1:
return [[i] for i in range(1,rem+1)]
ret=[]
for i in range(1,rem+1):
for j in DFS(rem-i,depth+1):
ret.append([i]+j)
memo[rem][depth]=ret
return ret
su=16-sum(len(i) for i in S)
L=DFS(su,1)
for p in permutations(S):
for l in L:
now=""
for i in range(N-1):
now+=p[i]
now+=l[i]*"_"
now+=p[-1]
if not 3<=len(now)<=16:
continue
if not now in T:
print(now); exit()
print(-1)
中々実装が重く、コーナーケースも意地悪な問題でした。
私も解けなかったので、集中して実装できるようにしたいです。
2 さいごに
最後までお読み頂きありがとうございます。
今回のD問題は最近では中々珍しい問題だったらしいです。
C問題の、$O(N^2)$を$O(N)$にするテクニックは可也重要なので身に付けておきましょう。
以上です。
ありがとうございました。
よい競プロライフを!!
いいねお願いします...(切実)