Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

DDCC2019 参加記

競プロ 参加記

DDCCこと、DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦に参加してきました。

www.discoverychannel.jp

雰囲気とかはハッシュタグを辿ると色々と写真が見れて楽しめるかと思います。

予選

ABCまで解いて139位、無事非就活枠で本戦通過できました！

昨年のDDCCでは大爆死をして、就活枠にもかかわらず本戦チャレンジを失敗したので、雪辱戦の意味もあり嬉しかったです。

当日

スケジュール

  1. 開会
  2. コード部門コンテスト
  3. 昼食
  4. 装置部門コンテスト 予選
  5. 会社見学
  6. 装置部門コンテスト 決勝
  7. 表彰式/懇親会

開会

かっこいいオープニングとともにスタート！

コード部門コンテスト

ABまで解けてあとは座る人をしていました。114位でした(´・ω・｀)

普通に実力不足を感じたので精進したいです。以下、解けた問題の解説(思考メモ)。

A - レース (Race)

制約を完全に見逃していて「連続する雪マスは2以上」を気づかず、解いてしまいました。一応、この制約がなくても解くことは可能で

  • 累積和をめっちゃして前計算をがんばる
  • 各雪マスを氷マスに変更したときの経過時間の差分を前計算を利用してO(1)で求める。合わせてO(N)
  • 差分が最小となるものを選ぶとそのときの経過時間が答え

これでACを取りました。

配点300点にしたらむずかしいし、また企業コン特有の得点詐欺か？と思ったら恒例の誤読ミスで反省。

B - 大吉数列 (Array of Fortune)

構築問題。転倒数を漂わせる問題。

  • a_i \geq a_j+K \land i \lt jとなる組 (i, j)の個数を xとおく。
  • N, N-1, \cdots, 1が xを最大化するので、「この状態から xを減らすように数列をいじって最終的に Rにできるか？」を考える
  • 実はこれは大きい数から順に貪欲に位置を動かすことで、可能かがチェックできる
  • 貪欲なので動かす位置は各数に対しO(1)で定まり、合わせて O(N)。十分間に合う
  • 実装上pushBackがO(1)でできるデータ構造があればOK

これでACが来た。

昼食

昼食は豪華なビュッフェでした。寿司🍣🍣🍣🍣🍣🍣。チョコフォンデュとかもあった。

おいしくいただきました😊

あとC問題の解法アイデアが浮かんだ。

これで実装量が減っていけるはず。

追記：

omizatta.blog.fc2.com

ああなるほど。誤差許容がゆるいから円周を等分割→線形探索すればいいのか

装置部門コンテスト 予選

今回のDDCCから追加された企画です。

実際の機械を動かすことを意識した実務よりなマラソン問題。

・・・30分で問題理解&実装が間に合わずno submitでした💦

なんと参加者200人中、正の得点の入手者19名！

かなしいね。。。色々考える前に自明解を提出するべきだった。

会社見学

装置部門の本戦通過者が戦っている間、他の人にはディスコさんの会社案内がありました。

会社内に温水プールやジムやダーツ/ビリヤード場があるなど、色々新鮮でした。また、機械が実際に動く様子も見せていただきました。

写真を取り忘れました＞＜

装置部門コンテスト 決勝

機械を実際にプログラムで動かして戦うタイプの決勝でした。

文字だけだと伝えられないですが、端的に言ってすごく面白かったです。シミュレータ上だとかなり理想的な状況でプログラムが動くが、物理では「水がこぼれないように移動速度/加速度を調整する」といった調整しづらい部分を考察する必要があり、物理ならではの面白さがありました。

普段やっているコンピュータ上でプログラムを動かすことももちろん楽しいが、こういうリアルへ影響するプログラムを書くというのはさらなる楽しさがあるのだと。今回は見るだけだったけど、この楽しさを肌で感じたいものです。

次回DDCCはさらにグレードアップするとのことなので、非常に楽しみです。

表彰式/懇親会

よすぽさんがコード部門&装置実装部門ともに優勝しててほんとにすごい

感想

DDCCは初参加でしたがとてもたのしいイベントでした。次回も開催する雰囲気なのでぜひとも参加したいです。

装置実装部門のさらなる発展にすごく期待してます。

最後に全体写真を撮って終了しました。