AtCoder Beginners Contest 310 (ABC310) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Order Something Else
問題ページ
考察
支払う方法は次の2つです。
- $P$ 円だけ払う
- $Q$ 円払って、さらにリスト $D$ の中で最も安いものを買う
これをそのまま実装します。
min(D) ← これでリスト内の最小値を持ってきてくれて便利です！
コード
N, P, Q = map(int, input().split())
D = list(map(int, input().split()))
ans = min(P, Q + min(D))
print(ans)
B - Strictly Superior
問題ページ
考察
問題文はごちゃごちゃ書いていますが、B問題までならだいたい書いてあることを愚直に実装できればOKなことが多いです。
具体的なことは、下のコードを参考にしてください。
下のコードの入力受け取りについて
入力の受け取りでは、次のコードを書いています。
p, c, *f = map(int, input().split())
このコードは、次のように動きます。
T = [10, 30, 70, 4, -15]
p, c, *f = T
print(p) # 10
print(c) # 30
print(f) # [70, 4, -15]
これを知っていると、たまにつかえてラクできます！
コード
N, M = map(int, input().split())
P = [] # P[i]: 商品iの値段
F = [] # F[i]: 商品iの機能のセット
for _ in range(N):
p, c, *f = map(int, input().split())
P.append(p)
se = set()
for el in f:
se.add(el)
F.append(se)
for i in range(N):
for j in range(N):
if i == j:
continue
# 1つ目の条件
if P[i] < P[j]:
continue
# 2つ目の条件
is_ok = True
for el in F[i]:
if el not in F[j]:
is_ok = False
if not is_ok:
continue
# 3つ目の条件
if P[i] > P[j]:
print("Yes")
exit()
for el in F[j]:
if el not in F[i]:
print("Yes")
exit()
print("No")
C - Reversible
問題ページ
考察
反転させたものも同じものとみなすのが、難しいポイントです。
まずセットを用意します。文字列を順番に見ていって、「その文字列 $S$と反転させた文字列 $T$ がどちらもセットに入っていなければ、セットに今見ている文字列を入れる。」の操作を繰り返すことでACできます。
また、文字列の反転は次のコードで書けます。
T = S[::-1]
コード
N = int(input())
se = set()
for _ in range(N):
S = input()
T = S[::-1]
if S in se or T in se:
continue
else:
se.add(S)
print(len(se))
D - Peaceful Teams
問題ページ
考察
再帰関数で解きます。
再帰関数をつかうときは、以下のコードをそのまま先頭に貼り付けます。
import sys
import pypyjit
sys.setrecursionlimit(10**7)
pypyjit.set_param('max_unroll_recursion=-1')
setrecursionlimitは再帰の回数を引き上げるメソッドで、なにもしないとPythonは $1000$ 回が再帰の上限なので、それを $10^7$ 回にしています。
もう片方のはpypyで再帰がはやくなるおまじないらしくて、まだ私もよくわかっていないです。(すみません...)
各チームをリストだと思うことにします。つまり、
$[[チーム1], [チーム2], ..., [チームT]]$
みたいに管理していきます。
ただし、 $[[1, 2], [3, 4]]$ と $[[3,4],[2,1]]$ のように、順番が違うだけのものは一緒のものとして扱います。
具体的には、次のように解きます。
- 関数 $f(v, lis)$ を用意します。これは、今から選手 $v$ をチームに入れようとしていて、チームの状況が $lis$ であることを表しています。
- チーム1から順番に選手 $v$ が入れるかどうかを見ていきます。もし選手 $v$ がそのチームに入れるなら、そのチームに選手 $v$ を加入させた新たなチームの状況 $nlis$ を用意して、 $f(v+1, nlis)$ を解くことにします。
- ただし、今から入ろうとしているチームの人数が0人だったとき、加入させたうえで、それ以降のチームに関しては入れるかどうかを見ずに打ち切ります。順番が違うだけのものは一緒のものとして扱われるからです。
- こうして $N$ 人をみんなチームに入れたら、チーム $T$ に誰か所属しているのを確認して、変数 $ans$ を $1$ だけ増やします。チーム $T$ に誰も所属していなかったら、それはチーム数が $T-1$ になってしまっているのでカウントしません。
コード
import sys
import pypyjit
sys.setrecursionlimit(10**7)
pypyjit.set_param('max_unroll_recursion=-1')
N, T, M = map(int, input().split())
C = set()
for _ in range(M):
a, b = map(int, input().split())
C.add((a - 1, b - 1))
C.add((b - 1, a - 1))
ans = 0
def f(v, lis):
if v == N:
# チーム数がT未満なら、答えにはカウントしない。
if len(lis[-1]) == 0:
return
global ans
ans += 1
return
for i in range(T):
nlis = [a[:] for a in lis] # lisのコピー
if len(nlis[i]) == 0:
nlis[i].append(v)
f(v + 1, nlis)
break
is_ok = True # 相性の悪い選手がチームにいればFalse
for v2 in nlis[i]:
if (v, v2) in C:
is_ok = False
if is_ok:
nlis[i].append(v)
f(v + 1, nlis)
f(0, [[] for _ in range(T)])
print(ans)
類題
E - NAND repeatedly
問題ページ
考察
動的計画法DPで解きます。
例えば $N=3$ だったとして、すべての $f(l,r)$ の値が分かっているとします。
このときの数列の末尾に $0$ か $1$ を追加したときに、答えがどう変わるかを考えます。
答えには $f(1,4)+f(2,4)+f(3,4)+f(4,4)$ を足すことになります。
$f(1,4)=f(1,3) \bar\wedge A_4$
$f(2,4)=f(2,3) \bar\wedge A_4$
$f(3,4)=f(3,3) \bar\wedge A_4$
( $f(4,4)=A_4$ )
です。こうしていちいち計算していると計算量が $O(N^2)$ でTLEしちゃいます。
上の例だと、 $f(1,3)$ ～ $f(3,3)$ の中で $0$ と $1$ の数が分かっていると、$O(N)$ で計算できます。
$dp[i][num]$: $f(1,i)$ ～ $f(i,i)$ の中で値が $num$ の個数
として、$N=1$ のときの問題から順番に $N=2, N=3, ...$ と解いていくことで答えが求められます。
コード
def NAND(x, y):
if x == y == 1:
return 0
return 1
N = int(input())
S = input()
dp = [[0] * 2 for _ in range(N + 1)]
for i, ss in enumerate(S):
s = int(ss)
dp[i + 1][NAND(s, 0)] += dp[i][0]
dp[i + 1][NAND(s, 1)] += dp[i][1]
dp[i + 1][s] += 1
ans = 0
for i in range(N + 1):
ans += dp[i][1]
print(ans)