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

AtCoder Beginner Contest 119

AtCoder Beginner Contest 119 解説放送 - YouTube

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)))

            

        
      