エンジニアの田中です。

RCOアドテク部では、初の試みとして「RCO presents 日本橋ハーフマラソン」というプログラミングコンテストを開催しています。

その予選が先日開催されました。コンテストの内容についてお伝えします。

コンテストの形式

3時間の制限時間で2つの問題を出題しました。2問とも、提出されたプログラムの完成度に応じて段階的に点数がつく形式の問題です。より良い解を出せるよう制限時間いっぱいひたすらアルゴリズムの改善を続けるという、参加者にとってはなかなかハードなコンテストだったのではないでしょうか（お疲れ様でした）。

近年は様々な競技プログラミングコンテストが開催されていますが、その多くは時間内に正解できた問題の数を競うものです。それはそれで面白くはあるものの、せっかく開催するのなら一風変わったものにしたい！　という思いがあり、こういったあまり例のない形式にしました。

さすがにこの制限時間内に2問とも賢い解法を考えて実装・デバッグまでやりきるのはかなり厳しいことが想定されるので、予選通過ラインは「それなりに適切な貪欲アルゴリズムを実装できた」あたりになることを念頭に置いて問題を作成しました。

A問題「Multiple Pieces」

問題のルールはリンク先を参照ください。

スコアは掛け算になっているので、大きい数同士をくっつけるのが良い戦略です。盤面上の未使用のマスの中で最も大きな数のものから幅優先探索を行い、隣接する数が大きいマスを順次くっつけていく、といった方針が考えられます。

なお、オクトミノの種類は全部で2725個しかなく、すべてのピースの作り方を列挙することが可能です（0が含まれるものを除外すると、250万通りくらいになります）。そのうえで、スコアが高いピースから順に使えるなら使うという貪欲法を行うと、本番4位相当の得点になります。ただしポリオミノの列挙は地味に難しく、よほど実装に自信がないと取りづらい方針だとは思います。

B問題「Food Collector」

問題のルールはリンク先を参照ください。

エサの価値は時間で減衰するため、できるだけ早く回収していきたいという気持ちになります。最も近いところにある正のスコアが取れるエサへ向かっていくようにすると、なんとそれだけで本番8位相当の得点が取れます。さらに、最も近い正のエサが等距離で複数個ある場合にはどれを選択するかをランダムに選ぶようにして、それを時間制限いっぱい試すと、本番4位相当の得点になります。

これ以上伸ばすには、ビームサーチを使って良い方針の取り方を優先して試していけるようにするとよいでしょう。こちらも、コンテスト時間中にビームサーチを実装し切るのはかなり難しいとは思いますが…。

本戦

本戦は3月20日(祝) 14:00-18:00 に開催します。よりじっくり考察できるよう、時間を4時間に延長しました。

本戦に参加できるのは予選で上位に入った方のみですが、本戦と同じ問題に取り組むオープンコンテストをオンラインで同時開催します。予選よりさらに面白い問題になっていると思いますので、是非ご参加ください！

コンテストページ