Xmas Contest 2019
12月24日にAtCoderで開かれたXmas Contest 2019の感想です。318点194:18で25位でした。
コンテスト
Q1. どんな問題が出題されるのでしょうか？
A1. 全体的に，「一風変わった問題」を目指しています．過去の問題が参考になるかもしれませんが，傾向が同じとは限りません．
A Signboard 1
100点 27:56
8×8枚に分割された紙（画像）を復元する問題。 入力をダウンロードできるので人力でがんばることでACできます。 私はデスクトップでサムネイル表示のファイルを並べて解き、FAを取りました。
A問題のFAになっていた(๑>﹏<๑｀)！ #xmascon19
— ˚‧º·(˚ ˃̣̣̥ ⌓ ˂̣̣̥ )‧º·˚ (@reminjpn) December 24, 2019
他のコンテスタントのツイートを見ると、がんばり方は様々で、
- ペイントソフトを使う
- プレゼンテーションソフトを使う
- 印刷する
などがありました。 また、少ないながらスクリプトを書いている人もいるようでした。
J Sub-Post Correspondence Problem
100点 68:33
競技プログラミング。 普通に解き、C++で実装してACしました。
L Signboard 2
100点 191:16
A問題の続き。 復元した紙の裏側に書かれていた英単語を使い、別途与えられたスケルトンパズルを解く問題。
初めに、紙の裏側に書かれていた英単語は分割されている可能性があるので、A問題の解答を使用して復元します。 得られた英単語を長さ別にして持っておきます。
次に、スケルトンの空欄に入る英単語をDFSします。 空欄の個数も単語の個数もさほど多くないので、1秒も掛からずに解答が求まります。 ただし、探索では、既に単語を入れた空欄と交差する空欄を優先することで、枝刈りが効くようにする必要がありました。
ところで、この問題では質問を投げましたが「ノーコメント」でした……。
C Sokoban
18点 194:18
いわゆるポケモンの「かいりき」を使い、すべての荷物を指定されたマスに移動させるまでの、行動回数の最小値を求める問題。 手で遊べるビューアーで5個中2個のケースを解き、解答を埋め込んだコードを提出しました。
他
AC者が多かったG問題あたりを読んでいましたが何もわかりませんでした。
感想
毎年楽しいXmas Contestですが、今年はここ数年の出題傾向と異なる問題が並んでいたように思えます。 そのおかげか、これまでにない高い順位を取ることができました。
コンテスト中に考えられていませんでしたが、Project Eulerの知見が役立つ問題があったそうなので、Project Eulerの問題を埋めようと思いました。