12/24に行われていたXmas Contest 2016の昼の部に参加した。
参加しようとしてたら、ちゃっく(@chakku_000)にチーム組みを誘われたので、ロ技研部室に集まって参加した。
xmascon16noon.contest.atcoder.jp
このコンテストの結果は249点で21位だった。
ちゃっくはA問題、I問題を担当して、自分はB問題、E問題、J問題を担当してた。
コンテスト中の流れ
コンテスト開始後20分くらいに部室に着いたらちゃっくがA問題を解いてたのでB問題に手を付けた。
B問題
B問題は深さ11の完全二分木を格子点に埋め込む問題。
いろいろ考えて以下のように、三角形で再帰する感じで実装したが、WAになった。 (左の図がf(k) (深さkの完全二分木が収まる空間), 右の図が全体)
http://xmascon16noon.contest.atcoder.jp/submissions/1037861
問題をよく読むと、格子天上にある頂点間の辺の上では他の格子点が存在してはいけないことに気付く。
この実装では(x, y)から(x+a, y+a)みたいな感じにしてたのが悪かったので(x+a+1, x+a)みたいな感じにずらしたら通った(24点)
http://xmascon16noon.contest.atcoder.jp/submissions/1037931
B問題はこれ以上取れる気がしなかったので切り上げた。B問題を考えている間にちゃっくがA問題で75点をとってた。
E問題
次に、順位表の上では多く100点が出てたE問題を見てみる。
最初は200個のテストケースは同じ30匹のうなぎだと思って考えてたら、それぞれ独立であることに気付いて時間を無駄にしてた。
その後、
- 一番多い回答を正答と仮定
- その正答が一番多いうなぎから順に10匹ずつ1,2,3のタイプに分ける
- タイプ1とタイプ2の回答を考慮して正答を計算する
という流れを実装した。
最初はタイプ1は2、タイプ2は1の重みで正答を計算したらWAだった。
http://xmascon16noon.contest.atcoder.jp/submissions/1038350
ここからさらに、
- 正答と仮定した回答が全体の約2/5以上を占めているもののみをタイプ計算に使う
- タイプ1の重みを大きくする(2 -> 4)
ということをしたら通った (100点)
http://xmascon16noon.contest.atcoder.jp/submissions/1038388
J問題
その時、残り一時間くらいだった。次はJ問題が良さそうだと思ってJ問題に手を付けた。
J問題はこのコンテストのD,E,F,G,H,J問題のテストケースとして出力できるものを出力する問題だった。
部分点として、D,E,F,G,H,J問題のうち多くの問題で使えるテストケース(整数列)を出力するのはできそうだったので取りに行った。
解法としては、
- D,E,F,G,H,J問題すべてを満たすテストケースが存在することを仮定
- ランダムな長さ(2~20)で1,2,3からなるランダムな整数列を出力し、各問題(D,F,G,H)の制約を満たすかをチェック
- 満たした場合にE問題に合わせて30*50*200の長さの整数列になるように1を追加
みたいな感じのことを書いたら部分点が取れた (50点)
http://xmascon16noon.contest.atcoder.jp/submissions/1038731
この時点で残り5分だったので、ここで終了。ちゃっくはA問題のあと、I問題を解いてて実装がつらそうな感じだった。
今回、文章読めてなくてハマったりしたのは反省。
