第4回 ドワンゴからの挑戦状 予選
作成日：2018.01.14
カテゴリー：競プロ 参戦記録
目次
コンテスト前の計画
配点は$100-300-500-600-1000$である。
しかし通過枠は$5$しかないので、なるべく早く全完しなければならない。
とにかく前から順に解いていくことにする。
コンテスト中
A,B問題は簡単なのですぐ解けた。[A 04:58 AC][B 08:03 AC]
C問題は計算量解析を間違えて、TLEするコードを書き出してしまったため時間をロスした。
だが、なんとか計算量を落とすことができ通すことができた。[C 39:09 AC]
D問題はbitDPであることが制約から見えるので、解法はすぐに思いついた。
しかし細かいところでミスをしたので、1WAが出てしまった。[D 56:16 WA][D 60:08 AC]
E問題も制約から比較的すぐに解法を思いつくことができた。
しかしこれもバグを埋め込んでしまったため、1WAを出してしまった。[E 87:26 WA][E 103:20 AC]
コンテスト後(結果)
全完103:20、2WAの18位。
解法を思いついてから、ACを得るまでに時間がかかっているのが気になる。
実装力をつけるために、問題を解き続ける精進が必要であるようだ。
各問題の(軽い)解説
A : ニコニコ文字列判定
s[0]==s[2]&&s[1]==s[3]?"Yes":"No"B : 2525文字列分解
問題文
まず、$2$と$5$は同じ個数なければならないことはすぐに分かる。
また$2$を開き括弧、$5$を閉じ括弧とみなした時に、正しく括弧が閉じていないといけないことも分かる。
これらが満たされていない時、答えは$-1$である。
$2$と$5$をこの順に文字列から選んだ時、選んだ$2$より前で構成された2525文字列にのみつなげることができる。
このことから答えは文字列を前から見ていった時に現れた$2$,$5$の個数をそれぞれ$a$,$b$とすると、$a-b$の最大値が答えであると分かる。
C : Kill/Death
問題文
$killA_i$の総和$S_A$と$deathB_i$の総和、$killB_i$の総和$S_B$と$deathA_i$の総和はそれぞれ等しい。
すなわち$M$要素からなる整数列の和が$S_A$に、$N$要素からなる整数列の和が$S_B$になるような適切な整数列の数を数えれば良い。
前者と後者は同様に考えることができ、それぞれ独立であるから、以下では前者について考える。
$A$のキル数がすべて異なる時は、$i$番目まで見た時にデス数を$j$だけすでに割り振ったことを状態に持つDPを行えば良い。
このDPの計算量は$O(N {S_B}^2)$であるから十分高速である。
$A$のキル数で同じものがある場合は、同じものごとに個数を数えてまとめることでキル数が異なるものごとに先のDPを行う。
この時、$c$個の非負整数で総和が$s$になるようなものの組み合わせの個数$< c,s >$が$O(1)$で分かる必要がある。
よってこれを前計算で求めておく。
$c = 1$の時は常に1である。
$c \geq 2$の時、非負整数の中で最小のものを$z$とする。
これは$c$個の整数に$z$ずつ割り当てた後、残りの$s-cz$を$(c-1)$個の整数に割り当てると考えることで、$< c-1,s-cz >$通りあることが分かる。
このことを用いれば$< c,s >$を計算量$O(N S_B)$のDPで求めることができる。
D : ディスクの節約
問題文
制約からbitDPを行うことを考える。
状態として実行し終えたタスクの集合を持ち、その状態ごとに問題に対する答え$ans$と不要である実行結果を削除した時のディスクの使用量$m$を求めていく。
ある状態$S$への遷移は、$S$に含まれるタスク$e$で$S$中に$e$の依存先がすべて含まれるものにおいて$S-\{e\}$($T$とする)から行われる。
$ans_S$は$max(ans_T$,$m_T + x_e)$の最小値、$m_S$は$m_T + x_e$から$e$の依存先$u$それぞれについて$x_u$を引いたものである。
このbitDPの計算量は$O(2^N N)$であるから十分高速である。
E : ニワンゴくんの家探し
問題文
制約から1回の質問をするたびに候補となる頂点を半分ほどにしなければならない。
このことから重心付近の2頂点を選び質問すれば良さそうであることが分かる。
重心が2つある時、その2頂点を選んで質問することでいずれかの頂点が答えとして返されるが、いずれにおいても候補となる頂点を半分にできる。
重心が1つの時、重心$g$を根とした根付き木として考える。
$g$を質問する頂点として選んでしまうと、候補が最悪$4/5$にしかならないので、$g$の子のうち2つを選んで質問することにする。
$g$の子で部分木の大きさが大きいものから順に$c_1$ , $c_2$ , $...$とする。
まず$c_1$と$c_2$を選び質問する。
いずれかの頂点が答えとして返ってきた場合、候補はその頂点の部分木に絞られる。
$g$が重心であることから、この部分木の大きさは元の木の半分以下である。
$0$が答えとして返ってきた場合、$c_1$の部分木と$c_2$の部分木以外が候補となる。
このままだと候補が半分にならない可能性がある。
しかしその場合は$g$の次数は$4$以上であるから、$c_3$,$c_4$を選び質問することで、1回目の質問の前と比べて候補を$1/4$以下にすることができる。
いずれにおいても候補となる頂点集合は木をなしているので、このような質問を繰り返すことで答えを求めることができる。
質問回数は高々$log \: N$であるから、これで十分である。
＜(古い記事) Topcoder Marathon Match 96 最終結果