AtCoder Beginner Contest 103
17分で3完でした。
Rate:1135 → 1137 (+2)
A問題
2番目のタスクで場合分け(3通り)して最小値を求めた。
よく考えると2番目のタスクから他の二つのタスクまでの距離（コスト）が最小になるのはソートした時に2番目にくるものなので、最大値から最小値を引いたものが答えになる。
B問題
全通り試す。実装に手間取り13分程度かかった。
C問題
全てのa[i]の最小公倍数-1ですべてのa[i]についてm mod a[i] = a[i]-1 とできるので総和からnを引けば良い。
ここを3分で通し何とかレート維持に漕ぎ着けられたのは良かった。
D問題
数直線上の複数の範囲をできるだけ少なく串刺ししてすべての範囲を網羅する問題。このような問題は「区間スケジューリング」と呼ばれるらしい。
区間スケジューリング問題の解法は、範囲の右端でソートして小さいものから順に串刺していき、串刺した範囲に被らないもののうち左端が最小のものを串刺すことをくりかえすことである。
今まで数直線上の範囲をメモる時に数直線をリストとして表現して範囲内の数字を1つずつ増やして対応していてTLEしていたので(
Educational Codeforces Round 46 - プロコン参加記 のC問題とか) 解法がわかって進歩した気分。
↓この方のコードが簡潔で参考にさせていただきました。
