もふふろぐ

by

DDCC 2019 参加記

atcodercompetitiveeventprogram

1月19日のDISCO presents ディスカバリーチャンネル コードコンテスト2019に参加しました。 例年秋の開催でしたが今回は年末年始をまたいだため、DDCC 2018が存在しないことになります。

予選では700点（44:10）の327位という厳しい結果でしたが、2020年卒業者の枠で本戦に進むことができました。 また、実際に本戦に出場するには当日の9:50までに受付に着く必要がありましたが、これも何とか達成することができました。

会場は昨年と同じ本社10階のカフェテリアです。 あいかわらずの日差しのせいで、席によってはコーディングしづらい環境だったと思います。 Tシャツは水色でした。

本戦

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦

5問120分のコンテスト。 2完で900点（53:59）の133位になりました。 レート順位は113位だったので妥当な結果だと思います。

DDCCではいつも円を格子状に分割する問題が出題されていたため、今回そのような問題がなかったことに驚きました。

A レース (Race)

N個のマスからなるレース場が与えられ、このうち1マスを変更できるとき、走り切るのに掛かる最小時間を答える問題。 マスは2種類あり、雪（’-’）1マスには1秒、氷（’>’）1マスには1/(k+2)秒（kはその氷マスの直前に連続する氷マスの個数）が掛かります。

コンテスト中には、1マスの変更によって氷の連続成分が統合されうる入力（例 “>>->“を”>>>>“に変更）があると勘違いしていましたが、実際には制約で入力中の’-‘は2個以上連続することが保証されていたため、私は無駄に複雑な解法を実装していました。

B 大吉数列 (Array of Fortune)

数列構築問題。 降順であるとき「a_i >= a_j + K を満たす (i, j) の組 (i < j) の数」が最大になるので、これをR個まで減らしていくことを考えました。

入力のRがintから溢れると気づくまでに時間が掛かり、3WAしました。 A問題と同じく制約をよく見ていなかったことがわかります。

C 光の反射 (Reflection of Light)

2次元平面でのシミュレーション問題。

円の接線を計算する解法がすぐに思いつきます。 しかし、接線を求める計算や、円と直線の交点を求める計算は、コンテスト時間で実装するには複雑すぎます。 案の定、実装を終えることができませんでした。 円の交点などを扱う幾何問題に当たったのは初めてでなかったため、競プロスニペットを十分に整備していなかったことを後悔しました。

解説では、接線となる線分を二分探索で求めることで「直線と点の距離」に落とし込んでおり、賢いと感心しました。

昼食

肉と寿司とケーキ。 ゆったりと取りに行ってもまだ寿司が余っているくらいの量が用意されていました。

装置実装部門

DISCO presents ディスカバリーチャンネル コードコンテスト2019 装置実装部門 本戦

普通の競技プログラミングよりも実装力を重視した形のコンテスト。 30分という短時間で、装置の仕様を読み取り、制約を遵守したプログラムを書く力が試されます。 シミュレータ問題の上位10名が、実機を動かす決勝に進出できたのですが、惜しくも0点で20位という結果に終わりました。

DISCOの社長の「プログラミングで機械を動かす面白さを知ってほしい」という思いが込められた企画だそうです。 初めての開催であっただけに、シミュレータ部門では粗さが目立ちましたが、装置の完成度から熱意が伝わってきました。 決勝の観戦も面白かったです。

懇親会

稲荷寿司やDDCCケーキなどが振る舞われました。 早起きしたため眠かったです。