競プロ初心者による全探索の練習

https://qiita.com/e869120/items/f1c6f98364d1443148b3#%E6%9D%A1%E4%BB%B6-1
この中の全探索を解いてみた。

ABC144B
https://atcoder.jp/contests/abc144/tasks/abc144_b
特に問題なし。

import sys

n=int(input())
m=list(range(1,10))
for i in range(1,10):
  N = n/i
  if N in m:
    print('Yes')
    sys.exit()
print('No')

二回目。復習。

import sys

n=int(input())
for i in range(1,10):
  for j in range(1,10):
    if i*j == n:
      print('Yes')
      exit()
print('No')
      

計算量はO(1)

ABC150B

n = int(input())
s = input()
ans=0
for i in range(n-2):
  if s[i:i+3]=='ABC':
    ans+=1
print(ans)

これも特に問題なし。input()で受け取った文字列をそのままスライシングできる。
あとはスライシングするときの引数で後ろは入らないので、i+2にしないように注意。

２回目はsearchメソッドを使おうとしたがぱっと出てこなかった。
文字列のカウントにはこれがいいかも??
https://yu-nix.com/archives/python-str-find/#count()%E3%81%A7%E6%96%87%E5%AD%97%E5%88%97%E3%82%92%E3%82%AB%E3%82%A6%E3%83%B3%E3%83%88

n=int(input())
s=input()
n=s.count('ABC')
print(n)

上記の記事見てcount()使ったらめっちゃ楽だった…。計算量はO(n)

---

import math
n=int(input())
digit=int(math.log10(n))+1
for i in range(1,digit-2,2):

桁数nを求めて、1~n-1の間で偶数の桁は0、奇数の桁は9、nは数え上げて…とやろうとしたが、めんどくさい。

N = int(input())

count = 0
for i in range(1, N + 1):
    if len(str(i)) % 2 == 1:
#len()関数は文字列やリストなどのシーケンス型の要素数を取得するために用いられる関数であり、整数型に対しては使うことができない。整数型の桁数を調べるためには、文字列に変換する必要がある。

        count += 1
#一つずつ桁数を調べ、奇数であれば+1して言っている
print(count)

これで十分。計算量オーダーもO(NlogN)で済む。

ABC106B

#1~n/2までの範囲で割り切れるか奇数の中で二重ループ、カウント
n=int(input())
ans=0
for i in range(1,n+1,2):
  count=0
  for j in range(1,int((n+1)/2)):
    if i%j ==0:
      count+=1
      if count==4:
        ans+=1
print(ans)

これでWAだった。
半分に分けてやれば早いと思ったが、25＝5*5の場合は因数は一つか。ややこしくなるから普通にやったほうがよかったな。

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

これでAC。

ABC120B

a,b,k = map(int, input().split())
factor_a = set(i for i in range(1,a+1) if a%i == 0)
factor_b = set(j for j in range(1,b+1) if b%j == 0)
commons=list(factor_a.intersection(factor_b))
commons.sort()
print(commons[k-1])

これでWA。なんでダメなのかわからない。

a,b,k = map(int, input().split())
count=0
for i in range(1,101):
  if a%i == 0 & b%i == 0:
    count += 1
    if count==k:
      print(i)

これでもWAだった。なぜだめなのか。
ABC57C

import math
import sys
n = int(input())
sqrt_n = math.sqrt(n)
ceil_n=math.ceil(sqrt_n)
N = int(ceil_n)
for i in range(N,n+1):
  ans = n%i
  if ans == 0:
    digit_count=len(str(i))
    print(digit_count)
    exit()

最初はこのコードを書いたがTLEになってしまった。
chatGPTに聞いたところ以下のように改善してくれた。

import math
n = int(input())
min_digits = len(str(n))
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        other_factor = n // i
        max_factor_digits = max(len(str(i)), len(str(other_factor)))
        min_digits = min(min_digits, max_factor_digits)
print(min_digits)

考えていた方針は似ているのに上はO(n)で下はO(sqrt_n)と計算量は異なるらしい。
うーん不思議というか難しい…

ABC095C

A,B,C,X,Y=map(int,input().split())
Ans=0
Z=min(X,Y)
if A+B >= C*2:
  Ans=min(C*Z*2 + A*(X-Z) + B*(Y-Z),C*max(X,Y)*2)
else:
  Ans=A*X + B*Y
print(Ans)

答えを見て理解。
min関数がめちゃくちゃ便利。5行目のところは今までなら場合分けしていた。
どちらか小さいほう、どちらか大きいほうを出力する場合min,max関数は積極的に利用していきたい。