tooh’s diary

半角全角、常体敬体が入り乱れるカオス

2/27 AtCoder(小数点以下の四捨五入、直積(itertools.product())、いもす法(最大被覆区間))

こんにちは。競プロ合宿二日目のとーです。

 

AtCoder

解くに至った問題(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]]となる

atcoder.jp

 

 

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がくるのはわかりきっているので、二番目に小さい)ものを選ぶ それが、除くべき最小のポイント区間であり、逆にここを除くことで、その点上の区間は被覆されていないようにすることができる

 

という流れで答えを求めることができる

 

atcoder.jp

 

 

解けなかった問題

ABC:029D