北大・日立新概念コンピューティングコンテスト2018

ということで、初めてマラソンに参加しました。
この記事では、自分が最終的に行ったことと、時系列順に行ったことの簡単な列挙をしていこうと思います。

問題
最終的に行ったこと
- 変数がすべて1のケースの得点を狙う方法
- 厳密解を作成する方法
感想
追記(おまけ)
3/19追記

問題

リンクはこちら
基本的には同じ問題になります。制約が違う部分だけピックアップすると、
A:

3 <= N <= 50
1 <= K <= 50
0 <= d_i <= N

3 <= N <= 300
1 <= K <= 1000
0 <= d_i <= min(N,6)

3 <= N <= 10
1 <= K <= 2^N
0 <= d_i <= 6

といった具合です。
実際、ランキングを見てもわかるように、この部分が違うだけでかなり得点の取りやすさが異なります。

最終的に行ったこと

提出コード(C)
基本的にはA~Cでやっていることは同じです。ただ、一部分岐条件を問題によって切り替えています。
やることは主に2つです。1つめは、Twitter等で公開されていた、「変数がすべて1」のケースの得点のみを狙い、極限まで項数等を削る方法で、2つめが、厳密解を効率よく作成し、両方のケースで高得点を狙う方法です。

変数がすべて1のケースの得点を狙う方法

こちらは、以下のツイートの方法とほぼ同じです。

https://twitter.com/arimasenu/status/1099583866614931456

手順としては、次の通りです。

定数項および1次の項について、係数をそのまま割り振る
正負の項をまとめられるものについてはまとめる
$k_{1}ab - k_{2}abc$ という項が存在していた場合、( $k$ は係数です)
$k_{1}ab(1-c) - (k_{2}-k_{1})abc$
と $k_{1}$ で項をまとめることができます( $k_{1} \leqq k_{2}$ の場合です、逆でもやることはほぼ同じです)。そして、まとめた後の左側の項は、 $(1-c)$ という部分が負になることはありえない上、変数すべてが1のケースでこの項が0になるため、消去しても問題ありません。
よって、残った $(k_{1}-k_{2})abc$ という項についてのみ今後考慮していけばよいことになります。このようにして、どんどん項数を減らしていきます。
係数が負の項について、以下のように係数を割り振る
$-kabc$ という項があったとすると、こんな感じです。
$2k -ka - kb - kc$
つまりは、定数項に係数×(項数-1)を-1倍したもの、そしてそれぞれの変数に係数をそのまま割り振る、という形です。
この操作を行うことで、 $abc$ 全てが1であったときのみちょうど-kぴったりになり、それ以外の場合はそれを下回ることがありません。
係数が正の項について、係数を割り振る
$kabc$ という項があったときに、 $a,b,c$ の項に、うまく係数を割り振っていきます。この際、それぞれの項ができるだけ0に近づくように割り振りたいので、自分は山登り法を用いて調べることにしました。
まず、それぞれの一次の項に均等に係数を割り振ります。その後、それぞれの係数を移動することにより、よりスコアが高くなるような場所がないかを探していきます。
係数が正の項が存在していたら、定数項にまとめる
採点のうちの片方、ランダムケースでの得点を完全に捨てているため、捨てられる項は捨てていきます。
負の係数の最大値を調整する
例えば、 $-ka$ という項が存在していた場合、新規変数を利用して、 $- \frac{ka}{2} - \frac{kaw}{2}$
とした方が得点が伸びるパターンがあります。
係数の絶対値の最大値を $X$ とし、それを超える係数 $k$ が存在していたら $X$ と $k-X$ に分ける、ということを繰り返していきます( $k-X$ がそれでもなお $X$ を超えていたら、新規変数をもう一つ作成していきます)。
あとはこれを全ての項に対して行います。ただし、新規変数は共有して問題ないので、 $(k-1)/X$ の最大値が、新規変数の個数になります。
そして、最もスコアが高くなるように $X$ を選択したいのですが、(おおよそ)凸関数になっているので、三分探索である程度範囲を絞ってから、残った範囲をすべて調べ、スコアが最大となる $X$ を見つけます。

ということで以上が方法の1つめになります。この方法は、複雑な式、つまり項数が多いものに対して適用します。

厳密解を作成する方法

まず、厳密解を作成する方法はいくつか存在します。
notさんという方のブログを見ていただければ、論文に載っている厳密解の作成方法が書いてあるのでそちらをご覧ください。

新概念コン2018 論文まとめ - notブログ

おそらく自分の解法はこのブログの一番最初に載っているものが近いかと思います(この論文だけよく知らないのでなんとも言えませんが…違っていたり、そもそもこの方法が世に出回っていたらごめんなさい)。
厳密解の作成方法ですが、次数が0~2の場合はそのまま、そして係数が負の場合は、上のブログに載っている方法を利用します(ただし、すこし手を加えているので、後で説明します)。

係数が正の3次以上の項についての厳密解の作成

まずは、次数が3のものについて考えます。係数は最後にかけるだけでよいので省略します。
$abc$ という項があったとします。ここに、新規変数 $w$ を加えると、次のように表現できます。

$ab + w(-a-b+c+1)$

$a,b,c,w$ それぞれに0と1をあてはめてみると、これが $abc$ を表現できていることがわかります。
では、4次以上の場合はどのようにすればよいのでしょうか。
$abcd...$ という項が存在した場合、 $cd...$ の部分をまとめて1つの変数 $u$ と表現できれば、上の3次のケースに帰着させることができます。
ということで、まずは2次の項 $cd$ を、 $u$ と置き換えることができないかを調べればいいことになります(項が増えても、あらたに置き換えた変数と、もう1つの変数に対して同じ方法を適用していけば、最終的に1つの変数になります)
ということで結果は以下のような形になります。

$cd + u(-c-d+1)$

$(c,d) = (0,1) or (1,0)$ の際に $u$ の中身が0になるから動作するかどうかわからないじゃないか、と思うかもしれませんが、その場合でも $u=0$ が最適になります。
なぜならば、仮に $u=1$ とすると、元々の項 $abcd$ について考えてみると、 $(a,b)=(1,1)$ の際に $(a,b,u) = (1,1,1)$ となり、 $abu$ の項の係数が加算されてしまいます。現在、係数は正のパターンのみに限定しているので、 $(a,b,u) = (1,1,0)$ とした方が、 $abu$ の項の係数が加算されずに済むため、 $u=0$ が最適となるからです。
ということで、上の式を利用すると、 $u$ という変数が、新しく $cd$ を表す変数になりました。ので、 $abcd...$ という項ではなく、 $abu...$ という項を表現する問題に帰着できます。
これを繰り返し、3次になった時に、先ほどの公式に当てはめれば、厳密に $abcd...$ を表現できたことになります。
この方法の良い点は、項数が増えすぎない、という点だと思っています。
例えば、 $abc$ と $abd$ が存在した場合、
$2ab + w(-2a-2b+c+d+2)$
とやると、2つの項をいっぺんに表現できます。
また、 $abef$ という項と $cdef$ という項の二つが存在した場合、
まず、 $abef$ の $ef$ について、
$ef + u(-e-f+1)$
と変形をしてあげてから、
$ab + w(-a-b+u+1)$
としてあげることで、 $abef$ を表現できますが、
$ab + w(-a-b+u+1) + cd + x(-c-d+u+1) + 2ef + u(-2e-2f+2)$
としてあげると、 $abef$ と $cdef$ の、 $ef$ の部分が $u$ 一つで表現できます。
それだけでなく、
上の式における $w$ の部分そのものも、実は $ab$ を表す項になっていて、
具体的には、 $abc$ という項と、 $abde$ という項が存在した場合、
$ab + w(-a-b+c+1)$
で $abc$ を表現でき、
$de + x(-d-e+w+1) + ab + w(-a-b+1)$
で $abde$ を表現できます。まとめて、
$2ab + de + w(-2a-2b+c+2) + x(-d-e+w+1)$
としてあげると、これだけで2つの項を表現してあげることができました。
あとは、どの2次変数に対して新規変数を作成するか、の最適解を探せばよく、今回はこちらは焼きなまし法と山登り法(焼きなまし法の条件がうまくかみ合った問題については焼きなまし法を使いました)で探すことにしました。

係数が負の項についての厳密解の作成

こちらは、基本的には上で紹介したnotさんのブログにも書かれている、論文の方針と同じになります。
$-kabc$ という項を表現するには、
$kw(-a-b-c+2)$
とすればよいです。
新規変数 $w$ を1つ用意し、それぞれの変数と $w$ からなる二次の項にはそのまま $-k$ を、そして $w$ のみからなる一次の項には、 $k \times (変数の個数-1)$ を割り振ってあげればよいです。
ここで、 $-k$ が大きい場合、 $w$ のみからなる項の係数が大きくなってしまいます。
そこで、 $w,u$ という二つの変数を用意し、 $X$ という基準を設けて、 $k$ が $X$ より大きかった場合に
$Xw(-a-b-c+2) + (k-X)w(-a-b-c+2)$
のように分けてあげることで、得点を伸ばせることがあります。
厳密解でない方法の、負の係数に対する処理とほぼ同じものになります。なので、これも三分探索をして、最もスコアが上がる $X$ について調べてあげます。

その他細かい手法

$-kabc$ という項が存在して、
$-kw(-a-b-c+2)$ という項を作成したときに、
$jabcd$ (ただし $j \leqq k$ )という項を埋め込むことができます。
$-kw(-a-b-c+2)+jwd$
としてやると、1つの項のみで、4次の項を1つ作成できたことになるのでお得です。
今回は、焼きなまし法等でじっくり時間を費やしたい(~~実装が難しくて面倒くさい~~)ので、一部の項のみ、これを適用しました。具体的には、負の係数がある項の変数と、それらの変数より大きい番号の変数1つからなる正の項のみに絞りました。
具体例を出すと、 $-kabc$ という項が存在したら、 $jabcd$ や $jabce$ のうちのどれか1つが対象になります。
正の係数に対する負が存在するかどうかは、負の係数の項を辞書順ソートしておくだけで、二分探索で調べることができるので、これなら時間がそこまでかかりません。

ということで、記載漏れがなければこれが自分の解法のすべてになります。
あとは、ランダムケースを捨て、全てが1の場合の得点を稼ぐ方法を項数が多いものに対して、厳密解を作成する方法を項数が少ないものに大して行えばよいです。

ということで、最終的な順位はわかりませんが、15個のテストケースに対する得点は次のようになりました。
f:id:emtubasa:20190227225538p:plain

感想

今回初参加だったのですが、最初のマラソンで2週間のものに出場するのはやめましょう。
自分は、できるとこまでとことんやる性格(自称)なので、ほぼ2週間、隙あらばマラソンのことを考えていたため、他の作業が何もできませんでした…。毎日夜遅くまで考えていたため、特に得点が伸びない時期は明らかに体調が悪くなり、親や友人に心配されてしまいましたｗ
ただ、その分得点がぐんと伸びたときはとても面白いです。普段の競プロで高難易度を解いたり高パフォーマンスを出すのとは別の気持ちよさがありました。
あとは、競プロとは違って、普段強い方々といい勝負ができる可能性があって楽しかったです(でもやっぱり強い方々はマラソンでも強いのですが…)。
提出欄を見ればわかるように、上位の方々は基本提出回数が少ないので、わずかな思考時間であの点数を出していると考えると、いかにすごいかがわかると思います。
今回のマラソンでだいたいどんな感じかわかったので、次にマラソン出る際は、とりあえず数時間のものに出場してみようと思います…ｗ
ずっと同じことを考えて詰まってしまってもあまりよくないので、思考時間を少なくしてリフレッシュするのも大事ですし、それこそ体調が悪くなってしまっては元も子もありません。このあたりも調整しつつ頑張ってみたいです！(この性格があまり向いていないのでしょうか…ｗ)

追記(おまけ)

#HokudaiHitachiProcon2018というハッシュタグを見ればわかるのですが、嘘を混ぜ込んだ解法がほとんどっぽいですね…！！
それでも、上位勢は論理的な嘘(?)というか、他の出場者とは一味違う実装をしているっぽいので、やはり差がくっきりと出ているように見えます。
RE、WAを吐かずに入賞することを期待して数日間待っていようと思います！

3/19追記

僕頑張った pic.twitter.com/IKhTJcU0vJ
— ツバサ (@emtsu_ba) 2019年3月19日

グッズが届きましたー！うれしいですね

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。