math314のブログ

主に競技プログラミング,CTFの結果を載せます

DDCC2019で準優勝した

DDCC2019という DISCOさん主催のオンサイトコンテストに参加しました。

www.discoverychannel.jp

コード部門 (10:10:00 開始)

atcoder.jp

A - レース (Race) (10:24:48 AC)

S において、- は必ず別の - と隣接して現れる と太字で書かれているのに見逃して、一般の場合を解いていた。

14分ちょっとでAC

B - 大吉数列 (Array of Fortune) (10:31:17 AC)

こういう問題は辞書順と同じく、現在見ている場所に x を置いて、無理なら別のものを置くというのを

先頭から貪欲に繰り返せば解けることが多い。

O(n2)では通らないが、明らかに残っているものの中で最大の数と最小の数以外を考えなくてもいいことが分かるのでO(n)で出来る。

  1. {1,2,3, ... N} の K転倒数 (転倒数の定義から察してください) は 0 で最小
  2. {N, N-1, ... 3, 2, 1} の K転倒数 (転倒数の定義から察してください) は N-K + N-K-1 + N-K-2 + ... + 1 + 0 で最大
  3. 上手に構築すれば 上記の単純な足し算の式からいくつかの数を抜き出すことが可能
  4. 例えば N=5, K = 2 の時、 {5,4,3,2,1} の K転倒数は 1 + 2 + 3 = 6 だが、ここから1と3を消して 2 だけにするとか 1だけ消して2+3 = 5にするとかは自由に出来る
  5. {a1, a2, ... ai-1} まで構築済みの時、aiの候補として、残っているものの中で最大の数と最小の数のみを考えれば上記の式でやれるよね

という感じになのだが、自分の頭の中では逆順に思いついていった。5が最初に出てくるのは経験だと思います。

Aで複雑な解き方をした分Bの方が簡単だった。

C - 光の反射 (Reflection of Light) (提出なし)

幾何は失敗すると時間が解けるので後回し決定。BをACした時点でDを解いている人もいるしDに突撃。

D - DISCO! (10:47:03 AC)

DPの遷移をSegment Treeに乗せると解けるやつということが分かるので実装する。個人的には一番簡単だった。類題はcodeforcesとかhackerrank, codechefで見かけるイメージ。

実行時間が13sと長いもののSeg木にvector<vector> を乗せるとMLEやTLEが発生する気配を感じるので固定長のarrayを乗せることにした。

CとEを見比べたところ、面白そうだしワンチャンあるのでEにチャレンジすることに。

E - 飾りつけ (Decoration) (12:02:42 AC)
  • 1 ~ 2000 を 1~1000, 1001 ~ 2000 に分けるといいのか?(10:50)
  • 上の分け方も2の累乗パターンは無理そう (11:00)
  • 1 - 50 - 50 - 1 みたいなグラフを作れば 50 * 50 の値を表現出来そうだけどACは取れそうにない (11:10)
    • 解説にある解法 #1 と同じです
  • 結局の所 {a, a+1}, {b, b+1} みたいなのを1つのノードに集約出来なければこれ以上のノードは節約出来ない… (11:15)
  • a を入力すると {a, a+1} を出力するような部分グラフは作れるっぽい (11:20)
  • 1 ~ 2000 の数が与えられるんだから、{1,2}, {3,4}, {5,6}, ... {1999, 2000} みたいに分けて、{}, {a}, {a + 1}, {a, a+1} の4パターンに分けてどうにかする?どうにかって何?
  • {a}と{a+1} は同一視していい
  • 3つ, 4つ区切りでも出来そうだから、とりあえずノードの減りそうな3つ区切りにする
  • {a}, {a, a+1}, {a, a+2}, {a, a+1, a+2} の 4パターンを考えればいいっぽい (11:30)
  • こんがらがってきたので整理すると、こんな感じになる

f:id:math314:20190121030456p:plain
Eの整理後のイメージ

  • 青い層で 0 を増やして、 青とオレンジの層の間で直積をとる感じで必要な数を生成。最後にオレンジと緑の層で {a}, {a, a+1}, {a, a+2}, {a, a+1, a+2} の生成を調整する。
  • 最後の層のノードは3つ固定だが青とオレンジは分からない。解説にもあるように {a} パターンと {a, a+1} パターンは同じオレンジ層のノードに乗せることは出来ない。
  • ノード数の合計は100以下なので、 青い層のノード数を i, オレンジ層のノード数を j として、答えを生成出来る中で i + j が最小のものを探せばいいのでは?
  • 実装して出すと1080点 (11:55)
  • 4つ毎に分ければどうなるだろう?ということでリファクタリングと改造を施しつつ粘る。
  • AC!!! (12:02)

7, 8分でCが実装出来るはずもないので終了。結果は2位でした。

装置実装部門

MM形式にも関わらず予選が30分なので、読解&シンプル解法高速実装コンテストということが想像できる。

20分程度で書き上げたもののWA、最後までWAが取れなかった、残念。機械を範囲外に動かしたのが敗因だった様子。

装置部門の決勝がめちゃくちゃ楽しかったので次回参加出来れば勝ち上がりたい。

感想等

ICPCやISUCON, CTFだとそこそこの順位は何度も経験しているがこれらは全て団体競技。味方が強ければ、例え優勝出来たとしても自分単体はそこまで強いわけではないのかもしれないという気持ちが拭えなかった。 今回の個人大会では多数の強い人々が参加している中での2位なので本当に嬉しい。これまで参加していた大会の中でも一番かもしれない。

社会人となってしばらく経ち勉強や練習出来る時間も減ってしまった(スプラトゥーンが多大な影響を及ぼしている)。 同時期に競プロをしていた人々と同じようにそのうちゆっくりとフェードアウトしていくかもしれないが、いい思い出になった。

競プロが出来なくなる前に、ゆったりと参加出来て健康に良いらしいとされているKaggleにも参加してみたいですね。

帰る時にプレートも一緒に持って帰ろうかと思ったけど、冷静に考えると置く場所に困りそうなのでかわりに写真を撮っていただくことにした。快く引き受けてくださったスタッフの皆さんありがとうございました。