競技プログラミング

ABC165

はじめに

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

A - We Love Golf

https://atcoder.jp/contests/abc165/tasks/abc165_a

シミュレーションをすれば十分に間に合います。

1
2
3
4
5
6
7
k = int(input())
a, b = map(int,input().split())
for i in range(a,b+1):
    if i%k==0:
        print ('OK')
        exit()
print ('NG')

B - 1%

https://atcoder.jp/contests/abc165/tasks/abc165_b

入力例2でXの上限である10**18に対する答えが3760とわかります。

預金額は単調増加するので、3760回以上ループを回せば十分です。

1
2
3
4
5
6
7
X = int(input())
d = 100
for i in range(4000):
    d = int(d * 1.01)
    if d >= X:
        print (i+1)
        exit()

C - Many Requirements

https://atcoder.jp/contests/abc165/tasks/abc165_c

リストから要素を重複を許して選択し、新たなリストを作成します。ただし、新たなリストの各要素に対応する元リストのインデックス番号が単調増加するという条件を付けます。

これは深さ優先探索で解くことができますが、Pythonの場合はitertools.combinations_with_replacement
で直接求めることができます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import itertools
N, M, Q  = map(int,input().split())
query = []
for q in range(Q):
    a,b,c,d = map(int,input().split())
    a-=1
    b-=1
    query.append((a,b,c,d))
mx = 0
for comb in itertools.combinations_with_replacement([i for i in range(1,M+1)],N):
    score = 0
    for a,b,c,d in query:
        if (comb[b] - comb[a] == c):
            score += d
    mx = max(score,mx)
print (mx)

D - Floor Function

https://atcoder.jp/contests/abc165/tasks/abc165_d

関数の値はxに対して周期Bで変化することが直感的に分かる。
そこでx=pB+qとおく。（q<B）

1
2
floor(Ax/B) = pA+floor(Aq/B)
A*floor(x/B) = pA

となるので、元の関数は

1
floor(Aq/B)

となる。q<Bであるため、この関数はqに対して単調増加である。

よって、NとB-1のうち小さい値が答えとなる。

1
2
3
4
A, B, N = map(int,input().split())
x = min(B-1,N)
ans = (A*x)//B - A * (x//B)
print (ans)

E - Rotation Matching

https://atcoder.jp/contests/abc165/tasks/abc165_e

（初期に割り当てられる）参加者番号の差分が1,2,3,4,..となるように対戦場に番号を割り振ることができれば制約を満たすことができる。
そのような割り振り方は、解説pdfの通りに参加者をM//2人のグループと(M+1)//2人の2つのグループに分ければよい。

1
2
3
4
5
N, M = map(int, input().split())
for i in range(M//2):
    print(i+1, M-i)
for i in range((M+1)//2):
    print (M+1+i,2*M+1-i)

F - LIS on Tree

https://atcoder.jp/contests/abc165/tasks/abc165_f

深さ優先探索とLISの組み合わせで解くことができます。

LISの基本については下記の問題で練習するのが良いでしょう。
ABC006D - トランプ挿入ソート

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import bisect
import sys
sys.setrecursionlimit(10**6)
INF = 10**10

N = int(input())
A = [0] + list(map(int,input().split()))

adj = [[] for n in range(N+1)]
for n in range(N-1):
    u, v = map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)

ans= [0 for i in range(N+1)]
depth = [-1 for n in range(N+1)]
def dfs(s, d, dp): # 頂点番号、深さ、LIS
    depth[s] = d
    idx = bisect.bisect_left(dp,A[s])
    history = dp[idx] # 巻き戻すために保存
    dp[idx] = A[s]
    ans[s] = bisect.bisect_left(dp, INF)
    for i in adj[s]:
        if depth[i]==-1:
            dfs(i, d+1, dp)
    dp[idx] = history # 探索が終わったら巻き戻す
dp = [INF] * len(A)
dfs(1, 0, dp)
for n in range(1,N+1):
    print(ans[n])

関連記事

過去のABC解説記事です。

  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日：2020年5月2日
  • 最終更新日：2020年5月3日