競技プログラミング

ABC162

はじめに

この記事では、AtCoder Beginer Contest 162のA~E問題を解説します。

このコンテストから、使用可能言語が変更となりました。
Pythonのバージョンは3.8.2に変更されました。

これでようやく、gcd（最大公約数）のインポートのストレス（Python競プロでやりがちなミス）から解放されました。

A - Lucky 7

https://atcoder.jp/contests/abc162/tasks/abc162_a

問題文に「3桁の整数Nが与えられます」とあるので、intとして扱いたくなりますが、
数字7が含まれているかを確認したいだけなので、文字列として扱うのが良いでしょう。

1
2
3
4
5
N = input()
if '7' in N:
    print ('Yes')
else:
    print ('No')

B - FizzBuzz Sum

https://atcoder.jp/contests/abc162/tasks/abc162_b

問題文がちょっとややこしい気がしますが、「N項目までに含まれる数の和を求めてください。」とあるので、要するに3の倍数でも5の倍数でもない数を足せば良いです。

気をつけるのはrangeの範囲くらいでしょうか。

1
2
3
4
5
6
N = int(input())
ans = 0
for n in range(1,N+1):
    if (n%3 != 0 and n%5 != 0):
        ans += n
print (ans)

C - Sum of gcd of Tuples (Easy)

https://atcoder.jp/contests/abc162/tasks/abc162_c

GCDの問題です。Pythonistaとしてはこのタイミングで、GCDを出してくることに運命を感じますね。

gcd(a,b,c) = gcd(gcd(a,b),c)

であるため、単純にループを回せば良いです。

ただし、Pythonの場合は計算が結構ギリギリなので、gcd(a,b)の部分を使いまわします。

他の方のコードを見ていると、この高速化をしないで通している方もいました。

1
2
3
4
5
6
7
8
9
from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        gcd_ij = gcd(i, j)
        for k in range(1,K+1):
            ans += gcd(gcd_ij, k)
print (ans)

D - RGB Triplets

https://atcoder.jp/contests/abc162/tasks/abc162_d

まずは、一つ目の条件（全ての文字が異なる組）を数えます。

その後、二つ目の条件を満たす組を数えて引きます。

Pythonで文字列中に指定した文字がいくつ含まれるかを数えたい場合はcountが便利です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
N = int(input())
S = input()
ans = S.count('R') * S.count('G') * S.count('B') # 一つ目の条件

for i in range(N):
    for j in range(1,N): # 1から
        if (i-j<0 or i+j>=N): # リストの範囲内かを確認
            break
        l = S[i-j]
        m = S[i]
        r = S[i+j]
        if l!=m and m!=r and r!=l: # 二つ目の条件
            ans -= 1
print (ans)

E - Sum of gcd of Tuples (Hard)

https://atcoder.jp/contests/abc162/tasks/abc162_e

ほとんど解説PDFの通りです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MOD = int(1e+9 + 7) # 忘れずにintをつける
N, K = map(int, input().split())
 
cnt = [0] * (K + 1) # 後々のことを考え、サイズをK+1にする
　               
for x in range(1, K + 1): # 先頭0は使わない
    cnt[x] = pow(K // x, N, MOD) # 要素が全てXの倍数となるような数列の個数をXごとに求める
 
for x in range(K, 0, -1): # 大きい順に計算
    for i in range(2, K // x + 1): # 2X, 3Xの個数を求めてひく
        cnt[x] -= cnt[x * i]

ans = 0
for k in range(K+1):
    ans += cnt[k] * k # gcdがkである組はA[k]個ある
ans = ans % MOD # ここでもMODをつける
print(ans)

ちょっとプリントデバッグを仕込んでみましょう。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MOD = int(1e+9 + 7) # 忘れずにintをつける
N, K = map(int, input().split())
 
cnt = [0] * (K + 1) # 後々のことを考え、サイズをK+1にする
　               
for x in range(1, K + 1): # 先頭0は使わない
    cnt[x] = pow(K // x, N, MOD) # 要素が全てXの倍数となるような数列の個数をXごとに求める
print (cnt)

for x in range(K, 0, -1): # 大きい順に計算
    for i in range(2, K // x + 1): # 2X, 3Xの個数を求めてひく
        cnt[x] -= cnt[x * i]
print (cnt)

ans = 0
for k in range(K+1):
    ans += cnt[k] * k # gcdがkである組はA[k]個ある
ans = ans % MOD # ここでもMODをつける
print(ans)

そして、プログラムを実行し3 2を入力して下さい。

1
2
3
4
3 2
[0, 8, 1]
[0, 7, 1]
9

[0, 8, 1]は

  • 0: 先頭の要素はダミー
  • 8: 全てが1の倍数となる数列の数
  • 1: 全てが2の倍数となる数列の数

[0, 7, 1]は

  • 0: 先頭の要素はダミー
  • 7: GCD=1となる数列の数
  • 1: GCD=2となる数列の数

となっていることが確認できます。

記事情報

  • 投稿日：2020年4月13日
  • 最終更新日：2020年4月13日