目次
AtCoder Beginner Contest 103
A - Task Scheduling Problem
問題
- 3個のタスクがあり、それぞれに値 $A_1,A_2,A_3$ が決められている
- 最初のタスクはコスト0で完了できる
- 2番目以降の完了には、直前のタスクとの $A_i$ の差の絶対値のコストがかかる
- 全てのタスクを完了させるためのコストの最小値は？
解法
選ぶタスクの $A_i$ を増やしたり減らしたり行ったり来たりすると、往復する分が無駄なコストとしてかかってしまうので、小さい方から徐々に増やす（または大きい方から減らす）のがよい。
間を省略すると、$A_1,A_2,A_3$ の最大値ー最小値が答えとなる。
a, b, c = map(int, input().split()) print(max(a, b, c) - min(a, b, c))
B - String Rotation
問題
- 文字列 $S,T$ がある
- 文字列 $S$ を「回転させる」とは、$S$ の末尾の文字を先頭に持ってくる操作を指す
- ABCDE → EABCD
- 文字列 $S$ を回転させて、$T$ に一致させられるか調べよ
解法
全部試す。
s = input()
t = input()
for _ in range(len(s)):
if s == t:
print('Yes')
break
s = s[-1] + s[:-1]
else:
print('No')
C - Modulo Summation
問題
- 正整数列 $\{a_1,a_2,...,a_N\}$ がある
- 1つの正整数 $m$ に対して、$f(m)=(m \mod{a_1})+(m \mod{a_2})+...+(m\mod{a_N})$ とする
- $X\mod{Y}$ は、$X$を$Y$で割った余り
- 上手く $m$ を選んで $f$ が取れる最大値を求めよ
解法
ある $a_i$ で正整数を割った余りは $0$～$a_i-1$ の間である。つまり最大は $a_i-1$ である。
全ての $a_i$ について最大値 $a_i-1$ を取れるような $m$ が存在すれば、$f$ の最大値は $(a_1-1)+(a_2-1)+...+(a_N-1)$ となる。
じゃあ、そんな $m$ は存在するのか。
最大値 $a_i-1$ を得られるのは、$a_i$ の倍数から1少ない数 $m=ka_i-1$ の時である。
$m'=a_1\times a_2 \times ... \times a_N$ のように全ての $a_i$ をかけてしまえば、$m'$ は $a_1$～$a_N$ 全ての数の倍数である。
よって、$m=m' - 1$ とすることで、全ての $a_i$ に対して、最大値の $a_i-1$ が得られる。
$m$ を実際に計算する必要は無い。
n = int(input())
aaa = list(map(int, input().split()))
ans = 0
for a in aaa:
ans += a - 1
print(ans)
D - Islands War
問題
- 東西1列に並んだ $N$ 個の島がある
- $N-1$ 本の橋によって、隣同士の島が結ばれている
- いくつかの島で戦争が起こり、以下のような要望が $M$ 個寄せられた
- 島 $a$ と $b$ を、その間にあるいずれかの橋を壊して、移動できないようにしてほしい
- 全ての要望を叶えるために、壊す橋の最小数はいくつか？
例
１ ２ ３ ４ ○＝＝＝○＝＝＝○＝＝＝○ > 1と3を移動できないように > 2と4を移動できないように →2と3の間にある橋を壊せば、2つの要望を叶えられる 答えは1本
解法
必要が生じるまで橋は壊さないことにして、西から順に見ていく。
ある要望 $a_i,b_i$ について、$b_i$ まで見た時に、$a_i$ 以降のどの橋も壊されてなければ、$b_i-1$ と $b_i$ の間の橋を壊す必要がある。
ai bi
○＝○＝○＝○＝○＝○＝○＝○
↑ｺｺﾏﾃﾞﾐﾀ
ai bi
○＝○＝○＝○ ○＝○＝○＝○
↑壊す必要がある
他の要望のために既に $a_i$ 以降のいずれかの橋が壊されていれば、何もしなくてよい。
ai bi ○＝○＝○ ○＝○＝○＝○＝○
壊す時、$a_i$～$b_i$ の間ならどの橋でもいいのだが、出来るだけ右の橋を壊した方が、他の要望の区間を多く含めるようになる。
a b
○＝○＝○＝○＝○＝○＝○＝○
~~~~~~~~
~~~~~~~~~~~~~~~~
~~~~~~~~~~~~
↑ ↑
① ②
$b_i$ の小さい方から見ていくので、①を含み、右端がbより右にある区間は、必ず②も含んでいる。
実装
まず各要望について「$a_m$ と要望番号 $m$」「$b_m$ と要望番号 $m$」の計 $2M$ 個の情報をリスト化し、ソートする。
ソート時、同じ島なら $b$ の方が $a$ より前に来るようにする。（$b_1$ と $a_2$ が同じ島である2つの区間は、共有する橋を持たないため）
a1 b1
○＝○＝○＝○＝○＝○＝○＝○
a2 b2
「保留中リスト」と「確定済みリスト」を用意し、上記のソート済みリストを順に見ていく。
$a_i$ が出てきたら、要望番号 $i$ を保留中リストに蓄積する。
$b_i$ が出てきたら、
- 要望番号 $i$ がまだ叶えられてなければ、（確定済みリストに無ければ）
- 橋を1つ壊す
- 保留中リストの要望を全て確定済みリストに移す
- 保留中リストを空にする
- 要望番号 $i$ が既に叶えられていれば
- 何もしない
以上で、壊した橋の数が答えとなる。
n, m = map(int, input().split())
ab_list = []
for i in range(m):
a, b = map(int, input().split())
ab_list.append((a - 1, 2, i))
ab_list.append((b - 1, 1, i))
ab_list.sort()
ans = 0
separated = [False] * m
buf = set()
for island, ab, i in ab_list:
if ab == 1:
if separated[i]:
continue
else:
ans += 1
for j in buf:
separated[j] = True
buf.clear()
else:
buf.add(i)
print(ans)
実装2
もっとよい実装が解説されていた。
$(b,a)$ ペアについてソートして、「最後に壊した最も東の橋 $r$」を記録しながら西から見ていく。
$a$ が $r$ より小さければ、既に要望は叶えられている。
$a$ が $r$ より大きければ要望はまだなので、橋を壊して$r=b$ に更新する。
要望番号を管理しなくても、これで十分カウントできる。
また、$b$ が同じ要望が複数ある場合、必要なのは $a$ が最も東にある1つだけなので、その辺の重複を最初のソートリスト作る時に削除すると、後半のループが減ってなお高速になる。
n, m = map(int, input().split())
disputes = []
for i in range(m):
a, b = map(int, input().split())
disputes.append((b, a))
disputes.sort()
ans = 0
most_right_bridge = 0
for b, a in disputes:
if most_right_bridge <= a:
ans += 1
most_right_bridge = b
print(ans)
