AtCoder Beginner Contest 119 A,C,D問題メモ

A - Still TBD

問題

  • 'YYYY/MM/DD' 形式の文字列 $S$ が与えられる
  • 2019年4月30日以前なら'Heisei'、以後なら'TBD' と出力せよ

解法

多くの言語では、桁数がゼロ埋めで揃えられている数値文字列の比較は、文字列のまま比較が出来る。

ちなみにTBD = To Be Determined(未確定) らしい。果たして年号はDeterminedなのかPublishedなのか。

s = input()
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')

C - Synthetic Kadomatsu

問題

  • $N$ 本の竹があり、長さは $l_1,l_2,...,l_N$
  • これらを使って、長さが $A,B,C$ である3本の竹を作りたい
  • 以下の3通りの操作ができる
    • コスト1MP: 1本の竹の長さを1増やす
    • コスト1MP: 1本の竹の長さを1減らす(長さ1の竹を選ぶことは出来ない)
    • コスト10MP: 2本の竹を接いで1本にする。長さは2本の合計となる
  • 最小コストを求めよ
  • $3 \le N \le 8$

解法

$N$ が小さいので、全探索。どうやって全探索するかにちょっと手間取る。

1本の竹につき、考えられる使い方は4通り。

  • 長さ $A$ の竹を作るのに使う
  • 長さ $B$ の竹を作るのに使う
  • 長さ $C$ の竹を作るのに使う
  • 使わない

$N$ 本のそれぞれで4通りなので、$4^N \le 4^8=65536$。多くともこの数のパターンを調べればよい。

あるパターンのコストは、$A~C$ について使う竹を全て接ぐためのコストと、接いだ後に目標との差分だけ1ずつ増減させるコストの合計となる。

状態の列挙は、ビットで表現する。

N=5
0100101110
↓ 2桁ごと区切る
01 00 10 11 10
         ~~ ~~ ←1本目の竹の使い方
         ↑2本目の竹の使い方
00: 使わない
01: Aの竹を作るのに使う
10: Bの竹を作るのに使う
11: Cの竹を作るのに使う

これで、0から $4^N-1$ までをイテレートすると、全ての状態を列挙できる。

それぞれのコストを計算し、最小値が答え。$A,B,C$ がいくら短くとも、最低1本の竹は使っていないといけない点に注意。

n, a, b, c = list(map(int, input().split()))
lll = [int(input()) for _ in range(n)]

ans = 10 ** 9
for i in range(4 ** n):
    ta, tb, tc = 0, 0, 0
    tmp = 0
    for j in range(n):
        k = (i >> (2 * j)) & 3
        if k == 1:
            if ta > 0:
                tmp += 10
            ta += lll[j]
        elif k == 2:
            if tb > 0:
                tmp += 10
            tb += lll[j]
        elif k == 3:
            if tc > 0:
                tmp += 10
            tc += lll[j]
    if ta == 0 or tb == 0 or tc == 0:
        continue
    tmp += abs(a - ta) + abs(b - tb) + abs(c - tc)
    ans = min(ans, tmp)
print(ans)

D - Lazy Faith

問題

  • 東西一直線の道路に、西端から $1,2,...$ と座標が振られている
  • 道路沿いに $A$ 社の神社と $B$ 軒の寺が建っている
  • $i$ 社目の神社は座標 $s_i$ の地点にある
  • $i$ 軒目の寺は座標 $t_i$ の地点にある
  • クエリが $Q$ 個与えられるので、全てに答えよ
    • $x_i$ の地点から出発して道路上を自由に移動する
    • 少なくとも神社と寺を1軒ずつ訪れたい
    • 必要な最小移動距離を求めよ
  • $1 \le A,B \le 10^5$
  • $1 \le Q \le 10^5$
  • $1 \le s_i,t_i,x_i \le 10^{10}$
  • $s_i,t_j,x_k$ は全て異なる

解法

事前処理と二分探索

まず、取るべき行動は、以下のいずれかになる。各 $x_i$ について、以下の最小値を求めればよい。

  • $x_i$ から西に最も近い神社に行き、そこから最も近いに行く
  • $x_i$ からに最も近い神社に行き、そこから最も近いに行く
  • $x_i$ から西に最も近いに行き、そこから最も近い神社に行く
  • $x_i$ からに最も近いに行き、そこから最も近い神社に行く

たとえば1番目の行動で神社に着く前に既に寺を通過していた場合は、そこからさらに寺に行く必要は無くて無駄な移動になるが、その場合の最適な行動は3番目でフォローされている。

まずクエリを効率的に処理するため、以下を事前計算する。

  • 各神社について、最も近い寺までの距離
  • 各寺について、最も近い神社までの距離

二分探索を用いる方法がある。

座標       20  24    30    35
index       1         2     3
神社       ⛩        ⛩    ⛩
               ↑
i番目の寺      卍

Pythonでは bisect で二分探索が行える。 神社の列の中に座標24の寺を挿入する際、挿入すべきindexが返される。つまり、上の場合は'2'となる。 よって、$i$ 番目の寺から最も近い神社は1番目か2番目の神社なので、2社との距離を計算して小さい方が「$i$ 番目の寺について、最も近い神社までの距離」となる。

事前計算が済んだらクエリを順に処理する。これも同様にして、$x_i$ にとって西・東で最も近い神社・寺との距離を二分探索で求められる。

import bisect
import sys

a, b, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
sss = list(map(int, lines[:a]))
ttt = list(map(int, lines[a:a + b]))
xxx = list(map(int, lines[a + b:]))

nearest_temples = [0] * a
nearest_shrines = [0] * b
for i, s in enumerate(sss):
    ti = bisect.bisect(ttt, s)
    nt = 10 ** 11
    if ti > 0:
        nt = min(nt, abs(s - ttt[ti - 1]))
    if ti < b:
        nt = min(nt, abs(s - ttt[ti]))
    nearest_temples[i] = nt
for i, t in enumerate(ttt):
    si = bisect.bisect(sss, t)
    ns = 10 ** 11
    if si > 0:
        ns = min(ns, abs(t - sss[si - 1]))
    if si < a:
        ns = min(ns, abs(t - sss[si]))
    nearest_shrines[i] = ns

buf = []
for x in xxx:
    si = bisect.bisect(sss, x)
    ti = bisect.bisect(ttt, x)
    ans = 10 ** 11
    if si > 0:
        ans = min(ans, x - sss[si - 1] + nearest_temples[si - 1])
    if si < a:
        ans = min(ans, sss[si] - x + nearest_temples[si])
    if ti > 0:
        ans = min(ans, x - ttt[ti - 1] + nearest_shrines[ti - 1])
    if ti < b:
        ans = min(ans, ttt[ti] - x + nearest_shrines[ti])
    buf.append(ans)
print('\n'.join(map(str, buf)))

二分探索時の端の処理分けが煩雑なのは、番兵置いたらもっとスッキリ書ける。ただ、置いて問題ないかなかなかパッと判断できないね。

import bisect
import sys

SENTINEL = 10 ** 12

a, b, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
sss = [-SENTINEL] + list(map(int, lines[:a])) + [SENTINEL]
ttt = [-SENTINEL] + list(map(int, lines[a:a + b])) + [SENTINEL]
xxx = list(map(int, lines[a + b:]))

nearest_temples = [SENTINEL] + [0] * a + [SENTINEL]
nearest_shrines = [SENTINEL] + [0] * b + [SENTINEL]
for i, s in enumerate(sss[1:-1], start=1):
    ti = bisect.bisect(ttt, s)
    nearest_temples[i] = min(ttt[ti] - s, s - ttt[ti - 1])
for i, t in enumerate(ttt[1:-1], start=1):
    si = bisect.bisect(sss, t)
    nearest_shrines[i] = min(sss[si] - t, t - sss[si - 1])

buf = []
for x in xxx:
    si = bisect.bisect(sss, x)
    ti = bisect.bisect(ttt, x)
    ans = min(x - sss[si - 1] + nearest_temples[si - 1],
              sss[si] - x + nearest_temples[si],
              x - ttt[ti - 1] + nearest_shrines[ti - 1],
              ttt[ti] - x + nearest_shrines[ti])
    buf.append(ans)
print('\n'.join(map(str, buf)))

programming_algorithm/contest_history/atcoder/2019/0224_abc119.txt · 最終更新: 2019/02/26 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0