タイプ2の条件はひとまず無視して考える。
タイプ1のそれぞれの条件についてからに辺を張ったグラフを与えたとき、問われていることは「から入次数がの頂点を次々に消していくとき、最大で何個消せるか？」ということだった。この個数に消す順序は関係ないので、実際に自由に消していって確かめればよい。具体的には、入次数がの頂点をすべてキュー（あるいはスタック）に入れてBFS（あるいはDFS）をすればでできる。手順としては、キューから頂点を取り出したら、隣接頂点の入次数を1ずつ下げて、入次数がになったものをキューに入れればよい。あるいは、この制約ならBellman-Fordっぽく入次数が0の頂点の隣接頂点の入次数を下げる操作を周繰り返す、でもよさそう。()
タイプ2の条件については、
の2通りを調べれば十分で、後者はタイプ1と同じなので上の問題に帰着できている。タイプ2の条件は十分に少ないので、通りのグラフを調べればよい。。
Qiitaからこちらに転載した。AtCoderの環境の更新に合わせて、転載当時の内容から多少の変更を加えている。
表題の通り、競技プログラミングに参加しているLisperとこれから参加するかもしれないLisperのために、必要な情報を一通りまとめています。
AtCoderではCommon Lispが使えますし、CLで投稿できる大手コンテストサイトはCodeChefやyukicoder、CS Academyなど他にもいくつかあります。日本語の問題文があって運営の質が高くてコンテストが頻繁に開催されていて……というような点を考えていくと、競プロに興味を持った日本語圏のLisperにとってAtCoderは第一の選択肢といってよいでしょう。第二はyukicoderとCodeChefです。以下の解説は、特に断りがなければAtCoderを前提にしています。
本題ではありませんが、セクションを立てて言及しておくことにします。というのも、競技プログラミングに熱心なLisperはほぼ皆無に見えるからです。競プロに興味のある人の中にも、そもそもLispに向いているジャンルなのかどうか不透明に思う人がいるかもしれません。
端的に言うと、わたしのレベルではパフォーマンスの面でデメリットを感じたことはありません。より高レートの状況でどうなるかは知りえないことですが、悲観する材料は特に見つかっていません。終わり。
……でもよいのですが、いくつかのポイントに絞って説明してみます。
素早く・簡潔に・柔軟にDSLを生やすことにかけてはLispは今なお優れた言語であると言えるでしょう。競プロの文脈でもそれは役には立ちます。もっとも、そういったものは競プロにおけるパフォーマンスにさほど影響しないとも思います。競プロで大事なのは考察力です。
最良ではないが、悪くもないです。AtCoderにおける速さという観点で言語を雑に分類すると
で性能はおおむねA>B>Cということになりますが（あくまで雑な分類です）、LispはBの中で速いほう、くらいの位置づけです。状況にもよるので絶対的な比較は難しいですが、速度面では「Java/C#と同程度かわずかに有利」くらいの認識を持っています。そして、Java/C#専のまま強くなる人は特に珍しくもありませんから、スピードの問題はさほど心配しなくてよいです。
実情を言うと、ビギナーコンテストの問題では正しいロジック（＝最悪計算量が制約に適っているロジック）で書けていればTLE(Time Limit Exceeded)することはめったにありません。TLEするのは、最適化が足りないからではなく、計算量の考察がおかしいからと思ってほぼ間違いないです。ほとんどの場合、最適化のための基本的な宣言すら必要ないと思います。それ以上のレベルの問題でも、SBCLが遅くて通せないとか、あるいは最適化しても制限時間ぎりぎりになるという事態に陥ったことは一度もありません。そもそもAtCoderではJavaで通らない問題は出題されないそうなので、SBCLで通せないというケースは考えにくいです。
CS AcademyやHackerEarthなど、事前コンパイルなしで--scriptで実行されるサイトではその分の時間（おおむね50ms～200ms程度）が上乗せされますが、このような環境でも問題になることはまれです。
Common Lispの標準ライブラリは貧弱です。平衡二分木もなければ、優先度付きキューも両端キューもないし、それどころかただのキューすらないので、あらゆるデータ構造をいちいち用意しなければなりません。[1] 良い所もそれなりにはあって、多倍長整数が自然に扱えるのでオーバーフローの処理をちょっとくらいサボってもOKなのは悪くない点ですし、有理数や複素数も競プロでは活躍します。stringが単に文字の配列であるという時代遅れな仕様も、競プロではむしろ望ましいです。しかし、総合的に見てやや不十分なのは否めないでしょう。
もっとも、競プロerはどの言語を使っていてもけっきょくは自前実装のデータ構造を少しは用意することになるので、二分ヒープを自分で書くことくらいは誤差レベルとも言えます。ただ、自分でデータ構造を書く場合に、効率のために要素型で静的ディスパッチするようなコードを書くのが大変という別の問題はあります。CLにはパラメータ多相を自然に導入する方法の決定版がいまだにないので…… （競プロに限った話ではありませんが、ジェネリクスのデファクトがないのはCLのアキレス腱だと思っています。）
Common Lispは最大手のCodeforcesで使えませんし、もちろんTopCoderでも使えません。日本の競プロer御用達のAOJも対応していません。したがって、LisperはAtCoder、yukicoder、CodeChefを中心に利用し、Google Code Jamがあれば出て、足りなければCS Academy、HackerRankなどを使うことになります。それが不満ならC++やJavaを選んだほうがよいでしょう。ちなみにわたしはまあまあ不満です。
Lisperの数が極めて少ないため、参考にできるコードがありません。AtCoderで400点以上の問題だとLispの提出はゼロであることが多いです。 困ります。もちろん、根幹のロジックを理解するために読むのはなんの言語でもよいので、C++やPythonの提出コードを見ればよいです。しかし、他人のコードを読むのは、整理された間違えにくい書き方を学ぶためという側面が強いので、言語が同じであるほうが参考にしやすいのも確かです。
もっとも、この問題はあなたが参加すれば解消されるとも言えます。ぜひやってみませんか。
実践で生じるトラブルとその回避方法を挙げます。「いくつか」と題しましたが、今のところ重要なものは最初の１つだけです。また、入出力関係の話題はまとめて後のセクションで扱います。
SBCLのデフォルトのスタックサイズは2MBであり[2]、コールスタックがこのサイズを超えるとエラーになります。（末尾呼び出しはジャンプに変わるので安全と思ってよいです。）
2MBというサイズですが、目安としては105の深さで再帰すると確実にcontrol-stack-exhaustedする、104ならたぶんOK、くらいです。深さを見積もって無理そうなら再帰を使わなければ良いのですが、DFSなどを手動スタック+ループで書くのはやや面倒と感じる人も多いでしょう。幸運なことに、この問題については解決策が確立しています。スタックサイズを増やしたSBCLを子プロセスとして呼び出せばよいのです。ファイルの冒頭に次のフォームを置きましょう。
#-swank
(unless (member :child-sbcl *features*)
(quit
:recklessly-p t
:unix-status
(process-exit-code
(run-program *runtime-pathname*
`("--control-stack-size" "256MB"
"--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
"--eval" "(push :child-sbcl *features*)"
"--script" ,(namestring *load-pathname*))
:output t :error t :input t))))
こうすればスタックサイズの大きいSBCLが代わりに処理してくれます。
#-swankは必要ではありませんが、わたしはSLIMEでコーディングしているので、編集中にこのフォームが評価されないようにするために書いています。--scriptで実行する仕様でも、コンパイルしてから実行する仕様でも、どちらでも通るようにしています。ほとんどのコンテストサイトで使えます。forkを呼ぶことになるので、DMOJのようにシステムコールを制限しているジャッジでは使えないようです。
やや強引なハックではありますが、2年ほど使ってこの方法の欠陥らしきものは見つかっていません。数ms程度ロスしてわずかにメモリ消費が増えるだけですし、常に置いておいても特に問題ない程度のものです。
また、スタックサイズを書き換えてから新たにスレッドを作るという方法も考えられます:
(defun main () ...)
(setf (sb-alien:extern-alien "thread_control_stack_size" sb-kernel::os-vm-size-t)
(* 256 1024 1024))
(sb-thread:join-thread (sb-thread:make-thread #'main))
ただし、SBCLは起動後にスタックサイズを変更する機能を提供していないので「いちおう動く」だけではあります。最近のランタイムを眺めた限り、普通の使い方では壊れないだろうと思っていますが。（こちらもDMOJでは使えません。）
(declare (inline sort))しましょう。SBCLのsortはsb-ext:maybe-inlineなので、デフォルトではインライン化されません。[3] インライン化されないと、ベクタの要素型を考慮した静的ディスパッチがされないので、常識的なスピードが出ません。
ただ、SBCLのソートはベクタに対してはヒープソートなので、いずれにせよスピード重視ではないし、標準のソートは範囲指定ができないという問題もあります。[4] マージソートなりクイックソートなりを用意しておくのもよいかもしれません。
リストをsortする場合（マージソート）に関してはさらに(declare (inline sb-impl::stable-sort-list))が必要だったりします。（ソートが間に合うか不安なくらいに入力が大きいケースではリストで持たないほうがよいと思いますが。）
また、普段からSBCLのどの関数がどの場合にインライン化（インライン宣言やdefine-source-transformやdeftransformやdefine-vopによる変換）されるのか、型を考慮した最適化があるのかを気にしておきましょう。SLIME上なら、標準の関数に対してM-. slime-edit-definitionするとSBCLのソースにジャンプできます。
改行の扱いはコンテストによって異なるのですが、AtCoderのratedに出るだけならあまり気にする必要がないでしょう。あらゆるコンテストに出るなら、一般論としては以下のような指針があります。重要な順に
#\Linefeed限定と思わないほうがよいです。2番目については、CodeChefのようにCRLFが入っているかもしれないことを明言しているサイトもあります。SBCLのread-lineはCRLFをうまく扱えないので、場合によってはstring-trimなどをする必要があるかもしれません。（とはいえ、この辺は「ちゃんとした」コンテストになるほど気にする必要性が下がっていくので、わたしもあまり真剣に対処していません。CodeChefでも最近のratedで困ったことはないです。）
CodeChefではメモリは問題に関係なく4GBくらいまで使えるという情報がありますが、SBCLはなぜか--dynamic-space-size 48で起動されているのでそのままだと実用するのが厳しいです。上述のスタックサイズを増やすヘッダでヒープサイズも増やせます。（さすがにまずそうな仕様ですが、わたし以外のLisperを見たことがないので報告をさぼっています。）
double-float以上の精度が想定される問題はほとんど見ないですが、あれば役に立つことはよくあります。SBCLにはMPFRのモジュール（sb-mpfr）がありますが、AtCoderの環境ではrequireしてもlibmpfrが見つからなくて使えません。ジャッジ環境にlibmpfr自体は存在していて、requireの前に(sb-alien:load-shared-object "libmpfr.so.6")でロードするとよいです。自分が使っているヘッダの例はここにあります。
サイトによってSBCLのバージョンが異なるので、メモしておきます。該当のバージョンより上にある項目が注意点になります。重要な差異は特にないのですが、ジャッジのバージョンと近いものを使ったほうが細かいトラブルが起こりにくいです。Roswell等で切り替えるのがよいでしょう。
modの返り値が正数であると推論されないことがあります。うまくいかない場合はtheを使いましょう。version 1.5.7でたぶん解決。make-arrayで多次元配列を作る場合、element-typeの推論が正しくできないことがあります。sb-c:make-array-header*のderive-typeをコピペすれば解決しますが、そんなことをしなくても必要なら型を手打ちすればよいです。version 1.5.6で解決。*read-default-float-format*にrationalを指定できない。version 1.5.2で解決。
rationalが使えるのはSBCL独自の仕様ですが、便利なので載せていますmaphashが事前指定したサイズに対する。詳細はここに書きました。version 1.5.5で過去に到達した最大要素数に対するになりました。どちらの仕様でも、「maphashを何回も呼ぶけど合わせて」みたいな場合に本当にかどうか気を付けたほうがよいです。array-element-typeが定数伝搬しません。インライン関数の中で同じelement-typeの配列を作りたい場合等に困るかもしれません。array-element-typeのdeftransformをコピペすれば解決しますが、そんなことをしなくても必要なら型を手打ちすればよいです。version 1.5.0で解決。SBCLはかなり昔から安定しているので、処理系が落ちるようなバグはまず無いと思っていいです。私自身は、AtCoderでdynamic-extent絡みのバグを踏んだことが1回ある程度です。（詳細を忘れました）
大量の入出力をこなす場合（目安としては106文字くらいから）、全部(read)して一行ずつ書き出すような素朴すぎる方法を使うと無視できないロスになることがあります。このセクションでは効率をある程度考慮した方法を紹介します。しかし、ベストプラクティスと言えるような方法は特に確立していないので、以下のポイントを頭に入れつつ各自で好きなようにしましょう。
read-lineを高速化する（使用頻度: △）read-lineは遅いとよく言われます。遅い理由として、read-lineは呼び出すたびにコンシングするからという説明を見たことがありますが、わたしの知る限りでは、律速しているのはマルチバイト文字を考慮したread-charです。AtCoderでは（おそらく）ASCIIしか出ないので、バイト単位で読んでsimple-base-stringのバッファに読みだす関数が役に立つかもしれません。SBCLの標準IOはbivalentなので、read-byteが使えます:
(declaim (inline read-line-into))
(defun read-line-into (buffer-string &key (in *standard-input*) (term-char #\Space))
(declare (inline read-byte))
(loop for c of-type base-char =
#-swank (code-char (read-byte in nil #.(char-code #\Newline)))
#+swank (read-char in nil #\Newline)
for idx from 0
until (char= c #\Newline)
do (setf (char buffer-string idx) c)
finally (when (< idx (length buffer-string))
(setf (char buffer-string idx) term-char))
(return (values buffer-string idx))))
term-charは入力終了を表す文字として使います。例えば#\Spaceの場合、1 2 3という行を読むとbuffer-stringを"1 2 3 "で上書きするわけです。buffer-stringの長さがちょうど5なら"1 2 3"になります。read-charを使う必要があります。(declare (sb-kernel:ansi-stream in))を宣言するとさらによいかもしれません。上の関数はread-lineよりずっと速いですが、いちいちバッファを作るのが面倒であれば、サイズだけ指定してバッファは自動で用意するという方法もあるでしょう:
(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (term-char #\Space))
(let ((buffer (gensym))
(character (gensym))
(idx (gensym)))
`(let* ((,buffer (load-time-value (make-string ,buffer-size :element-type 'base-char))))
(declare (simple-base-string ,buffer)
(inline read-byte))
(loop for ,character of-type base-char =
,(if (member :swank *features*)
`(read-char ,in nil #\Newline) ; on SLIME
`(code-char (read-byte ,in nil #.(char-code #\Newline))))
for ,idx from 0
until (char= ,character #\Newline)
do (setf (schar ,buffer ,idx) ,character)
finally (when (< ,idx ,buffer-size)
(setf (schar ,buffer ,idx) ,term-char))
(return (values ,buffer ,idx))))))
fill-pointerでコントロールしたいところではあります。読み込み時だけarray-storage-vectorを使う、とかいろいろやり方は考えられますが、今のところわたしはあまり頑張っていません。read-lineとの比較ですが、105行以上のデータを読み込むなら200msくらいは得できるイメージです。最大で800msほど速くなるパターンを経験しています。
ただ、リードにしろパースにしろ、1文字ずつ読むならストリームから直接処理したほうが良くなりますし、read-sequenceなどを使う手もあるでしょう。以下にそのやり方も紹介しますが、read-lineや上の関数が役に立つこともよくあります。ストリングを介した行単位の処理は柔軟で、変則的な入力にも対応しやすいためです。
大量の整数を読み込んで処理する問題は頻繁に出ます。整数が個を超えたあたりからreadに掛かる時間が無視できなくなってきます。
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
(declare (inline read-byte)
#-swank (sb-kernel:ansi-stream in))
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
#+swank (char-code (read-char in nil #\Nul))
#-swank (read-byte in nil 0))))
(let* ((minus nil)
(result (loop (let ((byte (%read-byte)))
(cond ((<= 48 byte 57)
(return (- byte 48)))
((zerop byte) ; #\Nul
(error "Read EOF or #\Nul."))
((= byte #.(char-code #\-))
(setq minus t)))))))
(declare ((integer 0 #.most-positive-fixnum) result))
(loop
(let* ((byte (%read-byte)))
(if (<= 48 byte 57)
(setq result (+ (- byte 48) (the (integer 0 #.(floor most-positive-fixnum 10)) (* result 10))))
(return (if minus (- result) result))))))))
(defun read-bignum (&optional (in *standard-input*))
(declare (inline read-byte)
#-swank (sb-kernel:ansi-stream in))
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
#+swank (char-code (read-char in nil #\Nul))
#-swank (read-byte in nil 0))))
(let* ((minusp nil)
(result (loop (let ((byte (%read-byte)))
(cond ((<= 48 byte 57)
(return (- byte 48)))
((zerop byte) ; #\Nul
(error "Read EOF or #\Nul."))
((= byte #.(char-code #\-))
(setq minusp t))))))
(mid-result 0)
(index-mod18 0))
(declare (fixnum mid-result)
((integer 0 19) index-mod18)
(integer result))
(loop
(when (= index-mod18 18)
(setq result (+ mid-result (* result #.(expt 10 18))))
(setq mid-result 0)
(setq index-mod18 0))
(let ((byte (%read-byte)))
(unless (<= 48 byte 57) (return))
(setq mid-result (+ (- byte 48) (* 10 (the (mod #.(expt 10 17)) mid-result))))
(incf index-mod18)))
(setq result (+ mid-result (* result (expt 10 index-mod18))))
(if minusp (- result) result))))
read-fixnumは、読み込む整数がfixnum(=(signed-byte 63))とわかっている場合のreadの代替であり、わたし自身、ここに挙げた関数の中でもっとも頻繁に使っています。
read-bignumも用意してありますが、ほとんど使ったことがありません。AtCoderでは多倍長整数をそのまま扱えないと厳しい問題はそうそう出ないと思いますし、出ても1つ読むだけならreadが十分速いです。[5] どのくらい大きな整数を扱えるかは感覚で覚えるしかありませんが、目安としては10100000を読むのに200ms掛かると覚えておくとよいです。
string-output-streamにためる（使用頻度: ○）出力データが大量にある場合、一行ずつ*standard-output*に出していくとロスが大きくなることがあります。そういう時はstring-output-streamを使いましょう:
(let ((out (make-string-output-stream :element-type 'base-char)))
(dotimes (i n)
(princ data out)
(terpri out))
(write-string (get-output-stream-string out)))
これは場合によってはかなり効きます。マクロ化したければ次のような感じでしょうか。（わたし自身はマクロではなくスニペットで解決しています。）
(defmacro with-buffered-stdout (&body body)
(let ((out (gensym)))
`(let ((,out (make-string-output-stream :element-type 'base-char)))
(let ((*standard-output* ,out))
,@body)
(write-string (get-output-stream-string ,out)))))
ただし、メモリ制限が厳しい場合は、string-output-streamに全部ためるとMLE(Memory Limit Exceeded)になってしまうことがあります。AtCoderの最近のコンテストでは256MB～1GB以外の制約を見たことがないので、この点を気にする必要はないと思いますが、過去問を解く際には問題になることがあるかもしれません。
SBCLのformatの~Fや~$は遅いです。特に、~,5Fや~5$のように小数点以下の桁数を指定した場合、出力だけで時間切れするレベルのボトルネックになったりします。
単純な解決策としてはwriteやprincをそのまま使うことが挙げられます。この場合、出力に指数表記が混じることになりますが、AtCoderは基本的には指数表記で回答しても問題なかったはずです。（初期の問題に通らないものがあった気もします。） ただし、指数の記号はもちろんeでないといけません。実数を扱う問題では、精度を考慮するとdouble-floatが必要になることも多いのですが、その場合は*read-default-float-format*を変更する必要があります:
CL-USER> (write 1.4f10)
1.4e10
CL-USER> (write 1.4d10)
1.4d10
CL-USER> (let ((*read-default-float-format* 'double-float))
(write 1.4d10))
1.4e10
なお、わたし自身はdouble-floatを通常の表記で高速に出力する関数も用意してはいます。AtCoder以外のサイトだと、writeでも遅すぎたり、あるいは出力桁数を制限しないと出力サイズが上限を上回ってしまったりという経験があります。
小数を大量に入力する問題は意外にもまれです。SBCLのリーダーをいじったものをいちおう用意していますが、あまり試していません。
なお、readで読む場合、デフォルトではsingle-floatでパースされるので意図せず精度が落ちてしまう可能性はあります。これもやはり*read-default-float-format*を変更すればよいです。
「浮動小数点数の誤差の扱いが面倒だが有理数を使えば解決」という問題はたまにあります。しかし、入力も小数の場合は、readしてからrationalizeするとそもそもreadの時点で誤差が入るので、それについて考える必要が生まれます。SBCL 1.5.2以降であれば*read-default-float-format*にrationalが指定できるので、これを使うと何も考えなくてすむかもしれません。
ただし、SBCLではただのキューで良ければsb-queueが十分使えます。これはスレッドセーフなキューなので競プロ用途ではやや「リッチすぎる」わけですが、パフォーマンス上の問題は特にないことを確認しています。また、src/code/target-bst.lisp（バージョン1.5.0より前）かsrc/code/avltree.lisp（1.5.0以降）に平衡二分木が一応あったり、src/code/timer.lispに二分ヒープがあったりしますが、これらはユーザーが使うことを意図したものではないでしょうし、汎用的に作られてはいません。 ↩︎
AtCoder上のSBCLについては、コードテストで(print (sb-alien:extern-alien "thread_control_stack_size" sb-kernel::os-vm-size-t))を送れば確認できます。 ↩︎
SBCLのマニュアルにはなぜか載っていませんがCMUCLのマニュアルにはあります。標準の関数のうち、SBCLでmaybe-inlineなのはacons, both-case-p, digit-char-p, float-precision, get-properties, getf, intersection, keywordp, lower-case-p, nintersection, nset-difference, nset-exclusive-or, nsublis, nsubst, nsubst-if, nsubst-if-not, nthcdr, nunion, remprop, set-difference, set-exclusive-or, sort, stable-sort, sublis, subsetp, subst, subst-if, subst-if-not, tailp, tree-equal, union, upper-case-pです。ソート以外で覚えておきたいのはdigit-char-pでしょうか。また、maybe-inlineと似ていますが、inline宣言されたあとnotinline宣言されている関数としてunread-char, listen, read-char, read-byteがあり、これらも明示すればインライン化されます。 ↩︎
一応、displaceしたベクタをソートして副作用を利用するという方法はあります。おそらく挙動は未定義ですし、simpleでなくなるので遅いですが、SBCLでは意図通りに動くはずです。 ↩︎
いっぽう、SBCLのparse-integerは多倍長整数をパースするのが遅いので注意。10100000を読むのに2秒以上かかります。 ↩︎
文字の数があわないなどの自明ケースは先に考慮しておく。
実際にtitechという文字列をいくつか作りかけながら、文字列を先頭から走査していくことを考える。たとえばtitという文字列が2つできているときに次がeだったら、どちらに追加しても区別できない。したがって、長さの列を個持っているとしてと初期化しておけばよく、eを見たらを1減らしてを1増やすという感じで遷移すればよい。ほかの文字についてもだいたい同じで、最後まで走査できたらYesということになる……のだが、問題は文字tで、との二通りに追加できる。これはDFSで全探索すればよさそう。
しかし、計算量がどうなるかわからなくてしばらく逡巡していた。自明な評価から順に
titechは最大で16個作れてこの時tは32個だからDFSの末端の数は以下。逆から貪欲でいいらしい。なんと……
まずは与えられた数列の美しさを求める方法を考える。数列に桁目がの数が個含まれているとき、個から奇数個選べば残りの数をどう選んでもxorの桁目がになる。つまり、桁目だけに限ってxorの総和を取ると、ならが
個足されることになる。すなわち、桁目が立っている数がの中に1つでもあれば、桁目の総和はであり、ひとつもなければである。したがって、全体の総和はbitwise orを使って
と表すことができる。これがの美しさである。
次に 長さで美しさの数列の数、を求める方法を考える。上の式を見ると、が与えられたときにの立っているビットを考えればよいことがわかる。つまり、の桁目がなら、個の数のうちの少なくともつの数の桁目がであればよく、桁目に限定した個の数の選び方は通りとなる。いっぽう、の桁目がなら、個の数の対応する桁目はすべてでなければならないので、選び方は通りである。したがって、整数の立っているビットの総数をで表すとき、
と書ける。
さて、解くべき問題はを満たす最小のを求めるというものだった。上の式を見ると、を満たす最小のが求まれば、個のを並べて回左シフトしたものが求める最小のということになる。これで離散対数問題に帰着できた。
ただし、上の式からわかるように、の時は美しさの数列がないので、に対しては常にが答えということになる。（もちろんなら）。
ひたすらゲームの性質を観察する。
先手の手の列を, 後手の手の列をとする。
まず、先手は一手目より小さいカードを出せない。つまり、先手の一手目は必ず最小のカードでなければならない。
後手も先手の一手目以下のカードは出せない。
先手の有効な手の列でとなっている部分があったら、入れ替えが可能であることを示す。後手はと等しいカードをターン目までに出したはずだが、ちょうどターン目には出せないので、ターン目より前に出しているはず。したがって、の入れ替えと同時にとも入れ替えれば有効な列のままである。
以上より、先手の手の列としてはカードを昇順にソートしたものだけ調べればよい。これに対する後手の手の列も昇順としてよいことを示す。となるがあるとき、入れ替えてもそれぞれのとの大小関係は維持される。あとはを先に出すことによってが出せなくなる場合があるか検討する必要があるが、その場合はが成り立つので、となって矛盾。
したがって、先手、後手のカードをそれぞれ昇順にソートして、有効な手の列になっているかどうか確かめればよい。
盤面から消えたカードはbeatしたorされたものだけなので、同じ数字が書かれたカードが枚より多くあると引き分けることはできない。
いっぽう、以下のテクニックを使えば先手と後手のカードをだいたい任意に入れ替えることが可能なので、同じカードが枚以下の場合はだいたいYesということになる。
先手と後手は1と3で出したカードを交換したことになる。このあとは後手提出 → 先手提出 → 後手giveup→先手提出 → 後手提出 → 先手giveup→……を繰り返しながら、カードを2枚ずつ捨てていけばよい。
しかし、コーナーケースがいくつかある:
初手giveupができないルールと、カードがなくなった瞬間に終了するルールのおかげでだいぶ面倒になっている。
区間に登場する同じ数をまとめてそれぞれ個数を数える。grundy数を考えると、ゲームの勝敗は個数の組み合わせだけで決まっていることがわかる。つまり、現れる個数を個とした時に、その総xor で勝敗が決まっている。先手が初手でを減らしてにすることができればxorがゼロになって、先手必勝の盤面になる。したがって、先手が勝てる初手の総数は
と計算できる。ただし、石を増やしたりパスしたりすることはできないのでの項はとする。これを素朴に計算すれば部分点が取れる。
満点解法について。個数が同じもの、つまりとなるようなものはまとめて計算できることに注目する。つまり、個数が個あると考えるとき、を係数として
と計算できる。登場する個数が種類あるとして、がもっとも大きくなるのは回登場する数が1種類、回登場する数が1種類、...、回登場する数が1種類あるときで、このとき
なので、と評価できる。これなら全体の計算量はとなって間に合うはず。
さて、問題は区間に登場する数をどのように数えるかだが、Mo's algorithmでできるのでそうした。
というデータを持ちながら伸縮すればで遷移できるので、個のクエリに対しては となる。つまり、計算量をまとめると 。
ただ、とをハッシュテーブルで持つと定数倍が重すぎて間に合わなかった。に関しては、登場する数を座標圧縮すれば長さ以下の配列で持てる。しかし、は で走査する必要があるので、素朴に配列を使うと方針が破綻する。これは双方向リストっぽい持ち方で解決した。つまり、 長さの配列で持った上で、
という風に前後のインデックスを保持しておく。のある項を増やしたり減らしたりするときにはとを適切に変更する。こうすると、先頭からをたどればの正の要素だけを走査できるようになる。これで間に合った。
SBCLについて。これでも11秒くらい掛かって不思議に思っていたのだが、原因はコード変換に失敗していたことだった。sb-c:define-source-transformはdefine-compiler-macroと違ってコンパイル時実行ではないので、eval-whenで括らないとコンパイル時には存在しないことになってしまう。直したら余裕で間に合った。AtCoderだとスクリプト実行だからこの問題が起きなくて気づけなかった。
egg-free DAGが作れるためには明らかにchordal graphでないといけない。逆にchordal graphなら、perfect elimination orderingにしたがってDAGを作れば勝手にegg-freeになる。
以下は必要なアルゴリズムについてのメモ。
https://www.cse.iitd.ac.in/~naveen/courses/CSL851/uwaterloo.pdf に疑似コードが載っている。ハッシュテーブルを使えば期待線形時間の実装は難しくない。できればハッシュテーブルなしで線形にしたかったけれど、やり方を思いつかなかった。
chordal graphに対してPEOを求めるアルゴリズム。正確には、グラフに対してなんらかの頂点の順列を出力し、入力がchordal graphであればそれが必ずPEOになっているアルゴリズム。結果を上の判定アルゴリズムで調べれば、chordal graphかどうかも同時にわかることになる。
An introduction to chordal graphs and clique treesの疑似コードより:
V := {0, 1, ..., N-1}
L = {}
result = []
for i from N-1 downto 0:
find v in V s.t. |adj(v) ⋂ L|が最大
result[i] = v
L := L + {v}
V := V - {v}
これを実装するのがけっこう難しかった。がついていいなら優先度変更可能なヒープを使うのがいちばん簡単？
V := 頂点0, 1, ..., N-1を優先度0として挿入したヒープ
L = {}
result = []
for i from N-1 downto 0:
v := V.pop()
result[i] = v
for w in vの隣接頂点:
wがLに含まれていればwの優先度を+1する
しかし、優先度の範囲がなので、頑張れば配列の操作だけで線形にできる……はずなのだが、簡潔な方法が思いつかなかった。けっきょく、双方向リストを二次元的に持ってdancing linksのようなことをして優先度の変更とポップをにした。[1] 自分の実装はここにある。
Editorialはmaximum cardinality searchではなくlex. BFSに言及していたけれど、これはこれでけっこう大変そうに見える。
性質を調べてググって特徴付けを理解してアルゴリズムを実装して……みたいな段取りに3日かけてしまった。
正統な方法はTarjan, Yannakakis(1984)に書いてあるらしいのだが、買えなかった…… ↩︎
2つの三角形をとして、それらの3辺をそれぞれ長いほうから, とする。6辺の中で一番長い辺をとしてよい。
入力があらかじめ長さの降順で並んでいるとする。6辺の選び方の順番を全列挙すると次のようになる:
これらを調べていく。三角形が成立するためには、が成り立っていることが必要十分なので、小さいほうの4辺は左に詰めても損にならない。したがって、下の列挙ででつながった辺同士は列上で隣り合っているとしてよい。
これらを3つに分類してそれぞれ最大値を計算する。
これはいちばん簡単で、三角不等式を満たす連続する3辺を左から探して、見つかったらさらに3辺を探せばよい。
連続する5辺のすべてについて、が三角不等式を満たすような選び方でが最大になるものを検討すればよい。その選び方について、となるような最大のを左方から探せばよくて、これは二分探索でできる。
やはり連続する4辺のすべてについて、が三角不等式を満たすような選び方でが最大になるものを検討すればよい……のだが、その選び方について、左方にあるでを満たすものの中でが最大になるものを探す必要がある。これは（遅延伝搬付きの）平衡二分木に、をキー、を値として挿入していって、キーがより小さい区間の中での最大値を求めればよい。。
以外のパターンはすべて左に詰めることができるので、連続した6辺だけを調べればよいらしい。まったく気づかなかった。