【AtCoder】C問題をPythonで全制覇する（ABC150～199）【解説・分類】

アルゴリズム

2022.12.12

いくつかの記事を参考にしていますが、基本的に自力で解答することを目指しました。

今後に生かせるよう、汎用的で一般的な実装を行うことを心掛けました。

また、辞書的に利用できるよう、各問題に（個人的な）分類を記載しました。Ctrl + F のショートカットキーを使って、キーワードで問題を検索できます。

前回の記事

【AtCoder】C問題をPythonで全制覇する（ABC100～149）【解説・分類】

本記事ではAtCoderABCコンテストC問題について、考え方とPythonでの解答を紹介しています。汎用的でシンプルな解き方を心掛けています。また、辞書的に利用できるよう、各問題に分類を記載しました。Ctrl + F で問題をキーワード検索できます。

ABC150 C – Count Order（順列全探索）

C – Count Order (atcoder.jp)

N の最大値は8なので、順列全探索が可能.
順列の辞書順の小さいほうから、P, Qのリストとの一致をチェックする.

from itertools import permutations
N = int(input())

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

pairs = permutations([i + 1 for i in range(N)])

for i, pair in enumerate(pairs):
    if list(pair) == P:
        a = i
    if list(pair) == Q:
        b = i

print(abs(a - b))

ABC151 C – Welcome to AtCoder（カウント）

C – Welcome to AtCoder

「初めて出した」 AC や「初めて AC を出すまでに出した」 WAを、どう表現するかが問題.
AC が０の内は WA の数を数えていき、AC が１度出たらカウントをやめる.

from collections import Counter
ctr_ac = Counter()
ctr_wa = Counter()

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

acc = 0
for _ in range(M):
    p, s = input().split()
    p = int(p)
    
    if s == "WA" and ctr_ac[p] == 0:
        ctr_wa[p] += 1
        
    if s == "AC" and ctr_ac[p] == 0:
        ctr_ac[p] = 1
        
ac = 0
wa = 0
for key in ctr_ac.keys():
    ac += ctr_ac[key]
    wa += ctr_wa[key]
    
print(ac, wa)

ABC152 C – Low Elements（最小値）

C – Low Elements (atcoder.jp)

先頭から順に見ていき、今までに出てきた要素以下であればans += 1.
今までに出てきた要素の最小値だけを更新していけばよい.

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

mini = P[0]
ans = 1
for i in range(1, N):
    mini = min(mini, P[i - 1])
    if mini >= P[i]:
        ans += 1
print(ans)

ABC153 C – Fennec vs Monster（ソート）

C – Fennec vs Monster (atcoder.jp)

N, K = map(int, input().split())
H = sorted(list(map(int, input().split())))

# 必殺技で倒しきれないとき
if N > K:
    print(sum(H[:N - K]))
# 必殺技で倒しきれるとき
else:
    print(0)

ABC154 C – Distinct or Not（集合）

C – Distinct or Not (atcoder.jp)

N = int(input())
A = list(map(int, input().split()))

if len(set(A)) == N:
    print("YES")
else:
    print("NO")

ABC155 C – Poll（カウント・ソート）

C – Poll (atcoder.jp)

各文字列をカウント.
カウント数の最大値 maxi を取得.
カウント数が maxi に等しい文字列を抽出し、sort で辞書順に並び替える.

from collections import Counter
cnt = Counter()

N = int(input())

for _ in range(N):
    s = input()
    cnt[s] += 1
    
maxi = max(cnt.values())

ans = []
for key, value in cnt.items():
    if value == maxi:
        ans.append(key)

ans.sort()

print(*ans, sep = "\n")

ABC156 C – Rally（ユークリッド距離の最小値）

C – Rally (atcoder.jp)

N = int(input())
X = list(map(int, input().split()))

# 自乗距離の総和を求める関数
def sq_dist(X, p):
    dist = 0
    for x in X:
        dist += (x - p) ** 2
    return dist

ans = 10 ** 7
for i in range(101):
    ans = min(ans, sq_dist(X, i))

print(ans)

ABC157 C – Guess The Number（場合分け）

C – Guess The Number (atcoder.jp)

１桁目が０になってはいけないなど、分岐が少し面倒.
正確な順で条件分岐を書かないと、一部のケースでWAが出てしまう.

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

idx = [-1] * N
flag = True
for _ in range(M):
    s, c = map(int, input().split())
    s = s - 1

    if idx[s] == -1:
        idx[s] = c
    else:
        if idx[s] != c:
            flag = False
            break

if N != 1 and idx[0] == 0:
    flag = False
    
if flag:
    if N > 1 and idx[0] == -1:
        idx[0] = 1 
    print("".join([str(max(i, 0)) for i in idx]))
else:
    print(-1)

ABC158 C – Tax Increase（場合分け）

C – Tax Increase (atcoder.jp)

A, B = map(int, input().split())
flag = False
for i in range(1, 1001):
    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        flag = True
        break
if not flag:
    print(-1)

ABC159 C – Maximum Volume（相加相乗平均不等式）

C – Maximum Volume (atcoder.jp)

答えが整数でなくて良いとの記載から、全探索は不可能.
結局立方体が最大体積.

L = int(input())
print((L / 3) ** 3)

ABC160 C – Traveling Salesman around Lake（max）

C – Traveling Salesman around Lake (atcoder.jp)

一番遠い家間の距離を移動しない方法をとる.
一番遠い家間の距離を求め、円周 K から引けばよい.

K, N = map(int, input().split())
A = list(map(int, input().split()))

maxi = A[0] + (K - A[N - 1])
for i in range(1, N):
    maxi = max(maxi, A[i] - A[i - 1])
    
print(K - maxi)

ABC161 C – Replacing Integer （場合分け）

C – Replacing Integer (atcoder.jp)

$K \le x$の時、$|x – K|$はただの引き算$x = x – K$に等しい.
$K > x$の時、$|x – K|$は$K – x$に等しい.
後者の時（x が割る数 K より小さくなっているとき）、x = x % Kとなっている.

N, K = map(int, input().split())
print(min(N % K, -N % K)) # = min(N % K, K - (N % K))

ABC162 C – Sum of gcd of Tuples (Easy)（最大公約数）

C – Sum of gcd of Tuples (Easy) (atcoder.jp)

import math

K = int(input())

ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        gcd_ij = math.gcd(i, j)
        for k in range(1, K + 1):
            ans += math.gcd(gcd_ij, k)
            
print(ans)

ABC163 C – management（インデックスの利用）

C – management (atcoder.jp)

部下 i の持つ上司の値 Ai がある.
上司 Ai の持つ値（部下の人数）に + 1.

N = int(input())
A = list(map(int, input().split()))

g = [0] * N
for a in A:
    g[a - 1] += 1
    
for i in g:
    print(i)

ABC164 C – gacha（集合）

C – gacha (atcoder.jp)

N = int(input())
print(len(set([input() for _ in range(N)])))

ABC165 C – Many Requirements（重複あり組み合わせ全探索）

C – Many Requirements (atcoder.jp)

直感で理解できないときは、具体例を紙とかに描いて理解する.
1からMの数字から、N個取り出す組み合わせを全列挙.
各Aiは同じものが２つ以上有ってもよいから、重複ありの組み合わせ.
それらに対し、Q個の要求のそれぞれを満たせるか調べる.

import itertools
N, M, Q = map(int, input().split())

cr = itertools.combinations_with_replacement([i + 1 for i in range(M)], N)

abcd = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for i in cr:
    tot = 0
    for j in abcd:
        a, b, c, d = j[0], j[1], j[2], j[3] 
        a -= 1
        b -= 1
        if i[b] - i[a] == c:
            tot += d
    ans = max(ans, tot)

print(ans)

ABC166 C – Peaks（max）

C – Peaks (atcoder.jp)

ざっと読んだ感じ、（Peaks => 文字通り）極大域はいくらあるかという問題.
各展望台に対し、隣接する展望台の中で最も高いものと、高さを比較すればよい。

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

# neighbor
# 各展望台 i について
# 隣接する展望台の中で最も高いもの
neig = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neig[a] = max(neig[a], H[b])
    neig[b] = max(neig[b], H[a])

ans = 0
for i in range(N):
    if H[i] > neig[i]:
        ans += 1
        
print(ans)

ABC167 C – Skill Up（ビット全探索）

C – Skill Up (atcoder.jp)

初めて、自力かつWAを出さず、ビット全探索の実装をできた！

各本について買うか買わないかの２通りがある.
買う・買わないの全2^N通りの状態をビット全探索する.
各状態 st について、
・全てのアルゴリズムの理解度が X 以上か？
・それを満たす場合、合計金額 ans を更新する.

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

prices = []
A = []
for _ in range(N):
    s = list(map(int, input().split()))
    prices.append(s[0])
    A.append(s[1:])

ans = 10 ** 7
for st in range(1 << N):
    scores = [0] * M
    tot = 0
    for i in range(N):
        # i 番目の参考書を買う場合
        if st >> i & 1:
            tot += prices[i]
            for j in range(M):
                scores[j] += A[i][j]
    if all(sc >= X for sc in scores):
        ans = min(ans, tot)
        
print(ans if ans != 10 ** 7 else -1)

ABC168 C – : (Colon)（二次元極座標）

C – : (Colon) (atcoder.jp)

H 時 M 分 => minutes 分　と変換.
その時刻までに、２つの針が回った角度を計算.
角度を基に、座標に焼き直し、２つの針の先端の座標間の距離を出す.
math の三角関数は引数の単位を radian とすることに注意.

import math
A, B, H, M = map(int, input().split())

# H : M 
minutes = H * 60 + M
h_deg = (minutes / 2) % 360 # １分あたり 1/2 °回る
m_deg = (minutes * 6) % 360 # １分あたり6°回る

h_rad = math.radians(h_deg)
m_rad = math.radians(m_deg)

h_x, h_y = A * math.cos(h_rad), A * math.sin(h_rad)
m_x, m_y = B * math.cos(m_rad), B * math.sin(m_rad)

print(((h_x - m_x) ** 2 + (h_y - m_y) ** 2) ** 0.5)

ABC169 C – Multiplication 3（浮動小数点演算）

C – Multiplication 3 (atcoder.jp)

from decimal import Decimal
A, B = map(Decimal, input().split())

print(int(A * B))

ABC170 C – Forbidden List（min）

C – Forbidden List (atcoder.jp)

X, N = map(int, input().split())
p = list(map(int, input().split()))

diff = [10 ** 3] * 102
for i in range(102):
    if i not in p:
        diff[i] = abs(X - i)

mini = min(diff)

for i in range(102):
    if diff[i] == mini:
        print(i)
        break

ABC171 C – One Quadrillion and One Dal（n進数）

C – One Quadrillion and One Dalmatians (atcoder.jp)

２６進数に変換する問題と解釈できる.
各桁についてa : 1, b: 2, … z:26という対応関係を考えればよい.
しかし、それでは 0 を表現することができない.

本問題１つ目のポイント。通常の n 進数は、各桁の値をリスト rem に格納して表現するには、以下のようにすればよい。

def dec_to_n(target, n):
    
    #remainder
    rem = []
    
    while target != 0:
        rem.append(target % n) 
        target = target // n
        
    rem.reverse()
    return rem

このような通常の26進数への変換の場合、それを更にアルファベットにすると
1 -> rem = [0] -> alf[0] = a
26 -> rem = [1, 0] -> alf[1], alf[0] = b, a
27 -> rem = [1, 1] -> alf[1], alf[1] = b, b
となってしまう。

そこで、

下一桁目
1 -> a = alf[0]
2 -> b = alf[1]
…
25 -> y = alf[24]
26 -> z = alf[25]
下二桁目
27 -> 27%26 -> 1 -> a = alf[0]
28 -> 28%26 -> 2 -> b = alf[1]
…

となるような処理を挟む必要がある。そこで, n進数への変換を行う関数dec_to_n()内において, 変換対象の数を割る直前に -1 すればよい。これが本問題の２つ目のポイント。

N = int(input())
import string
alf = list(string.ascii_lowercase) # a to z

def dec_to_n(target, n):
    
    #remainder
    rem = []
    
    while target != 0:
        target -= 1
        rem.append(target % n) 
        target = target // n
        
    rem.reverse()
    return rem

alf_idx = dec_to_n(N, 26)

print("".join([alf[i] for i in alf_idx]))

ABC172 C – Tsundoku（二分探索・累積和）

C – Tsundoku (atcoder.jp)

累積和で, 何冊目まで読んだら, 何分かかるかを記録.
A から取る冊数 i についてループを回し, 二分探索で B からとれる最大の冊数を求める.

from itertools import accumulate
import bisect
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = [0] + list(accumulate(A))
B = [0] + list(accumulate(B))

ans = 0
for i in range(N + 1):
    if A[i] <= K:
        b_idx = bisect.bisect(B, K - A[i]) - 1
        ans = max(ans, i + b_idx)
print(ans)

ABC173 C – H and V（ビット全探索・コピー）

C – H and V (atcoder.jp)

各列について, 選ぶか選ばないかの２通りがあるので, ビット全探索.
リスト state の初期化に気を付ける必要がある.
A = […]
B = A
の場合, A, BのIDが等しくなる.
すると, Bを変更すると同じくAも変更されてしまう.
A = [１次元リスト]
B = copy.copy(A)
により, 新たなIDを持ったリストBを生成することができる.
A = [多次元リスト]
B = copy.deepcopy(A)
により, 新たなIDを持った多次元リストBを生成することができる.

import copy 

H, W, K = map(int, input().split())

C = [list(input()) for _ in range(H)]

ans = 0
for sth in range(1 << H):
    for stw in range(1 << W):
        num = 0
        state = copy.deepcopy(C) # copy.copy(C) はNG

        for i in range(H):
            if (sth >> i) & 1:
                state[i] = ["R" for _ in range(W)] # ["R"] * W だと同じidの要素になってしまう

        for j in range(W):
            if (stw >> j) & 1:
                for i in range(H):
                    state[i][j] = "R"
        
        for h in range(H):
            num += state[h].count("#")
            
        if num == K:
            ans += 1
        
print(ans)

ABC174 C – Repsept（modの性質）

C – Repsept (atcoder.jp)

K = int(input())
n = 0
flag = False
for i in range(K):
    
    n = (n * 10 + 7) % K
    
    if n == 0:
        print(i + 1)
        flag = True
        break
if not flag:
    print(-1)

参考：
解説 – AtCoder Beginner Contest 174
合同式(mod)の意味とよく使う６つの性質 | 高校数学の美しい物語 (manabitimes.jp)

ABC175 C – Walking Takahashi（場合分け）

C – Walking Takahashi (atcoder.jp)

|X| // D 回目までの移動は, 単純に原点に向かっていけばよい.
停留点としてありうる点の内, 原点から最も近い２つの点は, |X| // D 回または |X| // D + 1回移動した場所にある（それらを点G, G’としておく）.
移動回数Kが, それら２つの移動回数以下であれば, 原点に向かう一方向にK回移動すればよい.
Kが, |X| // D + 1回より多いとき, +D, -Dを交互に行う移動ののち, 点G, G’ のどちらに行きつくかを場合分けによって求める.

X, K, D = map(int, input().split())

times = abs(X) // D
if K <= times + 1:
    print(abs(abs(X) - D * K))
else:
    if (K - times) % 2 == 0:
        print(abs(X) - D * times)
    else:
        print(abs(abs(X) - D * (times + 1)))

ABC176 C – Step（単調増加列）

C – Step (atcoder.jp)

前の人より小さいときに台を追加するが, その場合, 自身の身長も高くなることに注意する.

N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(1, N):
    if A[i - 1] > A[i]:
        step = A[i - 1] - A[i]
        ans += step
        A[i] += step
print(ans)

ABC177 C – Sum of product of pairs（累積和）

C – Sum of product of pairs (atcoder.jp)

リスト$A_1, \ … , \ A_N$が与えられたとき,

$$\sum_{i = 1}^{N – 1}\sum_{j = i + 1}^{N}A_iA_j$$

を求めるという問題.

$A_i$と, $1 \le i < j \le N$を満たす$A_j$との掛け算について, 各$A_i$と掛け算される$A_j$を累積和的に求めておけば良い.
片方のリストの累積和を求めておき、もう片方のリストを線形探索するという問題.
ABC172 C – Tsundokuと似ている.

N = int(input())
A = list(map(int, input().split()))

acc_ = [sum(A[1:N])]
for j in range(1, N - 1):
    acc_.append(acc_[-1] - A[j])
    
ans = 0
for i in range(N - 1):
    ans += A[i] * acc_[i]
print(ans % (10**9 + 7))

ABC178 C – Ubiquity（ベン図）

C – Ubiquity (atcoder.jp)

先頭が0でもよい, 長さ N の10進数の内, 0, 9を含むものの数を数えるという問題.
０が含まれる数 + ９が含まれる数 – 0 or 9が１つ以上含まれる数

N = int(input())
print((2 * (10 ** N - 9 ** N) - (10 ** N - 8 ** N)) % (10 ** 9 + 7))

ABC179 C – A x B + C（１を引く）

C – A x B + C (atcoder.jp)

$A$を固定して, $A \times B \le N – 1$を満たす$B$の個数を求めればよい.

import math
N = int(input())

ans = 0
for i in range(1, N):
    ans += (N - 1) // i
print(ans)

ABC180 C – Cream puff（約数の全列挙）

C – Cream puff (atcoder.jp)

$\sqrt{N}$ 以下の数 $i$ で $N$ を割れるか試していけばよい.
$i$ で割った結果も $i$になることがあるので, ダブルカウントに注意.

import math
N = int(input())

yakusu = []
for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        yakusu.append(i)
        if i ** 2 != N:
            yakusu.append(N // i)

yakusu.sort()

for i in yakusu:
    print(i)

ABC181 C – Collinearity（組み合わせ・ベクトルの外積）

itertools.combinations()関数を用いることで, 100個の中から3個を選ぶ組み合わせを全列挙することができる.
選んだ3点をA, B, Cとすると, 外積$ \vec{AB} \times \vec{AC} = 0$が成り立てば, ３点が直線上に並んでいると言える.
numpyを使用して外積を計算したところ, 1ケースのみTLEが起こった. 原因は未だ不明.

import itertools
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

pairs = list(itertools.combinations([i for i in range(N)], 3))

flag = False
for i in pairs:
    a = xy[i[0]]
    b = xy[i[1]]
    c = xy[i[2]]
    ab_x = b[0] - a[0]
    ab_y = b[1] - a[1]
    ac_x = c[0] - a[0]
    ac_y = c[1] - a[1]
    if ab_x * ac_y - ab_y * ac_x == 0:
        flag = True
        break
        
print("Yes" if flag else "No")

ABC182 C – To 3（ビット全探索）

C – To 3 (atcoder.jp)

各桁について, 残すか残さないかの２通りがある.
よって, ２進数で表す状態stについて全探索すればよい.

N = input()

ans = 20
for st in range(1 << len(N)):
    string = ""
    for i in range(len(N)):
        if st >> i & 1:
            string += N[i]
    if len(string) > 0 and int(string) % 3 == 0:
        ans = min(ans, len(N) - len(string))
print(ans if ans != 20 else -1)

ABC183 C – Travel（順列全探索）

C – Travel (atcoder.jp)

「都市１の次の都市」～「都市１に帰る直前に訪れる都市」について, 有りうるすべての訪問順を, 順列として生成する.
都市１から出発し, 都市１に帰る部分は, 上の順列を生成した後に, 別途実装した.
順列 r の先頭と末尾に要素0（都市１のインデックス）を追加すれば, r のループ文の所を, N + 1個の要素に対する１つ処理として書くこともできる.

from itertools import permutations
N, K = map(int, input().split())

T = []

for _ in range(N):
    T.append(list(map(int, input().split())))

# 全順列を生成
roots = permutations([i for i in range(1, N)])

ans = 0
for r in roots:
    time = T[0][r[0]]
    for i in range(N-2):
        now = r[i]
        nxt = r[i + 1]
        time += T[now][nxt]
    time += T[r[N - 2]][0]
    if time == K:
        ans += 1
print(ans)

ABC184 C – Super Ryuma（場合分け・偶奇の利用）

C – Super Ryuma (atcoder.jp)

C問題にしては難しすぎた.
パリティ（偶奇）を上手く利用し, 始点と終点が市松模様の白黒のどちらに属するかを考える.
また, グリッドの縦横の値を足した値, 縦の値-横の値はそれぞれ, 座標軸をグリッドに対して45度回転させたときの座標に対応する.
0, 1, 2, 3回の移動が必要なパターンで, それぞれ場合分けをする.

r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
p1 = r1 + c1
p2 = r2 + c2
m1 = r1 - c1
m2 = r2 - c2

if r1 == r2 and c1 == c2:
    print(0)
elif p1 == p2 or m1 == m2 or abs(r1 - r2) + abs(c1 - c2) <= 3:
    print(1)
elif p1 % 2 == p2 % 2 or abs(r1 - r2) + abs(c1 - c2) <= 6 or abs(p1 - p2) <= 3 or abs(m1 - m2) <= 3: 
    print(2)
else:
    print(3)

ABC185 C – Duodecim Ferra（組み合わせの総数）

C – Duodecim Ferra (atcoder.jp)

組み合わせの総数を求める際、combination関数はmathモジュールにないので、自作する必要がある。

import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
L = int(input())
print(comb(L - 1, 11))

ABC186 C – Unlucky 7（N進数）

C – Unlucky 7 (atcoder.jp)

ある数字が含まれるかどうかは, 数字を文字列として扱えばよい.
oct()に数値を代入すると, 8進数の文字列として出力してくれる.

N = int(input())

ans = 0
for i in range(1, N+1):
    if "7" not in str(i) and "7" not in oct(i):
        ans += 1
        
print(ans)

ABC187 C – 1-SAT（集合・ソート）

C – 1-SAT (atcoder.jp)

同じ文字列が複数あっても仕方ないので, 集合にまとめる.
ソートを用いて, !ありorなしの文字同士が隣に並ぶようにする.
ただし, !が入ったときに自然なソートになるように, 文字列を逆から読む必要がある.
あとは, 文字列を１つずつ, 隣のものと比較していけばよい.

N = int(input())
st = set()
for _ in range(N):
    # 文字列を逆から読む
    st.add(input()[::-1])
st = sorted(st)

flag = False
for i in range(len(st) - 1):
    if st[i + 1].replace("!", "") == st[i]:
        print(st[i][::-1])
        flag = True
        break
        
if not flag:
    print("satisfiable")

ABC188 C – ABC Tournament（min・max）

C – ABC Tournament (atcoder.jp)

実際のトーナメント表をイメージすれば, ２ブロックに分けて, それぞれで勝ち上がった者同士で決勝が行われるのは容易に分かる.
二分探索木を使わなくてもいい点, D問題とは違うんだなと思った. D問題だと, グラフやら探索木やらで実装が重くなるんだろうな…

N = int(input())
A = list(map(int, input().split()))
mid = 2 ** (N - 1)
result = min(max(A[:mid]), max(A[mid:]))
for i, val in enumerate(A):
    if val == result:
        print(i + 1)
        break

ABC189 C – Mandarin Orange（区間全探索）

C – Mandarin Orange (atcoder.jp)

区間の左端を固定し, 右端を全探索.
それが完了したら, 左端をずらし, 右端の全探索.
Python3ではTELになったが, PyPy3ならACになった.

N = int(input())
A = list(map(int, input().split()))

ans = 0
for l in range(N):
    x = A[l]
    for r in range(l, N):
        x = min(x, A[r])
        ans = max(ans, x * (r - l + 1))
        
print(ans)

ABC190 C – Bowls and Dishes（ビット全探索）

C – Bowls and Dishes (atcoder.jp)

K 人のそれぞれについて, 2つの選択肢がある.
O(2^K * M) は全探索可能なのでビット全探索.

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

req = [list(map(int, input().split())) for _ in range(M)]

K = int(input())
ball = [list(map(int, input().split())) for _ in range(K)]

ans = 0
for st in range(1 << K):
    # state ごとに, ボールが置かれている皿を格納
    on = []    
    tmp = 0
    for i in range(K):
        if st >> i & 1:
            on.append(ball[i][0])
        else:
            on.append(ball[i][1])
    for j in range(M):
        # reqの各要素について, 2つとも条件を満たしている場合
        if req[j][0] in on and req[j][1] in on:
            tmp += 1
    ans = max(ans, tmp)
    
print(ans)

ABC191 C – Digital G（ビット全探索）

C – Digital Graffiti (atcoder.jp)

マス間のそれぞれの点について, 左上, 右上, 右下, 左下の四マスの内, いくつ黒になっているかを数えれば, その点が角になっているかわかる.
上下左右の探索は, ２重ループでも良いが, ビット全探索を使うとシンプルに実装できる.
ビット全探索は多くの問題で便利な手法なので, 敢えて使ってみた.

H, W = map(int, input().split())

s = [input() for _ in range(H)]

edge = 0
for i in range(H - 1):
    for j in range(W - 1):
        # ビット探索
        # # の数
        cnt = 0
        for st in range(1 << 2):
            if s[i + (st & 1)][j + (st >> 1 & 1)] == "#":
                cnt += 1
        if cnt == 1 or cnt == 3:
            edge += 1
            
print(edge)

ABC192 C – Kaprekar Number（文字列・ソート）

C – Kaprekar Number (atcoder.jp)

文字列化してソートすれば簡単に関数を実装できる.

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

def f(x):
    x = list(str(x))
    f1 = int("".join(sorted(x, reverse = True)))
    f2 = int("".join(sorted(x)))
    return f1 - f2

ans = N
for i in range(K):
    ans = f(ans)
print(ans)

ABC193 C – Unexpressed（整数）

C – Unexpressed (atcoder.jp)

Nの最大値を見て, 全探索は無理だと分かる.
べき乗で表せる数を数えて, Nから引けばよい.
2乗, 3乗, …の形になっている数を順番に探索していけばいいが, 重複が生じることがあるため, 集合set()で管理する必要がある.

# 193
import math
N = int(input())

# 最大指数
M = int(math.log(N, 2))

# Nを超えないべき乗の整数
nums = set()
if N >= 4:
    for m in range(2, M + 1):
        for i in range(2, N):
            if i ** m <= N:
                nums.add(i ** m)
            else:
                break
    print(N - len(nums))
else:
    print(N)

ABC194 C – Squared Error（累積和）

C – Squared Error (atcoder.jp)

式を展開して, 共通項を見出す必要があった.
同じ項の出現回数や, 累積和を駆使すればO(N)で計算できる.

N = int(input())

A = list(map(int, input().split()))
         
aa = (N - 1) * sum([a ** 2 for a in A])
ab = 0
tot = sum(A)
for i in range(N - 1):
    # 自分自身は引く
    tot -= A[i]
    # 自分自身と, その他との積
    ab += -2 * A[i] * tot
    
print(aa + ab)

ABC195 C – Comma（N進数）

C – Comma (atcoder.jp)

1000進数で考える.
$1000^1, 1000^2, …$に満たない数をNから引くことで, 下の桁から1つ目, 2つ目…のコンマの数を数えることができる.

import math
N = int(input())

M = int(math.log(N, 1000))

ans = 0
for i in range(1, M + 1):
    ans += N - (1000 ** i - 1)
    
print(ans)

ABC196 C – Doubled（整数）

C – Doubled (atcoder.jp)

N = int(input())
M = 10 ** 6
ans = 0
for i in range(1, M + 1):
    if int(str(i) * 2) <= N:
        ans += 1
    else:
        break
print(ans)

ABC197 C – ORXOR（ビット全探索）

C – ORXOR (atcoder.jp)

N – 1か所に区切りを入れるか入れないかという選択肢がある．
区切りの有無の組み合わせは，ビット全探索で網羅できるし，計算量も間にあう．
下からN桁目を1にして，最後の（N個目の要素の入る区間の右端となる）区切りとしておく．

N = int(input())
A = list(map(int, input().split()))

ans = float('INF')

for st in range(1 << (N - 1)):
    st += 1 << (N-1) # 最後の区切り
    ored = 0
    xored = 0
    for j in range(N):
        ored |= A[j]
        if st >> j & 1:
            xored ^= ored # xor演算 初期値0は影響しない
            ored = 0 # 区切ったら初期化
            
    ans = min(ans, xored)
    
print(ans)

ABC198 C – Compass Walking（場合分け）

C – Compass Walking (atcoder.jp)

import math
R, X, Y = map(int, input().split())
d = math.sqrt(X**2 + Y **2) # 原点からの距離
if d == R:
    print(1)
elif d <= 2 * R:
    print(2)
else:
    print(math.ceil(d / R))

ABC199 C – IPFL（場合分け）

C – IPFL (atcoder.jp)

N = int(input())
S = list(input())
Q = int(input())

S_f = S[:N]
S_b = S[N:]

for _ in range(Q):
    t, a, b = map(int, input().split())
    
    a -= 1
    b -= 1 
    
    if t == 1:
        if a < N and b < N:
            sa = S_f[a]
            sb = S_f[b]
            S_f[a] = sb
            S_f[b] = sa                
        elif a < N and b >= N:
            b -= N
            sa = S_f[a]
            sb = S_b[b]
            S_f[a] = sb
            S_b[b] = sa    
        elif a >= N and b >= N:
            a -= N
            b -= N
            sa = S_b[a]
            sb = S_b[b]
            S_b[a] = sb
            S_b[b] = sa   
            
    else:
        s_f = S_f
        s_b = S_b
        S_f = s_b
        S_b = s_f 

print("".join(S_f + S_b))