naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 018

agc018.contest.atcoder.jp
7/23 21:00-23:10
AGC2回目
2完 (oox---) 1000点、1ペナルティで78:01(318位)
やっとレーティングが4桁になった…
f:id:n4_t:20170723234723p:plain
f:id:n4_t:20170723234732p:plain

A. Getting Difference

何十分も悩んでたどり着いたのがこの解法:

数のリストAがあって。これをまずソートしておいて。
「この数さえあれば行ける」リストにKを追加。
Kより大きい数についてそれぞれ、Kとの差分を「この数さえあれば行ける」リストLに追加する。
Aの中に「この数さえあれば行ける」の数がどれか含まれていれば
Aの中の隣りあった数の差分dをAに追加する。この新しい数dが「この数さえあれば行ける」のどれかならOKで終わる。そうでない場合、「この数さえあれば行ける」のうちdより小さい数について、dとの差分を「この数さえあれば行ける」に追加する。
Aがこれ以上増やせなくなったらそこで終わり。
(リストって書いてるけどソートと挿入の手間を考えて実際にはそれぞれsetで実装)
→AC
https://agc018.contest.atcoder.jp/submissions/1446408

いやこれもっとスマートな方法があるんだろうな…

B. Sports Festival

最大許容人数を二分探索で。
最大許容人数をmと仮定する。ある各個人の一番好きなスポーツに行ってもらって、参加者がm人を超えてしまったスポーツについては一旦解散して、次に好きなスポーツに行ってもらって・・・で全員が参加するスポーツが決まるかどうか。
→WA
https://agc018.contest.atcoder.jp/submissions/1447602
あれ。二分探索の最大値をNじゃなくてMにしてた。直したら通った。
→AC
https://agc018.contest.atcoder.jp/submissions/1447747

C. Coins

とりあえず全員から金をもらって
銀をY人から(銀をたくさん持ってる順に)もらって(金との差分を差し引いて)
銅をZ人から(銅をたくさん持ってる順に)もらって(金との差分を差し引いて)
銀と銅を同じ人からもらってしまった分について、銀・銅それぞれの次点の人との差を調べて、ましな方に取り替えて(差分を差し引いて)
でサンプルは全部通るんだけど
まあ、もう時間少ししかないし投げとくか
(終了まで7分以上あったけど、終わってからも暫くジャッジ待ちだった。そんなこともあるのね)
→WA
https://agc018.contest.atcoder.jp/submissions/1449483

D. Tree and Hamilton Path

unopened

E. Sightseeing Plan

unopened

F. Two Trees

unopened