masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

ABC129 C - Typical Stairs 解説

AtCoder python3 競技プログラミング 高校数学

はじめに

Pythonで実装しました．そんなところで差が出るなんて，，，という学びがあったので記事にします．

問題

ABC123 C - Typical Stairs

考え方

いわゆるDPの基本的な問題なのだとおもいます．フィボナッチ数列と同じです．

1歩または2歩進めるとうことは，Ｎ段目に到達する方法はN-1段目から来る，またはN-2段目から来るの2通りです．したがってdp[N]をN段目に到達する方法とすれば，

dp[N] = dp[N-1] + dp[N-2]

と表すことができ，これはフィボナッチ数列の一般項と同じです．ここに壊れている床は使えないという条件を加えてやればACとなります．

TLEした実装

mod = 1e+9+7
 
# 入力の受け取り
N, M = map(int,input().split())
#壊れて使えない床をリストAに格納
A = [int(input()) for _ in range(M)]
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#DP遷移を計算
for i in range(2,N+1):
　#i段目が使えない床の場合はdp[i]=0とする
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
    
print(int(dp[N]))

ACした実装

mod = 1e+9+7

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

#壊れた床の格納方法を変更
#床iが使えるときはA[i]=True
#床iが使えないときはA[i]=False
A = [ True for _ in range(N+1)]
for i in range(M):
    A[int(input())] = False

dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if A[1] == True else 0
for i in range(2,N+1):
    #dpを計算するときのifの条件式もAに合わせて変更
    if A[i]: dp[i] = (dp[i-1] + dp[i-2])%mod
   
print(int(dp[N]))

これでTLEが解消されてACとなりました．

大学入試

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする．15段の階段を昇る昇り方は何通りあるか．（07 京都大　文 ）

競プロが大学入試にも役立つ好例ですね！！中高生も胸をはって競プロにいそしみましょう！

ABC186 解説（A～C）

AtCoder python3 競技プログラミング 高校数学

A - Brick

A - Brick

N=12，w = 5のときは，2個の荷物を載せることができる（3個目を載せると15キログラムとなりオーバーする）． これを素直に式に表すと 12÷5 = 2\cdots 3となる（\cdotsは余りを表す）．

従って，この計算の商の部分が答えになる．pythonでは切り捨て処理は//で記述できる．

N, W = map(int,input().split())
print(N//W)

B - Blocks on Grid

B - Blocks on Grid

ブロックを取り除くことしかできないので，すべてのマスの中でブロック数が一番少ないマスのブロック数に他のマスのブロック数を合わせるしかない．

おおむね次のような処理とした．

  • 入力の1行ごとに，その行の最小値を保存するようにして，すべての入力が終わったあとで，それらの中から全体の最小値を取得
  • H\times W個の要素を走査し，その中で先の最小値との差を合計していく
H, W = map(int,input().split())
A = []
mins = []
for i in range(H):
  a = list(map(int,input().split()))
  A.append(a)
  mins.append(min(a))
ans = 0
m = min(mins)
for i in range(H):
  for j in range(W):
    ans += A[i][j] - m

print(ans)

C - Unlucky 7

少し難しかった．

  • 各桁に7が出てくるかどうかのチェックが必要であり，それは整数型のままではできないので，文字列に変換して文字列の7を含むかどうかを判定する．

  • 10進数については，ただ文字列に変換して上記の処理を行えばよい

  • 8進数については，10進数を8進数に変換する処理が必要になる．

8進数への変換

実は，pythonには関数が用意されている(https://docs.python.org/ja/3/library/functions.html#oct)． ただ，ここでは向学のため8進数への変換も実装することとする．

進数について

カンジをつかむ

そもそも10進数とはどのような数の表し方かを確認する．例えば2345（二千三百四十五）は 2345 = 2000 + 300 + 40 + 5 = 2 \times 10^{3} + 3 \times 10^{2} + 4 \times 10^{1} + 5 \times 10^{0} と書き直すことができる． この各位の数2,3,4,5以外の部分に注目して10^{x}という形になっている．この部分が10なので10進法と呼んでいる．

では，8進数で3456_8と表されているという数は（10進数では）どのような数になるかというと，それは 345_8 = 3\times 8^{3} + 4\times 8^{2} + 5\times 8^{1} + 6 \times 8^{0}となる．ちなみにこれを計算すると1880である（もちろんこれは10進数）．※3456_8の右下の小さい8は，8進数で表していることを明示するためにつけている）

8進数を10進数に変換する

これで，８進数，10進数のカンジはつかめたのではないかと思うので，次は10進数で表された数を8進数に変換することを考える． 先の2345 _{10}を8進数に変換することを考える．8進数での表記は8^{x}というかたまりを作れば良い．下の桁から順番に調べよう．一番下の桁はk\times 8^{0}となっており，kは1～7のいずれかである（もしk=8なら，繰り上がって，8^{1}の桁の方に出てくることになる）．

したがって一番下の桁は，元の数字を8で割った余りを取ればよい． 2345÷8 = 293\cdots 1となり，最下位桁は1とわかる．

次に下から2番目の桁を求める．今，最下位桁は「●●▲◆」の◆の部分を８で割った余りとして求めたので，次の桁は一番下の◆を切り落とした「●●▲」に対して8 で割った余りを求めればよい．この一番下の◆を切り落とす方法を考える．

実は簡単である．10進法で考えると，1234を123にするには，10で割って小数点以下を切り落とせばよい．ここで10で割ることで一番下の桁が落ちるのは10進数だからである．

したがって今は8進法で考えているので8で割って小数点以下を切り捨てれば目的のものが得られ，それを8で割った余りを求めればよい．

2345÷8=293.125なので293とし，さらに293÷8=36\cdots 5となり下から2番目の桁は5だとわかる．

あとはこれを繰り返せばよい．計算式のみ記す．

293÷8 = 36.625となり36÷8 = 4\cdots4

36÷8 = 4.5となり4÷8 = 0\cdots4

4÷8 = 0となり0÷8 = 0\cdots0となりここで終わり．

したがって，2345_{10} = 4451_8であることがわかった．これを実装すると次のようになる．

def to_oct(n):
  s = ''
  while(n):
    s = str(n%8) + s
    n //= 8
  return s

ans = 0
N = int(input())
for i in range(1,N+1):
  if '7' not in str(i)  and '7' not in to_oct(i):
    ans += 1
print(ans)

ABC187 解説（D - Choose Me）

AtCoder python3 競技プログラミング

D - Choose Me

D - Choose Me

  • 貪欲法を用いる

何もしなければ，青木君はA_iすべての票を，高橋君は0票となる．もし，町iで高橋君が演説をすれば，青木君の票がA_i票減り，高橋君の票がB_i票増える．注意点は「 青木君の総得票数」<「高橋君の総得票数」となるときの演説回数なので，高橋君が得票すること以外にも青木君の票を減らすことも重要である．

どの町で演説するのがよいか

ある町の青木派が a人，高橋派が b人いたとする．この町で演説する場合としない場合の青木君と高橋君の得票数の差を調べる．

演説なし 演説あり
青木君 a 0
高橋君 0 a+b

となることから，演説ありと，演説なしのときの得票数の差の差は (a+b) - 0 )- (0-a) = 2a+bである．つまり，この町で演説した場合2a+b票だけ青木君の得票数と，高橋君の得票数の差が縮まることがわかる．したがって，この値が大きい町から順番に演説をすればよい．したがって，次のような実装になる．

N = int(input())
AB = []
for i in range(N):
  a,b = map(int,input().split())
  AB.append([2*a+b,a,b])

AB.sort(reverse = True)
sumA = 0
sumB = 0
for x in AB:
  sumA += x[1]

ans = 0
if sumA < sumB:
  print(ans)
  exit()
for i in range(N):
  sumA -= AB[i][1]
  sumB += AB[i][1] + AB[i][2]
  ans += 1
  if sumA < sumB:
    print(ans)
    exit()

ABC187 解説（A～C）

AtCoder 高校数学 python3

はじめに

Twitterを見ていると，意外と競技プログラミングに出てくる高校数学に慣れ親しんでいない人が多いという話だったので，簡単な問題でも解説記事は需要があるかもしれないと思ったので，解説記事を書くことにしました．また，最近ABCにはあまり参加できていなかったのですが公式Editorialはテキストベースから動画ベースに変わったのでしょうか？動画を見るのがめんどくさい，移動中なのでテキストが良いという人もいそうなのでそういう意味でも解説記事は価値がある（と思いたい）．なお，Pythonでの解説とする．

A - Large Digits

A - Large Digits - 3桁の文字列を1桁ずつに分割する - 文字列をint型に変換する という2つのことができればＯＫ

A, B = input().split()

if int(A[0]) + int(A[1]) + int(A[2]) < int(B[0]) + int(B[1]) + int(B[2]):
  print(int(B[0]) + int(B[1]) + int(B[2]))
else:
  print(int(A[0]) + int(A[1]) + int(A[2]))

Pythonでは文字列はリストのようにindex（何文字目か）を指定してその文字を取り出すことができます．さらにそれをintで囲んで整数型に変換して和を求めればＯＫです．
別解

sumA = sum(int(i) for i in A)

のようにしていっぺんに整数に変換することもできます．

A, B = input().split()
sumA = sum(int(i) for i in A)
sumB = sum(int(i) for i in B)
if sumA < sumB:
  print(sumB)
else:
print(sumB)

B - Gentle Pairs

B - Gentle Pairs - 2点の座標から直線の傾きを求める ことができればＯＫです．ここで，その方法を復習します．

そもそも，（ xy平面上の）直線は y = ax + bという形で表すことができます（実はこの形ではx=kというようなy軸に平行な直線を表すことができない．しかし，このようなことが起こるのは2点のx座標が一致するときであり，今の問題では条件からこのような状況は除外されている）．このaを傾き，bを（y）切片といいます．今の問題では切片は関係ないのでaについてだけ考えます．

傾きaの求め方

公式的に書けば，直線の傾きは「yの増加量／xの増加量」となります．

f:id:masuTomo:20210105212407p:plain
つまり，2点のx座標の差とy座標の差を計算すればよい．
　　 したがって，2点の座標をそれぞれ(x_1,y_1),(x_2,y_2)とすると，傾きを\frac{y_2-y_1}{x_2-x_1}として求めることができる．したがって，問題文に書かれている条件は -1 \leq \dfrac{y2-y1}{x2-x1} \leq 1ということになる．しかし，これをそのまま実装してしまうとWAとなってしまう．テストケースがわからないので想像だが，傾きを求めるときの除算の処理で誤差が発生したものによると考えられる．

除算での誤差への対処

では，どうすればよいかと言えば条件の不等式-1 \leq \frac{y_2-y_1}{x_2-x_1} \leq 1の分母を払ってしまえばよい．つまり不等式全体にx_2-x_1を掛けるのである．ただし，ここでも注意が必要で，それは不等式に掛け算をするときは掛ける値がマイナス（負）の場合は不等号の向きが反対になってしまうのである．しかも，今のままではx_1とx_2のどちらが大きいかわからないので，x_2-x_1が正なのか負なのかが確定しない（iによって異なる）．そこで，傾きを計算する前にx_1とx_2の大小をチェックして，次のようにしてx_1の方を小さくなるようにしておけばよい（あるいは絶対値を用いても良い）．

if x1 > x2: x1, x2 = x2, x1

こうしておくことで，分母を払うときに不等号の向きを変えなくて済むようになる．

以上のことを考慮して実装すると次のようになる．

N = int(input())
XY = []
for i in range(N):
  x, y = map(int,input().split())
  XY.append([x,y])

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    x1, y1 = XY[i][0], XY[i][1]
    x2, y2 = XY[j][0], XY[j][1]
    #(x1,y1)を左側にする
    if x1 > x2:
      x1, x2 =x2, x1
      y1, y2 =y2, y1
    if x1 - x2 <= y2-y1 <= x2-x1: ans += 1

print(ans)

C - 1-SAT

C - 1-SATは，与えられた文字列の中に，すべての文字列について「abc」だけ，または「!abc」だけがあるような状況になっているときに限り「satisfiable」である．したがって，Pythonではsetを用いて「!」が混じっている文字列のセットと「!」が混じっていない文字列のセットを用意し，それらのセットを比べればよい．

N = int(input())
SE = set()
S = set()
for i in range(N):
  s = input()
  if '!' == s[0]:
    SE.add(s[1:])
  else:
    S.add(s)
for s in S:
  if s in SE:
    print(s)
    exit()

for s in SE:
  if s in S:
    print(s)
    exit()
    
print('satisfiable')

アルゴリズムとデータ構造（けんちょん本）4.1,4.2

競技プログラミング python3

トリボナッチ数列を計算するプログラム

メモ化なし

import time

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  return  tori(n-1) + tori(n-2) + tori(n-3)

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

として、標準入力から第何項を求めるか入力させる形とした。k=50とすると手元の環境（Google colab）ではしばらく待っても終了しなかった。

メモ化あり

#import sys
#sys.setrecursionlimit(100000)

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  if memo[n] == -1:
    memo[n] = tori(n-1) + tori(n-2) + tori(n-3)

  return memo[n]

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

メモ化して実行するとk=50としても0.00018秒程度で結果が返ってきた。メモ化すごい。

計算量

メモ化した場合の計算量はO(N)と思われる。
メモ化しない場合の計算量はいくつだろう？（章末問題4.3をやります）

アルゴリズムとデータ構造（けんちょん本）4.1,4.2

競技プログラミング python3

トリボナッチ数列を計算するプログラム

メモ化なし

import time

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  return  tori(n-1) + tori(n-2) + tori(n-3)

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

として、標準入力から第何項を求めるか入力させる形とした。[tex;k=50]とすると手元の環境（Google colab）ではしばらく待っても終了しなかった。

メモ化あり

#import sys
#sys.setrecursionlimit(100000)

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  if memo[n] == -1:
    memo[n] = tori(n-1) + tori(n-2) + tori(n-3)

  return memo[n]

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

メモ化して実行するとk=50としても0.00018秒程度で結果が返ってきた。メモ化すごい。

計算量

メモ化した場合の計算量はO(N)と思われる。
メモ化しない場合の計算量はいくつだろう？（章末問題4.3をやります）

アルゴリズムとデータ構造（けんちょん本）3.4

競技プログラミング python3

アルゴリズムとデータ構造（けんちょん本）

この本の気になった章末問題等をPythonでやったりして更新してみることにする。いつまで続くかはわからない。おかしな点があれば教えてください。

章末問題3.4

#入力の受け取り
#入力でa_1, a_2, ,,,,a_Nを受け取る
A = list(map(int,input().split()))

#最大値，最小値はこの範囲内に収まっているとする
max = -10000000
min =  10000000

#Aは長さNなのでO(N)
for i in range(len(A)):
  if A[i] > max:
    max = A[i]
  if A[i] < min:
    min = A[i]
#差の最大値は最大値―最小値で得られる。
print(max-min)

これでええんか？