AtCoder Beginner Contest 165 振り返り
C - Many Requirements
A = {1,3,4} のとき
A3 - A1 = 4- 1 = 3 = c1 O 100点入る
A2 - A1 = 3- 1 = 2 = c1 O 10点入る
A3 - A2 = 4- 3 = 1 ≠ c1 × 10点入る
計110点
解き方：条件を満たす数列を全探索
Ai = i 番目の仕切りより左側に存在するボールの数 + 1 と置けば
N 個の仕切りと M − 1 個のボールを並び替えた列と一対一に対応
この際、Aの各要素を生成するのにitertools ライブラリがとても便利
import itertools
A = np.array(list(itertools.combinations_with_replacement(range(1,M+1),N)))
それぞれについてスコアを計算
s = np.zeros(len(A), np.int32)
for i in range(Q):
a,b,c,d = map(int,input().split())
s += d * (A[:,b-1] - A[:,a-1] == c)
print(s.max())
参考
E - Rotation Matching
全体N人、1ラウンドでM試合、これをN回行って被らないようにする（番号はローテーション）。
解き方：
Nが奇数と偶数、Mが奇数と偶数の場合で答えが変化
基本は1とN、2とN-1… と変化させていけばよい
Nが偶数の時は途中で1ずらせば良い
F - LIS on Tree
最長増加部分列問題 (Longest Increasing Subsequence)を木構造で解く
木構造の部分は巻き戻しを実装することでできる
他の参加者の実装例
