naoya_t@hatenablog

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

AtCoder Petrozavodsk Contest 001

apc001.contest.atcoder.jp
Petrozavodskって何だ?
というのはさておき。土曜深夜に5時間コンテスト。

寝ぼけててlong longにし忘れてWAみたいなのが多かったけど残り5分で5問目を通して5完。眠いけど頑張った。
ooooo----- (147th) 1616->1715 (+99)
f:id:n4_t:20180204054934p:plain
順位表では147なのに142ndなのはなぜだろう
f:id:n4_t:20180204054923p:plain
パフォーマンスは2216(黄)とな
続けて出てれば黄色(2000〜2399かな)までは行ける気がしてきた。
f:id:n4_t:20180204055105p:plain

A - Two Integers (100点)

なんか結構悩んだ。
XがYで割り切れるなら何を選んでも駄目。
割り切れないならXでいいじゃん。(XそのものもXの倍数ってことでいいよね?とかそんなレベルで迷ったけど)
→AC
https://apc001.contest.atcoder.jp/submissions/2051375

B - Two Arrays (300点)

a と b の各項の差を見る。正・負・ゼロに分類する。正の項は1つずつ(どこかを2つ増やしながら)減る。負の項は2つずつ(どこかを1つ減らしながら)増えるか、1つだけ(どこにも影響を与えずに)増える。ので、(正の項の数)≦(負の項の数/2)なら行ける。
→WA

あれ、long longじゃないと駄目じゃん
なんでそんな所で落とすかな
直して
→WA

あれあれ?…あ、+=を=って書いてた><
直して
→AC
https://apc001.contest.atcoder.jp/submissions/2054987

C - Vacant Seat (500点)

楽しいインタラクティブ問題。
円状に並んだ奇数個の座席(最大99999席)があって、男女が同性で固まらずに(交互または空席をはさんで)座っている。
空席が必ず1つあるのは自明だが、どこにあるかを20回クエリを投げる間に1つでも当てれば良いという問題。
・席Aと席Bの間に奇数個の席がある場合(B-Aが偶数)、席Aと席Bの人の性別が異なるなら必ずこの区間に空席が1つはある。性別が同じならこの区間の空席の有無は断言できない。
・席Aと席Bの間に偶数個の席がある場合(B-Aが奇数)、席Aと席Bの人の性別が同じなら必ずこの区間に空席が1つはある。性別が異なるならこの区間の空席の有無は断言できない。
必ず1つ以上の空席を含む開区間[A,B) について中点Mを選んでその席についてクエリをすれば、[A,M) に必ず空席があるか、[M,B) に必ず空席があるか、の少なくとも一方は言えるので、二分探索で必ず1つ以上の空席を含む区間を狭めていくことができる。
(ここまでのクエリで空席を引いたらその時点で終了する)
区間長が3以内になるまでに高々17クエリ。あとはその区間の未クエリ席を総当りしても20クエリに収まる。
→AC
https://apc001.contest.atcoder.jp/submissions/2055993

D - Forest (600点)

まずはunion-findで島分け。
各島に含まれる頂点(の値)リストを作り、それぞれ昇順にソートしておく。
priority_queue<vector<int>> に放り込んで、コストの低いやつ2つをくっつけて、島が1つになるまで続ける。
→TLE+WA
さすがに遅いか
くっつける所をinsert insert sortで書いてたのをmergeにする。O(N)のはず。
→WA(1つTLEあり)
TLEはさておきWAはなんでだ?ああ、1e9が1e5個集まると1e14だよねlong longだよねなんでintで計算してるの(solve関数をlong longにする)
いや、これ何か速く計算できる方法ありそう…
島がm個あるとき、これを1つの島にまとめるには m-1 回の連結操作が必要で、それに伴い 2(m-1) 個の頂点を消費する。
どの島も他のどこかの島と連結するので、各島の一番安い頂点は必ず使われる。これはもう除外してしまおう。m頂点。
残り 2(m-1) - m = m-2 頂点を、残り頂点から適当に(コスト昇順で)選んで行けば良いのでは? 頂点がm-2個残っていなければ Impossible でよくて。これで1つに島にまとまらない反例とかあるかなあ…と眠い頭で考えて(思いつかなくて)
とりあえずサンプルケースといくつかのケースは通ったし投げてみるか
→WA(前半はAC)
ちょっとこれ以上は眠い頭では無理だ…諦めて先にE(〜F)を読む

EFを考えてる時に、あれもしかして、と思ってDの提出コードを見たら、long long solve() を int 変数で受けてる。
これをlong longに直したのを投げて
→AC
https://apc001.contest.atcoder.jp/submissions/2060028

> 今日はケアレスミス多すぎるな… 眠いのに5時間コンテストとか出たらそんなもんか…

E - Antennas on Tree (900点)

なんか無理、と思って一旦パス
Fを少し考えてから戻ってきた。Fで書いたパーサを流用してとりあえず入力部分を押さえた。
部分木の親ノードが子供をmノード持っている場合、それぞれの子供に1つずつアンテナを仕込めばとりあえずどの子ノードかは識別できる。けどそんなに要らない。1つは削れる。ってのをボトムアップにrootに向けて足し込んでみる。
→WA
テストケース前半は合ってた。
ここまでの考え方だと、例えば3人子供がいるノードの下にはアンテナが2つ要るんだけど、そのノードの1段上があったら2つじゃ足りない。(削った方の子孫なのか、祖先側なのかが区別できない)
単純に足し込むだけじゃ駄目かも。子から親へアンテナ数を報告して、親の側でどうするか決めるようにした。
あと、rootをとりあえず0にしてたけど、一番子供の多いノードをrootにしてみる。こうすればその辺りのコーナーケースが発生しないでしょう。
→WA
削っちゃいけないケースがあることに気付いた。
子ノードが3つあって、それぞれに3ノードずつ付いてたら…子ノードのレベルでアンテナ2つずつ(1個削れる)ってのはいいんだけど、rootで削れるアンテナがなくなる。これはどう表現すればいいんだろう。
1つでも枝分かれがある(どこかの子ノードが2つ以上ある)系統では他の系統と合流する時にアンテナを削れない。
「この系統ではアンテナは削っちゃいけない」という情報を親ノードに上げていくようにした。
→AC
https://apc001.contest.atcoder.jp/submissions/2061424 (4:54:58)
ACが出るのを見届けて残り4分。ここで投了。

F - XOR Tree (1000点)

開いた
root(とりあえず0)からトップダウンに攻めるべきかleafからボトムアップに攻めるべきか、あれこれ考える。
とりあえず入力をパースしてツリー構造を組み立てるところまで書いた辺りでEに戻る;

G - Colorful Doors (2000点)

開いてない(2000点て何だよw)

H - Generalized Insertion Sort (2000点)

同上

I - Simple APSP Problem (2000点)

同上

J - Rectangles (2100点)

同上