AtCoder

5分で差分配列法を理解するためのノート 差分配列法 ある配列Aに対して、次のような操作を効率的に行いたいときに使える ある範囲 [l, r) に対して値 x を一括で加算する。 全体をスキャンして、範囲ごとの値を取得する。 以下の例を考える 長さ 10 の配列 A があるとする。初期値はは全て 0 。以下のような操作を考える。 区間 [2, 5) に 3 を足したい。 区間 [7, 9) に 5 を足したい。 これを差分配列法で解くために、まずはその名の通り差分配列を用意する。 D = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] まずは差分配列に愚直に操作を行う。 [2…

問題 B - Trained? 思考 N <= 105のため、全探索が可能そう 愚直にボタン1から順に辿っていって、ボタン2を押せるかをシミュレーションする 無限ループは避けたいので、訪れたボタンは記録するようにする N = int(input()) a = list(int(input()) for _ in range(N)) cur = 1 answer = 0 visited = {1} while cur != 2: cur = a[cur - 1] if cur in visited: answer = -1 break visited.add(cur) answer += 1 p…

70 問題 C - 100 to 105 思考 Xが100の倍数の場合は、100円のおにぎりを買うことで達成できる Xが100の倍数でない場合は、101~105円の商品を組み合わせて達成する必要がある X mod 100が1 ~ 5の足し算で作れればいいので、大きい方から順番に引い確認する 合計金額 >= 引いた回数 * 100であれば達成となる X = int(input()) m = X % 100 p = [5, 4, 3, 2, 1] if m == 0: answer = 1 else: count = 0 for i in p: while m > 0: if m - i >= 0…

実装中心で．テンプレは別記事．

問題 C - Energy Drink Collector 思考 Aを小さい順にソートして、M本になるまで順番に買い集めるのが早そう。 import sys N, M = list(map(int, input().split())) AB = [list(map(int, input().split())) for _ in range(N)] AB.sort(key=lambda x: x[0]) amount = 0 answer = 0 for ab in AB: for i in range(1, ab[1] + 1): answer += ab[0] amount += 1 if …

問題 B - Similar Arrays 思考 N <= 10以下のため全探索できそう Aと数列bを算出する Aから以下の2数列を算出する A'：A[i] + 1の数列 A''：A[i] - 1の数列 A, A', A''でzip処理（縦横変換）することでi番目の要素のプールを求められる その結果から直積を求めることですべての数列bを求めることができる あとは計算するのみ import functools import itertools import operator N = int(input()) A = list(map(int, input().split())) A_plus =…

問題 C - Same Integers 思考 [操作] A,B,C のうち2つを選んで、その両方を1増やす A,B,C のうち1つを選んで、その整数を2増やす 2つの数字を4増やす場合に必要な操作を考えると 操作1を4回 操作2を4回 になるため、どちらの操作でも操作回数は変わらない。 それを踏まえると次の操作で対応できると思われる。 最大値 - 中央値 = 操作1の回数 最大値 - ( 最小値 + 操作1の回数) = 残りの差 残りの差が偶数の場合はすべて操作2となるため、残りの差 / 2 = 操作2の回数となる 残りの差が奇数の場合は、残りの差 + 1までは操作2で増やし、+1分を操作1…