こんにちは。競プロ合宿二日目のとーです。
解くに至った問題（8問）
ABC:001C/005C/006C/015C/017C/028C/030C/057B
ABC001C
四捨五入をうまく扱えますか？的な問題
まず、調べて普通に出てきた組み込み関数round()を使ったところうまく動いてくれない
python3のround()の特徴として、
①0.5は、丸めた結果が偶数になる方に動く
[例]
round(1.5)→2
round(2.5)→2
round(3.5)→4
round(4.5)→4
②0.05......と小数点以下第二位よりも小さいところをround()で丸めると、①に当てはまらない場合が出てくる
[例]
round(0.35,1)→0.4
round(0.45,1)→0.5
これは、少数を浮動小数点で正確に表せないために起こってしまう
さて、四捨五入の他のやり方として
f =（何らかの与えられた数）を小数点以下第二位で四捨五入したいときは
P = Decimal(str(f)).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP)
とするといけなくもない（0.1の部分を0.01と返れば、第三位で四捨五入ができる）
ただ、これも扱いに注意が必要で、例えば
f = 32.65
という値は、上式に代入すれば、
P = 32.7
と返ってきて、一見よさそうだが、
P < 32.7
はTrueになる これはDecimalうんたらで表示桁を小数点以下下一桁にしてあるだけで、（見た眼的には四捨五入がうまく行ってるように見える）実のところ32.7より細かい情報は保持したままになっているからである
だから、本質的には32.65 < 32.7の比較を行っていることと同じになってしまう
これを解消する（つまり四捨五入した後のPを32.7として扱いたい）場合には、Pをfloatに変換すればよい そうすれば、Pが実は32.7より小さいんだという細かい情報が落ちて、P = 32.7として扱えるようになる
P = Decimal(str(f)).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP)
P = float(P)
とすればよい
さて、長々書いてきたが、こういった微妙な扱いを避けるために、四捨五入を自分で定義してしまうのが一番手っ取り早い
fを「四捨五入したい数」、digitを「少数第何位で四捨五入したいか」として
f,digit = map(float,input().split())
def my_round(f, digit):
p = 10**digit
return (f*p*2+1)//2/p
とすれば、これでうまく四捨五入ができたことになる
[例] f, digitを入力として、
my_round(32.65,0) → 33.0
my_round(32.65,1) → 32.7 # これはmy_round(32.65) < 32.7でFalseを返す
my_round(32.655,2) → 32.66
ABC015C
L = [[1,2],[4,5]]
というリストがあり、
L[0],L[1]から要素を一つずつ選んでくる（直積を求める）ようなコードを書きたい
itertoolsのproductというのを使うとよいらしい
文頭にimport itertoolsとつけてから使う
import itertools
M = list(itertools.product(*L)) #*LはL内の要素を表し、こうすればLに内包されたリスト
の数が増えても問題ない
とすれば、M = [[1,4],[1,5],[2,4],[2,5]]となる
ABC017C
長さがMの区間がある その中のいくつかの区間にポイントが与えられており、長さMの区間をすべて被覆しないように区間を一つずつ選んで（区間同士がかぶってもよい）、その合計ポイントを最大化する問題
いもす法を使う
実は以前に触れたことのある手法だったのだけれど、ここでも使えるのかと驚きました
具体例
温泉にi人の人が入りました p番目の人が入った時刻はH_j、温泉から上がった時刻はD_jです（時刻D_jまで温泉に入っていたことにする） この温泉には同時に最大何人入っていたでしょう？
例えば、H_j、D_jの入力が
1 4
2 6
3 5
4 7
4 6
みたいに与えられていたら、リストLを
L = [0,0,0,0,0,0,0,0]
と作っておく これは、L[t]が時刻t-1に何人が温泉に入っていたかを表すリストになる
ここでは、上から入力を受け取った順に、
L[H_j-1] += 1 （温泉に人が入った）
L[D_j] -= 1 （温泉から人が上がった）
とすると、
L = [1,1,1,2,-1,-1,-2,-1]
となる
これを前から順に足していったら、
L = [1,2,3,5,4,3,1,0]
となり、時刻4で最も多く人が温泉に入っていたと分かる、というような手法
（今上で挙げたコードでは最後が0になっている ここに注意する）
さて、上の例では「最も多く被覆している部分はどこですか」というのを求めるためにいもす法を用いたわけだが、今回は「被覆しないところを残しつつポイントを高くしたい」というのが目的である
結論から言うと、一か所でも被覆していないところがあればよいので、まず全部被覆したとして、合計ポイントを加算する そこからいもす法と同じやり方で、区間の各点におけるポイントを計算し、リストに保持しておく
このリストは、その点を被覆する区間が持つポイントを表している（このポイントは、複数の区間の合計ポイントであることもあり得る なぜなら各点を被覆する区間は単一とは限らないので）
そして、それが求め終わったら、リストをソートして、最も小さい（上の例で言えば、ソート後の一番最初に0がくるのはわかりきっているので、二番目に小さい）ものを選ぶ それが、除くべき最小のポイント区間であり、逆にここを除くことで、その点上の区間は被覆されていないようにすることができる
という流れで答えを求めることができる
解けなかった問題
ABC:029D
