AGC011個人的な反省
遅刻
理由は、これ
これのせいで20分ほど遅刻して参加しました。
2問解けました。
今回のセットはレート1600位までは、2問早解きででそうだったのでとても残念です。
解説?
A問題
時間Tiに N 人の乗客が到着します.
乗客を待たせる時間をK以下にして、バスの定員がCのとき。
何台バスを出発させる必要がありますか?
という問題でした。
考察としては、バスの出発時間を最大限遅らせるためにはT[i] + Kにバスが出ることにすればいい、ということだけでした。
よって貪欲で解けました。
到着時間をソートした後。(入力はソートされていない)
- バスには現在何人乗っている。
- バスは何時に出る。
- バスは何台出た。
という三つをもって貪欲しました。
新しいバスが必要になる条件は、定員オーバーと前のバスが出たという二つになります。
境界条件が分かりづらいので注意。
Submission #1157617 - AtCoder Grand Contest 011 | AtCoder
B問題
N匹生き物がいて、自分の体の2倍以下まで食べられます(食べた分だけ大きくなる)。最後まで残ることができるのはどのサイズの生き物まででしょうか?
という問題でした。
考察は、自分より小さい生き物は全員食べられる。
自分より小さい生き物を全員食べた上で食べられない生き物がいればそいつ以下の生き物は生き残ることができない。
つまり、生き物の大きさをすべて足していってその2倍よりも大きい生き物がいたらそこを記録するということをするだけです。
これも入力をソートする必要があります。
例3
40 1 30 2 7 20
ソート
1 2 7 20 30 40
足していくと
1 3 10 30 60 100
大きさ3の生き物は7の生き物をたべられないので、そこを記録します。
よってこれは、それよりも大きな4匹の生き物が残れるので答えは4になります。