Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

第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)

セグ木使わずに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))になるけど当然間に合う。

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;
}

C問題はピラミッドの作るフラクタルな性質を使って解くとのこと。「偶数番目を抜くと同じ形ができる」というのどうやったら気づくんだろう?

D問題は漸化式を行列に落として、似た形のものをうまく扱えば解ける~みたいな感じだったけどいまいち理解できなかった。解説が公開されたらしっかり読んで理解したい。

会社見学&懇親会

解説後は会社見学をさせていただき、その後は懇親会でした。

問題について話したり、おいしいご馳走をいただいたり。

f:id:ark4rk:20180204023622j:plain

ケーキもおいしかったです。

感想

お疲れ様でした。楽しい企画、おもしろい問題、色々ありがとうございました。

競プロは普段オンラインでやるけど、こういうオンサイトでやるタイプは新鮮でいいですね。オンラインとはまた違った楽しさがあるような気がします。モチベ維持にもつながるので積極的にオンサイトイベントに挑戦していきたいです。