選ぶタスクの $A_i$ を増やしたり減らしたり行ったり来たりすると、往復する分が無駄なコストとしてかかってしまうので、小さい方から徐々に増やす(または大きい方から減らす)のがよい。
間を省略すると、$A_1,A_2,A_3$ の最大値ー最小値が答えとなる。
a, b, c = map(int, input().split()) print(max(a, b, c) - min(a, b, c))
全部試す。
s = input() t = input() for _ in range(len(s)): if s == t: print('Yes') break s = s[-1] + s[:-1] else: print('No')
ある $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)
1 2 3 4 ○===○===○===○ > 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$ が出てきたら、
以上で、壊した橋の数が答えとなる。
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)
もっとよい実装が解説されていた。
$(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)