12/7日のyukicoderのアドベントカレンダーコンテストで出題しました．初めての作問です．
まず解説を書き，その後作問するときにやったこととこの問題の背景について書きます．
解説
コンテストサイトの方にも簡単な解説がありますが，もうちょっと丁寧な解説を書こうと思います．
まず，スピンの当てはめ方\(2^N\)通りを全探索するのは\(N \leq 25\)くらいまでならいけますがそれ以上は厳しいです．スピンが\(-1\)になる電子の数を決めても，エネルギーの値が決まるわけではないので，スピンが\(-1\)になる数を決めるという方針も難しそうです．
ここで，電子のスピンではなくて，隣り合う電子のスピンの関係に着目したらどうでしょう．スピンが逆向きになっている場所と，同じ向きになっている場所の数を決めたら答えは定まるでしょうか．これは定まります．
向きが逆になっているペアの個数を\(k\)個とすると，向きが同じところは\(N - k\)個となります．向きが逆になっているところでは\(s_i s_{i+1} = -1\)，同じところでは\(s_i s_{i+1} = 1\)となります．よってエネルギーは\(-(-1 \times k + 1 \times (N - k)) = -(N - 2k)\)となります．
ここで，\(k\)は1以上\(N\)以下なら何にしてもいいというわけではありません．1番目から\(N\)番目までに奇数回向きが変わったとすると，1番目と\(N\)番目のスピンは逆向きなので，合計で偶数回逆向きになったことになります．1番目から\(N\)番目までに偶数回向きが変わったとすると，1番目と\(N\)番目のスピンは同じ向きなので，合計で偶数回逆向きになったことになります．結局，\(k\)は偶数である必要があります．
エネルギーが\(-(N - 2k)\)になるように選ぶ方法の数を考えます．まず向きが逆になっているところを選ぶ方法の数が\(\binom{N}{k}\)あります．しかしこれだけではスピンの配置が定まらないので，電子を一つ選んでそのスピンを固定してあげる必要があります．その電子のスピンの選び方は2通りあるので，結局\(2\binom{N}{k}\)となります．
以上より，求める解は
\[
\sum_{k = 0, \text{偶数}}^N 2\binom{N}{k} 2^{|N - 2k|}
\]
となります．2の累乗と，二項係数を求めるための階乗を前計算することでこの問題を\(O(N)\)で解くことができました．
問題の背景
これは他分野の問題から着想を得て競プロの問題っぽく改変した感じの問題です．
大学で創造工学研修という授業があって，そこで僕は量子アニーリング（量子力学を使って最適化問題を解くよくわからないやつ）入門みたいなことをしています．量子アニーリングとかをやる前に統計力学を軽く勉強する必要があって，その時に教授に出された問題が以下のようなものです．
円周上に\(N\)個の電子があって，スピン\(\sigma_i\)をもっている．エネルギー\(E\)は次のように計算できる．
\[
E = -J\sum_{i=1}^N \sigma_i \sigma_{i+1}
\]
分配関数\(Z\)を次のように定義する．
\[
Z = \sum_{\text{スピンの配置}} e^{-\beta E}
\]
それでここから\(Z\)を使ってエネルギーの期待値を計算したりするんですが，とりあえず\(Z\)を求めることにしました．
これ競プロの問題っぽいな～と思いながら解いていました．最初は電子のスピンを決める方針でずっとやっていましたが，全然うまく行きませんでした．すると天啓が降ってきて，隣り合う電子の向きの関係に着目すれば解けると分かり，線形で計算できるところまで落としました．教授は閉じた式で表してほしかったらしいんですが，僕が「これコンピュータで余裕で解けるんでよくないですか？」といって妥協しました．僕がプログラムに落としている間に教授はホワイトボードでなんか変な計算をして閉じた式で表していました．まじで意味が分からなかったんですが，なんか対角化したりトレースの計算したりするらしいです．
ちなみにこれは1次元周期境界イジングモデルとかいうやつらしいです．
これ，競プロの問題としてとても面白い問題だと思ったので，帰ってから競プロ向けにちょっといじったらいい感じになったので，今回アドベントカレンダーコンに出してみました．
作問の過程
この問題を作ったときに問題概要と想定解をマークダウンで書き残しておきました．
アドベントカレンダーコンテストなるものがあると知り，writerデビューのいい機会だと思って思い切って参加してみようと思いました．
yukicoderのページで問題やら制約やらを書きます．テストケースに関しては，自分で適当に思いついた数字を入力にしてました．この問題は入力が整数1個だけなので，非常にテストケースが作りやすい．途中から自分で考えるのがめんどくさくなったのでランダムに生成しました．
writer解は想定解の数式をそのまま打ち込んで，あとは小さいケースで\(O(2^N)\)の愚直と比較して確認しました．
testerはICPCチームメイトのrenjyakuさんとmugen1337さんにお願いしました．問題文とか解説とかしっかりチェックしてくれてとても助かりました．ありがとうございます
コンテスト中
問題公開から10分くらいたって，続々と提出が来ます．開始前は自作問題自明に見える病にかかっていたので問題が簡単すぎることを危惧していたのですが，そんなことはなかったようです．強い人がWAを出すたびに安心しました（最悪）．AC提出を見るとどれも想定解と全く同じような計算をしていました．WA提出を見ると，正しい解と近いけど微妙に違う数式が書いてあり，それでサンプルは全部通っていました．たぶんNが奇数の時だけ正しい解を返すコードを書いていて，サンプルにNが偶数のケースがないので提出しているのだと思いました．サンプルに偶数のケースを入れていないのは特に意図してやったことではないのですが，思いがけず良い（悪い？）効果をもたらしました．
最後に
これからもおもしろい問題ができたら積極的にyukicoderに出してみたいと思います．いつかAtCoderのwriterもやってみたいなあ．
追記
絶対値なしバージョンは，上と同様の解法で解けますが，閉じた式で表すこともできます．Twitterでkobaさんに教えていただきました．
2\sum_{iは偶数} 2^{2i-n}C(n,i)が答えで、一般に\sum_{iは偶数} A(i)=\sum_i (A(i) + A(i)(-1)^i)/2が成立するので、2^{-n}\sum_i (4^iC(n,i) + (-4)^i C(n,i)) = 2^{-n}(5^n + (-3)^n)です
— koba (@kobae964) 2020年12月8日
非常に賢い...．\(\sum_{\text{偶数}} A_i = \sum \frac{A_i + A_i (-1)^i}{2}\)という式が一般に成り立つというのは汎用性が非常に高く他の問題でも使えそうです．とても面白いことを教えていただきました
