第4回ドワンゴからの挑戦状参加記

第4回ドワンゴからの挑戦状本戦に参加しました！

dwango.co.jp

予選

第4回ドワンゴからの挑戦状予選

ABC+E(部分点)で76位でした。

19卒枠として無事出場することができました！
本選出場者の中では最下位のようでほんとギリギリでした。

DDCCでもコロコンでも大爆死してたのでめちゃくちゃ嬉しかったです。

当日

場所はドワンゴ本社で行われました。

コンテスト

第4回ドワンゴからの挑戦状本選

2時間で4問、配点はA:400, B:800, C:1300, D:1400(1300)

A問題

秒針、分針、時針のあるアナログ時計について

初期時刻
秒針と分針が重なった回数
分針と時針が重なった回数

が与えられるので、ありうる時刻の範囲を求める問題。

見た瞬間実装めんどそうだなぁと思った。思いつくままにコードを書いてたら無限にバグらせて50分くらい経過。焦りを感じながらやむなく一旦B問題へ

B問題

K=0のとき、LIS（最長増加部分列）を求めるのと等価。LISの計算をいい感じにしてK>0のときも対応できないか考えた。

$\mathrm{dp}[j][i] := \text{高々}j\text{回の違反をしている長さ}i+1\text{の増加部分列の末尾のうち最小となる値（存在しない場合INF）}$

のDPで、違反のときは直前の値が-INFとみなすことができるので $dp[j][i]$ から $dp[j+1][i]$ への遷移は $dp[j+1][i] \leftarrow -\mathrm{INF}$ でいけそう。実際にコードに落としてみると通った。 $O(NK\log N)$ 。

Submissions #2049861

セグ木使わずにlowerBoundでやったのでシンプルな実装になったと思う。

C, D問題→A問題

Cは、この問題のxorバージョン。でも解法は関係なさそう。xorの性質をうまく使ってやるんだろうなぁと思いながらパス。

Dは、とてもシンプルな問題なんだけど、制約がありえんでかい。これもパス。

再びA問題に戻ってコードを書き直したりしてたけどここでタイムアップ。終。

結果

結果はBのみ解いて30人中24位でした。Bはたまたま解ける問題だったので実装めんどそうなAは早めに切り上げてBを解けばよかったなあ。とはいっても、Aはやるだけだったので通したかった。C, Dは今の実力だとしょうがない感あったのでそのうちこれと同程度の問題も解けるように精進していきたいです。

解説

コンテスト後は解説がありました。

A問題はやっぱりやるだけだった。ただし実装面できびしい。一応帰宅後に通した（Submissions #2054612）けど、スマートに実装できない・・・

B問題は別解として「適当な大きい定数 $c$ を使って $v_1+Kc, v_1+(K-1)c, \cdots, v_1, v_2+Kc, v_2+(K-1)c, \cdots, v_2, v_3+Kc,\cdots, v_N$ の大きさN*(K+1)の配列を作って普通にLISの計算をする」が紹介されててなるほどなぁと思った。テクニックとして覚えておきたい。この解法だと $O(NK\log(NK))$ になるけど当然間に合う。

Submissions #2059529

void main() {
    int N, K;
    scanln(N, K);
 
    long c = 10L^^10;
    long[] vs = readln.split.to!(long[]).map!(v => (K+1).iota.retro.map!(i => v + i*c).array).join;
 
    long[] dp = new long[vs.length];
    dp[] = INF;
    foreach(v; vs) {
        auto p = dp.assumeSorted.lowerBound(v);
        dp[p.length] = v;
    }
 
    dp.count!(a => a<INF).writeln;
}