Python初心者のためのABC204

A問題
B問題
C問題
D問題

A問題

3人の出す手を $x,y,z\in\{0,1,2\}$ （ $0,1,2$ がそれぞれグー，チョキ，パーに対応）とします．この問題は， $x,y$ が与えられたときにあいこになるような $z$ を求める問題です．公式解説では，

$x,y$ は高々9通りしかないので場合分け
$x=y$ のとき $z=x$ ， $x\ne y$ のとき $z=3-x-y$ を出力

という2つの解法を紹介しています．別解として，3人の手があいこになるときは $x+y+z$ が3の倍数になることを利用します．この性質に気づくことができれば，実装量は上記の2つの解法よりも少なく抑えられます．

x,y = map(int,input().split())
print(-(x+y)%3)

B問題

atcoder.jp

そのまま実装するだけです．A問題より簡単かもしれません．それぞれの木から収穫する木の実の個数は，生っている木の実が10個以下かどうかif文を使って場合分けしても良いですが，以下のような表し方も可能です．

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
  ans += max(0, a - 10)
print(ans)

C問題

atcoder.jp

都市を頂点，道を有向辺とするグラフとみなすことができます．各頂点から探索（幅優先探索または深さ優先探索）を行うことで，その頂点をスタート地点とした場合のゴール地点の候補をすべて調べることができます．頂点数を $N$ ，辺数を $M$ とした場合の全頂点からの探索には $O(N(N+M))$ の計算量がかかり， $M$ は一般には最大で $O(N^2)$ 程度になるため，全体では $O(N^3)$ の計算量を要しTLEしそうな気がします．しかし，今回は $M\le 2000$ という追加制約によって時間制限に間に合うように設定されています．

問題文はよく読みましょう．（スミマセンでした）

from collections import deque

N,M = map(int,input().split())
node = [[] for _ in range(N+1)]
for _ in range(M):
  a,b = map(int,input().split())
  node[a].append(b)

# 幅優先探索
def bfs(v):
  q = deque()
  done = [0]*(N+1)  # すでに探索済かどうか
  q.append(v)
  done[v] = 1
  cnt = 1  # 到達可能な頂点数
  while q:
    x = q.popleft()
    for y in node[x]:
      if not done[y]:
        q.append(y)
        done[y] = 1
        cnt += 1
  return cnt

ans = 0
for v in range(1,N+1):
  ans += bfs(v)
print(ans)

D問題

atcoder.jp

誤った解法（貪欲法）

料理を時間がかかる順にオーブンを割り当てることを考えます．ある料理を割り当てたいとき，今までに割り当てたられた料理にかかる時間の合計が小さい方のオーブンに割り当てれば良さそうな気がします．

N = int(input())
T = list(map(int,input().split()))
T.sort(reverse=True)

oven1 = 0
oven2 = 0
for t in T:
  if oven1 <= oven2:
    oven1 += t
  else:
    oven2 += t

ans = max(oven1, oven2)
print(ans)

この解法はサンプルケースに対してはACですが，実際に提出するとWAになってしまいます．例えば，以下のようなケースが反例になります．

5
3 3 2 2 2

正解は6分（1つ目のオーブンで3分かかる料理を2つ，2つ目のオーブンで2分かかる料理を3つ調理するのが最適）ですが，上記のプログラムでは7分（1つ目のオーブンで3分，2分，2分の料理，2つ目のオーブンで3分，2分の料理を調理することになる）を出力してしまいます．このように，サンプルケースに対しては正解を出力しても解法が根本的に間違っている場合があるので注意しましょう．

正しい解法

$S=\sum_i T_i$ とします．1つ目のオーブンに割り当てる料理の調理時間 $S_1$ が決まると，2つ目のオーブンでの調理時間は自動的に $S-S_1$ と定まります．よって，考えられるすべての $S_1$ に対して $\mathrm{max}(S_1, S-S_1)$ の最小値が答えとなります．すべての $S_1$ を調べるには典型056 のテクニックが使え，計算量は $O(NS)$ であるため時間制限にも間に合います．

N = int(input())
T = list(map(int,input().split()))
S = sum(T)

# 合計調理時間がxになるような料理の割り当て方があるか
dp = [0]*(S+1)
dp[0] = 1

for t in T:
  nxt = [0]*(S+1)
  for x in range(S+1):
    if dp[x]:
      nxt[x] = 1
      if x+t<=S:
        nxt[x+t] = 1
  dp = nxt
        
ans = 3141592
for x in range(S+1):
  if dp[x]:
    ans = min(ans, max(x, S-x))
print(ans)

きゃねろぐ

とある「おひさま」の徒然日記

Python初心者のためのABC204

A問題

B問題

C問題

D問題