[[ABC 089]]

ABC 089

A - Grouping 2

問題

  • $N$ 人の生徒をグループに分ける
  • 各グループは3人以上
  • 最大何グループ作れるか

解法

3で割ればいい。(余り切り捨て)

a = int(input())
print(a // 3)

B - Hina Arare

問題

  • $N$ 粒のひなあられが1つの袋に入っている
  • ひなあられは、「桃白緑」の3色か「桃白緑黄」の4色のどちらか
  • 各粒の色が教えられるので、3色か4色か判定せよ

解法

Pythonなら、set()で配列を重複なしの集合に変換できる。この重複なしの集合の長さが3か4か見ればよい。

n = input()
s = set(input().split())
print('Three' if len(s) == 3 else 'Four')

もしくは、色が決まっているので、'Y'が入っているかどうかで見分けられる。

n = input()
s = input().split()
print('Four' if 'Y' in s else 'Three')

C - March

問題

  • $N$ 人の人の名前が(英大文字で)列挙される
  • 以下の条件を満たすように、3人を選ぶ
    • 3人とも、頭文字が'M','A','R','C','H'のどれかで始まっている
    • 同じ頭文字で始まっている人はいない
  • 選び方は何通りあるか

解法

選ぶ3人の頭文字がどうなっているかというと、「'M','A','R'」や「'A','C','H'」のように'MARCH'の中から選べる異なる3文字となっている。

たとえば頭文字「'M','A','R'」に絞って考えると、それぞれの文字で始まる人が「5人、9人、4人」だった場合、組み合わせの数は $5 \times 9 \times 4=180$ となる。これを全ての異なる3文字の組み合わせで調べれて足しあわせればよい。ただし各頭文字で始まる人がいなかった場合にKeyErrorに注意。

Pythonでは、ある頭文字で始まる人が何人いるかは、collections.Counterを使って数え上げられる。 また、5個の中から異なる3個を取る組み合わせの列挙は、itertools.combinationsを使える。

from collections import Counter
from itertools import combinations

n = int(input())
l = [input()[0] for _ in range(n)]
lc = Counter(l)

con = []
for c in 'MARCH':
    if c in lc:
        con.append(lc[c])

ans = 0
for a, b, c in combinations(con, 3):
    ans += a * b * c

print(ans)

D - Practical Skill Test

問題

理解にちょっと手間取る。

  • $H\times W$ のマス目に、1から$H\times W$ までの整数が1つずつ書かれている。(順番通りとは限らない)
  • ある数字 $D$ が決まっている
  • ある数字 $L_i,R_i \ (1 \le L_i,R_i \le H \times W)$ が $Q$ 組与えられる。それぞれについて、以下の結果を求める
    • $L_i$ の書かれたマスから、$L_i+D, L_i+2D, L_i+3D,\ldots$ の書かれたマスに順に移動する
    • $R_i$ の書かれたマスに着いたら終わり(必ず着けるような数が与えられる)
    • $(i_1,j_1)$ から $(i_2,j_2)$ に移動するコストは、マンハッタン距離($|i_1-i_2|+|j_1-j_2|$)
    • 移動にかかる総コストを求める

  • 上図の例
    • $H,W=4,4$
    • $D=4$
    • $L,R=2,14$
  • 上図の総コスト
    • 2→6: 移動コスト4
    • 6→10: 移動コスト3
    • 10→14: 移動コスト6
    • 計13

解法

$Q$ の制約が $10^5$ と割と大きいので、1個ずつのクエリを高速に求められるように事前計算する、というのがこの問題の肝。

こういうのは累積和の差分で計算させるとよい。

  • 各数字($1 \le L \le H \times W$)について、移動できるまで移動した時の総コストを求めておく
    • 「移動できるまで」とは、今いるマスの数字が $L_k$ で、$L_k+D \gt H \times W$ となるまで。(言い換えると、次に $L_k+D$ の書かれたマスに移動しようとしても、その数字が書かれたマスが存在しなくなるまで)
    • この結果を $dist$ とする
  • すると、$dist[L_i]-dist[R_i]$ が、求めるべき答えとなる
HxW=5x5
D=4, L=2, R=14
                 2     6    10    14    18    22
        dist[L] ○→→○→→○→→○→→○→→○
        dist[R]                   ○→→○→→○
dist[L]-dist[R] ○→→○→→○→→○

※AtCoderの解説pdfや解説資料では、逆に始点からの累積距離を事前計算していたので、混同に注意。

import sys

h, w, d = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(h)]

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

d_map = [0] * (h * w)
for l in range(h * w - d - 1, -1, -1):
    i, j = c_map[l]
    i2, j2 = c_map[l + d]
    d_map[l] = d_map[l + d] + abs(i - i2) + abs(j - j2)

buf = []
q = int(input())
for line in sys.stdin.readlines():
    l, r = map(int, line.split())
    buf.append(d_map[l - 1] - d_map[r - 1])

print('\n'.join(map(str, buf)))

programming_algorithm/contest_history/atcoder/2018/0304_abc089.txt · 最終更新: 2018/07/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0