トップ > AtCoder > AtCoder - 全探索に慣れよう！！！ (2021.4)

AtCoder - 全探索に慣れよう！！！ (2021.4)

AtCoder Python

AtCoder Beginners Selection，ABC196，ABC197に取り組み，全探索の問題を多く解くことが必要だと感じました．

次は，これの「1-6. 「茶色コーダー」になるためのガイドライン」をやろうと思います：レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiita

AOJ 「Introduction To Programming I」

まずはこれからやります．
AIZU ONLINE JUDGE


【2021.4.5】6_Dまでやりました．5_D: Structured Programmingのバグ取りに時間がかかりました．

【2021.4.6】
10-Dまでとき終わりました．
8_Cのインプットが何回あるかわからない場合の処理が参考になりました．
ITP1_8_C

while True:
    try:
        str = input()
    except EOFError:
        break

（参考：解説（Python3））

全探索

1-6-4. 全探索に慣れる！をやっていきます．

ABC144: B - 81

B - 81
2021.04.06：こうしました．

n=int(input())
for i in range(1,10):
  if n%i==0 and n//i<10:
    print('Yes')
    exit()
print('No')

参考になりそうな回答：Submission #10817870 - AtCoder Beginner Contest 144

ABC150: B - Count ABC

B - Count ABC
2021.04.06：まず，探索しない方法はこれが思いつきます．

N=int(input())
print(input().count('ABC'))

探索っぽいことをしたのが次（※スライスでは，添字がオーバーしても良いらしい．←これによりS[N-2:N+1]が定義でき，ループで処理できる．）

N=int(input())
S=input()

ans=0
for i in range(0,N-2):
  if S[i:i+3]=='ABC':
    ans+=1
print(ans)

ABC122: B - ATCoder

B - ATCoder
2021.04.06：初回，最後のif文が必要なことを見落としました．

S=input()
acgt={'A', 'C', 'G', 'T'}
ans=0
tmp=0
for a in S:
  if a in acgt:
    tmp+=1
  else:
    if ans<tmp:
      ans=tmp
      tmp=0
if ans<tmp:
  ans=tmp
print(ans)

あ，むだなことしてました．．．なるほど，これでいいんですね．Submission #4685713 - AtCoder Beginner Contest 122

ABC136: B - Uneven Numbers

B - Uneven Numbers
2021.04.06：ABC196: C - Doubledで同じような問題がありました．この個数なら，全探索できるということですね．

N=int(input())
ans=0
for i in range(1,N+1):
  if len(str(i))%2!=0:
    ans+=1
print(ans)

真面目にやると次の回答例になりますね．Submission #6685973 - AtCoder Beginner Contest 136

ABC106: B - 105

B - 105
2021.04.07：こうしました．

N=int(input())
ans=0
for i in range(1,N+1,2):
  tmp=0
  for j in range(1,i+1,2):
    if i%j==0:
      tmp+=1
  if tmp==8:
    ans+=1
    
print(ans)

ABC120: B - K-th Common Divisor

B - K-th Common Divisor
2021.04.07：こうしました．

A,B,K=map(int,input().split())
tmp=0
for i in reversed(range(1, min(A,B)+1)):
  if A%i==0 and B%i==0:
    tmp+=1
  if tmp==K:
    print(i)
    exit()

ABC057: C - Digits in Multiplication

C - Digits in Multiplication
2021.04.07：こうしました．$O(\sqrt{N})$にできる，ということですかね．以前の問題で，こんなwhile文を見たので，思いつきました．N/iにはint()を噛ませないと，桁数がおかしくなりました．

def f(a,b):
  return max(len(a),len(b))

N=int(input())
i=1
ans=float('inf')
while i<=N**0.5:
  if N%i==0:
    tmp=f(str(i),str(int(N/i)))
    if tmp<ans:
      ans=tmp
  i+=1
print(ans)

ABC096: C - Half and Half

C - Half and Half
2021.04.07：いろんな落とし穴にはまりました．A,Bから決めると2重ループですが，ABから決めるとループ1個で済むのがポイントです．ただし，探索範囲に注意しなくてはなりません（AB2個でA1個・B1個となる）．

A,B,C,X,Y=map(int, input().split())

ans=float('inf')
for i in range(0, int(4e5), 2):
  price=C*i
  if int(i/2)<X:
    price+=A*(X-int(i/2))
  if int(i/2)<Y:
    price+=B*(Y-int(i/2))
  if price<ans:
    ans=price
print(ans)

三井住友信託銀行プログラミングコンテスト2019: D - Lucky PIN

D - Lucky PIN
2021.04.07：結構苦労しました．．．

これだとTLEですね．．．

N=int(input())
S=input()

p=set()
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      p.add(S[i]+S[j]+S[k])
print(len(p))

3桁の数字1000通りを含むか調べるほうが計算量は少なそう，というところまでわかりました．正規表現でマッチすれば良さそうですが，書き方がよくわかりませんでした．とりあえず，次で通りました．なんかすっきりしない．．．

N=int(input())
S=input()

ans=0
for i in range(1000):
  i2=str(i).zfill(3)
  j=S.find(i2[0])
  if j!=-1:
    k=S[j+1:].find(i2[1])
    if k!=-1:
      l=S[j+1:][k+1:].find(i2[2])
      if l!=-1:
        ans+=1
print(ans)

このあと，forで書き直そうとしましたが，簡潔に書く方法を思いつきませんでした．
他の人の回答も，これだ！というものがすぐには見つからず．．．

ABC128: C - Switches

C - Switches
2021.04.07：いきなり難しくなりました．．．ビット使うとかいてあったので，力技でねじ伏せた感じです．途中，bit[s-1]=='1'を==1と書いてあるバグを見つけるのに苦労しました．

N, M=map(int, input().split())

ks=[[] for i in range(M)]
for i in range(M):
  ks[i]=list(map(int ,input().split()))
p=list(map(int ,input().split()))

ans=0
for i in range(2**N):
  bit=str(bin(i))[2:].zfill(N)
  flag=False
  for j in range(M):
    on=0
    for s in ks[j][1:]:
      if bit[s-1]=='1':
        on+=1
    if on%2!=p[j]:
      flag=True
      break
  if flag==False:
    ans+=1
print(ans)

次の回答がきれいでした：Submission #5637081 - AtCoder Beginner Contest 128

ABC147: C - HonestOrUnkind2

C - HonestOrUnkind2
2021.04.08：一日中バグが取れなくて，今日はこれだけです．考え方は，
  1. 「正直者」と「不親切な人」の全パターンのそれぞれに対し，
  2. 正直者の証言が矛盾しないことを確認できれば（そのパターンはあり得る）
  3. そのパターンの「正直者」の人数を数える
とすればよいです．

文字列と整数を比較して，条件が正しく分岐されないバグが最後まで残りました．．．（str(y)のところ）上の問題と同じようなミスですね．．．

N=int(input())
l=[[] for _ in range(N)]
for i in range(N):
  A=int(input())
  tmp=0
  for _ in range(A):
    x,y=map(int, input().split())
    l[i].append([x-1,y])

ans=0
for i in range(1<<N):
  flag=False
  for j in range(N):
    if i&(1<<j):
      for x,y in l[j]:
        if str(y)!=format(i, '0'+str(N)+'b')[N-1-x]:
          flag=True
          break
    if flag:
      break
  else: 
    num=bin(i).count('1')
    if ans<num:
      ans=num
      
print(ans)

提出時刻が早い回答Submission #8852152 - AtCoder Beginner Contest 147が，同じ内容をわかりやすく書いています．条件分岐で上記のようなミスが起きない書き方ですね．参考になります．

ABC145: C - Average Length

C - Average Length
2021.04.09：これも苦労しました．以下を参考にしました．試行錯誤感が出ていると思います．

import math

N = int(input())
p = []
for _ in range(N):
  p.append(list(map(int, input().split())))

d=[['' for _ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(N):
    d[i][j] = ((p[i][0]-p[j][0])**2 + (p[i][1]-p[j][1])**2)**0.5

ans = 0
def dfs(i, depth, dist):
  global ans
  seen[i] = True
  if depth == N:
    ans += dist
  else:
    for j in range(N):
      if seen[j] == False:
        dfs(j, depth+1, dist+d[i][j])
        seen[j] = False

for i in range(N):
  seen = [False for _ in range(N)]
  dfs(i, 1, 0)
  
print(ans/math.factorial(N))

別解を知っていれば，簡単すぎる．みんな別解でやってますね．DFSを参考にしたいのに見つからない．All Submissions - AtCoder Beginner Contest 145

一応，別解 (公式解説)の考え方を書いておきます．町$i,j$の距離を$d_{ij}$とすると求めたいのは

\begin{aligned}
\frac{1}{N!}\sum_{\sigma} d_{\sigma(i)\sigma(j)}
\end{aligned}
です（$\sigma$で置換を表しました．和は，全ての置換をとります）．ここで，各$d_{ij}$が何回出てくるか考えます．すると，$N$個のボールのうち2個をまとめて考えればよく，$(N-1)!$回出てくることになります．したがって，
\begin{aligned}
&\frac{1}{N!} \sum_{i,j=1}^{N} (N-1)! d_{ij} \\
&=\frac{1}{N}\sum_{i,j=1}^{N} d_{ij} \\
&=\frac{2}{N}\sum_{1\leq i < j \leq N} d_{ij}
\end{aligned}
となります（$ d_{ij}=d_{ji},\, d_{ii}=0$）．

ABC150: C - Count Order

C - Count Order
2021.04.10：まず，N!通りの並び順を書き出すをつくってから取り組みました．

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

def dfs(l, depth):
  global a, b, order
  if depth == N:
    order += 1
    if l == P:
      a = order
    if l == Q:
      b = order
  else:
    for i in range (N):
      if all[i] not in set(l):
        dfs(l+[all[i]], depth+1)
        
all = [i for i in range(1, N+1)]
order = 0
dfs([], 0)
print(abs(a - b))

itertoolsのpermutationsを使えばすぐできるようで，そうした回答が多かったです：Submission #9387081 - AtCoder Beginner Contest 150


ABC054: C - One-stroke Path

C - One-stroke Path