2020年3月30日月曜日

ARC 049 C - ぬりまーす

ARC 049 C - ぬりまーす

タイプ2の条件はひとまず無視して考える。

タイプ1のそれぞれの条件(x,y)(x, y)についてyyからxxに辺を張ったグラフGGを与えたとき、問われていることは「GGから入次数が00の頂点を次々に消していくとき、最大で何個消せるか?」ということだった。この個数に消す順序は関係ないので、実際に自由に消していって確かめればよい。具体的には、入次数が00の頂点をすべてキュー(あるいはスタック)に入れてBFS(あるいはDFS)をすればO(N+A){\mathcal O}(N+A)でできる。手順としては、キューから頂点を取り出したら、隣接頂点の入次数を1ずつ下げて、入次数が00になったものをキューに入れればよい。あるいは、この制約ならBellman-Fordっぽく入次数が0の頂点の隣接頂点の入次数を下げる操作をNN周繰り返す、でもよさそう。(O(NA){\mathcal O}(NA))

タイプ2の条件(u,v)(u, v)については、

  1. uuを選ばないとする(=頂点uuは存在しないものとする)
  2. vvを選ぶ場合にはuuを先に選んでいなくてはならないとする。

の2通りを調べれば十分で、後者はタイプ1と同じなので上の問題に帰着できている。タイプ2の条件は十分に少ないので、2B2^B通りのグラフを調べればよい。O((N+A)2B){\mathcal O}((N+A)2^B)

2020年3月27日金曜日

競技プログラミングでCommon Lispを使っている人とこれから使うかもしれない人のために

競技プログラミングでCommon Lispを使っている人とこれから使うかもしれない人のために

Qiitaからこちらに転載した。


表題の通り、競技プログラミングに参加しているLisperとこれから参加するかもしれないLisperのために、必要な情報を一通りまとめています。

コンテストサイトの選択

AtCoderではCommon Lispが使えますし、CLで投稿できる大手コンテストサイトはCodeChefyukicoderCS Academyなど他にもいくつかあります。日本語の問題文があって運営の質が高くてコンテストが頻繁に開催されていて……というような点を考えていくと、競プロに興味を持った日本語圏のLisperにとってAtCoderは第一の選択肢といってよいでしょう。第二はyukicoderとCodeChefです。以下の解説は、特に断りがなければAtCoderを前提にしています。

Lispで競プロすることについて

本題ではありませんが、セクションを立てて言及しておくことにします。というのも、競技プログラミングに熱心なLisperはほぼ皆無に見えるからです。C++の使用率がどのサイトでも圧倒的なのは事実なので、競プロに興味のある人の中にも、そもそもLispに向いているジャンルなのかどうか不透明に思う人がいるかもしれません。

端的に言うと、わたしのレベルではパフォーマンスの面でデメリットを感じたことはありません。より高レートの状況でどうなるかは知りえないことですが、悲観する材料は特に見つかっていません。終わり。

……でもよいのですが、いくつかのポイントに絞って説明してみます。

○: 柔軟な構文

素早く・簡潔に・柔軟にDSLを生やすことにかけてはLispは今なお優れた言語であると言えるでしょう。競プロの文脈でもそれはちゃんと役に立ちます。もっとも、そういったものは競プロにおけるパフォーマンスにさほど影響しないとも思います。競プロで大事なのは考察力です。

○: スピード

最良ではないが、悪くもないです。AtCoderにおける速さという観点で言語を雑に分類すると

  • A群: C/C++/Rustなどの、システムプログラミングのための言語
  • B群: Ocaml/Haskellなど、ネイティブコードへの事前コンパイルを前提とするその他の言語。Java/C#などの高速VMを持つ言語。
  • C群: Python/Ruby/PHPなどのスクリプト言語

で性能はおおむねA>B>Cということになりますが、LispはBの中で速いほう、くらいの位置づけです。状況にもよるので絶対的な比較は難しいですが、「Java/C#よりやや有利」くらいの認識を持っています。そして、Java/C#専のまま強くなる人は特に珍しくもありませんから、スピードの問題はさほど心配しなくてよいです。

実情を言うと、500点くらいまでの問題では正しいロジック(=最悪計算量が制約に適っているロジック)で書けていればTLE(Time Limit Exceeded)することはめったにありません。TLEするのは、最適化が足りないからではなく、計算量の考察がおかしいからと思ってほぼ間違いないです。ほとんどの場合、最適化のための基本的な宣言すら必要ないと思います。それ以上のレベルの問題でも、SBCLが遅くて通せないとか、あるいは最適化しても制限時間ぎりぎりになるという事態に陥ったことは一度もありません。そもそもAtCoderではJavaで通らない問題は出題されないそうなので、SBCLで通せないというケースは考えにくいです。

ただ、AtCoderのシステム上の問題として、Lispは(C++等と違って)コンパイルの時間を取らずにsbcl --scriptで実行されるので、その時間の分だけやや損をしているという点があります。このロスですが、普通は150ms以内におさまるし、必要な長さのコードを提出する限り300msを超えることは稀なので、深刻な問題にはなっていません。1 もちろん、コンパイルのフェーズを用意してくれるに越したことはないですし、次回の言語更新ではそのようになるでしょう。

△: 標準機能・ライブラリの充実度

Common Lispの標準ライブラリは貧弱です。平衡二分木もなければ、優先度付きキューも両端キューもないし、それどころかただのキューすらないので、あらゆるデータ構造をいちいち用意しなければなりません。2 良い所もそれなりにはあって、多倍長整数が自然に扱えるのでオーバーフローの処理をちょっとくらいサボってもOKなのは悪くない点ですし、有理数や複素数も競プロでは活躍します。stringが文字の配列であるという時代遅れな仕様も、競プロではむしろ望ましいです。しかし、総合的に見てやや不十分なのは否めないでしょう。

もっとも、競プロerはどの言語を使っていてもけっきょくは自前実装のデータ構造を少しは用意することになるので、二分ヒープを自分で書くことくらいは誤差レベルとも言えます。ただ、自分でデータ構造を書く場合に、効率のために要素型で静的ディスパッチするようなコードを書くのが大変という別の問題はあります。CLにはパラメータ多相を自然に導入する方法の決定版がいまだにないので…… (競プロに限った話ではありませんが、ジェネリクスのデファクトがないのはCLのアキレス腱だと思っています。)

△: コンテストサイト・オンラインジャッジの選択肢

Common Lispは最大手のCodeforcesで使えませんし、もちろんTopCoderでも使えません。日本の競プロer御用達のAOJも対応していません。したがって、LisperはAtCoderyukicoderCodeChefを中心に利用し、Google Code Jamがあれば出て、足りなければCS AcademyHackerRankなどを使うことになります。それが不満ならC++やJavaを選んだほうがよいでしょう。ちなみにわたしはまあまあ不満です。

✕: 言語コミュニティの規模

Lisperの数が極めて少ないため、参考にできるコードがありません。AtCoderで400点以上の問題だとLispの提出はゼロであることが多いです。困ります。もちろん、根幹のロジックを理解するために読むのはなんの言語でもよいので、C++やPythonの提出コードを見ればよいです。しかし、他人のコードを読むのは、整理された間違えにくい書き方を学ぶためという側面が強いので、言語が同じであるほうがはるかに参考にしやすいのも確かです。

もっとも、この問題はあなたが参加すれば解消されるとも言えます。ぜひやってみませんか。

いくつかの問題と解決策

実践で生じるトラブルとその回避方法を挙げます。「いくつか」と題しましたが、今のところ重要なものは最初の1つだけです。また、入出力関係の話題はまとめて後のセクションで扱います。

スタックサイズが足りない(重要度:◎)

SBCLのデフォルトのスタックサイズは2MBであり3、このサイズを超えて関数呼び出しするとエラーになります。(末尾呼び出しになっていればジャンプに変わるので安全です。)

2MBというサイズですが、目安としては105の深さで再帰すると確実にcontrol-stack-exhaustedする、104ならたぶんOK、くらいです。オーダー的に無理そうなら再帰を使わなければ良いのですが、DFSなどを手動スタック+ループで書くのは馬鹿馬鹿しいと思う人も多いでしょうし、そもそもツリーの走査や分割統治的な処理は再帰で書いたほうが間違えにくいのも確かです。幸運なことに、この問題については解決策が確立しています。スタックサイズを増やしたSBCLを子プロセスとして呼び出せばよいのです。ファイルの冒頭に次のフォームを置きましょう。

#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--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が代わりに処理してくれます。

  • 終了コード絡みの処理は、子プロセスでエラーが起こった時に親プロセスのエラーにするためにやっています。そうしないと子プロセスでエラーが起こってもREと表示されなかったりします。
  • #-swankは必須ではありませんが、わたしはSLIMEでコーディングしているので、編集中にこのフォームが評価されないようにするために書いています。
  • 直接--scriptで実行する仕様でも、コンパイルしてから実行する仕様でも、どちらでも通るようにしています。yukicoder、CodeChef、CS Academy、HackerRank、HackerEarth、SPOJ、Kattis、GCJでも使えることを確認しています。
  • 今のところ128MBで足りなかったことはありませんが、64MBで足りなかったことはあります。スタックサイズが足りないとき、必ずしもREと表示されるわけではなく、TLEになることもあるので気をつけましょう。

やや強引なハックではありますが、この方法の欠陥は発見されていません。10ms程度ロスしてわずかにメモリ消費が増えるだけですし、なんなら、常にこのフォームをくっつけて投稿しても問題ない可能性があります。(わたしは今のところ、スタックサイズが不安な時にしか使っていません。)

最初のテストケースに時間がかかっている(重要度:○)

atcoder.jpg

20ms程度で済むはずの処理が、最初のテストケースだけ200ms以上掛かっていることがよくあります。原因は知りませんが、AWSの問題らしく、Lisp以外でも生じるようです。TLEした場合には繰り返し実行して検証するという対応を取っているとのことで、これが原因でACできなかったと思われるパターンはわたしは経験したことがないです。したがって、解決策は「無視する」です。問題で与えられた時間制限よりずっと短い実行時間を比較するような目的にはAtCoderの環境は向いていません。(そもそもそういう競技ではないので。)

ベクタのソートが遅い(重要度:△)

(declare (inline sort))しましょう。SBCLのsortsb-ext:maybe-inlineなので、デフォルトではインライン化されません。4 インライン化されないと、ベクタの要素型を考慮した静的ディスパッチがされないので、常識的なスピードが出ません。

ただ、SBCLのソートはベクタに対してはヒープソートなので、いずれにせよスピード重視ではないし、標準のソートは範囲指定ができないという問題もあります。5 マージソートなりクイックソートなりを用意しておくのもよいかもしれません。

リストをsortする場合(マージソート)に関してはさらに(declare (inline sb-impl::stable-sort-list))が必要だったりします。(ソートが間に合うか不安なくらいに入力が大きいケースではリストで持たないほうがよいと思いますが。)

また、普段からSBCLのどの関数がどの場合にインライン化(インライン宣言やdefine-source-transformdeftransformdefine-vopによる変換)されるのか、型を考慮した最適化があるのかを気にしておきましょう。SLIME上なら、標準の関数に対してM-. slime-edit-definitionするとSBCLのソースにジャンプできます。

末尾の改行の扱いが一貫していない(重要度:△)

  1. テストケースの入力の末尾に改行があるとは限りません。常に#\Newlineがあるという仮定で処理をすると原因不明のREに苦しむことになります。

  2. 同様に、出力の末尾に改行がなくても通るかどうかは不定です。必ず改行を送っておきましょう。

ただ、これらは昔の問題に限った注意点だと思います。最近のジャッジは出力を柔軟に受けつけてくれる印象があります。

入出力の改行コードは#\Linefeed決め打ちで問題なかったはずです。ウェブ上のサンプルケースにはCR+LFのものもありますが、合わせる必要はありません。

コンパイルメッセージが見たい(重要度:△)

AtCoderのSBCLのバージョンは1.1.14です。ローカルのバージョンもそれに合わせたい場合は、roswellを使うなりする手があると思いますが、コンパイラの出力を確認したいだけなら、コードテストで次のヘッダをつけて送ると良いでしょう:

#-swank
(quit
 :unix-status
 (process-exit-code
  (run-program *runtime-pathname*
               (list "--noinform"
                     "--eval" (format nil "(compile-file \"~A\")" *load-pathname*)
                     "--quit")
               :output t :error t :input t)))

CS Academy: 実行時エラーが起きてもWrong Answerと表示される

注意: 2019年8月頃に仕様が変わったらしく、下の記述はたぶん今の事情とは異なる。

CS Academyの環境でCommon Lispを使うと、実行時エラーが起きてもResultにWrong Answerと表示されるので、エラーなのか答えが間違っているかの区別がつきません。おそらく、SBCLを--scriptで実行しておらず、デバッガが起動したときのエラー出力を回答とみなしているのだと思います。対策は簡単で、提出コードの始めのほうに

(sb-ext:disable-debugger)

という一行を入れておけば、エラーが起きたときにNon zero exit code = 1と表示されるようになります。ローカルで編集しているときにdisable-debuggerするのが不都合であれば、例えばSLIMEなら#-swank (disable-debugger)などとするとよいでしょう。

SBCLのバージョン間の差異について(重要度:△)

サイトによってSBCLのバージョンが異なるので、メモしておきます。該当のバージョンより上にある項目が注意点になりますが、重要な差異はないです。一番古いAtCoderでさえ、特別に困った点は思いつかないですね。(意味がわからない項目は自分には関係ないと思ってください。)

  • 負数に対するmodの返り値が正数であると推論されないことがあります。うまくいかない場合はtheを使いましょう。version 1.5.7でたぶん解決。
  • make-arrayで多次元配列を作る場合、element-typeの推論が正しくできないことがあります。sb-c:make-array-header*のderive-typeをコピペすれば解決しますが、そんなことをしなくても必要なら型を手打ちすればよいです。version 1.5.6で解決
  • yukicoder: version 1.5.5
  • maphashが事前指定したサイズに対するO(N){\mathcal O}(N)。詳細はここに書きました。version 1.5.5で過去に到達した最大要素数に対するO(N){\mathcal O}(N)になりました。どちらの仕様でも、「maphashを何回も呼ぶけど合わせてO(N){\mathcal O}(N)」みたいな場合に本当にO(N){\mathcal O}(N)かどうか気を付けたほうがよいです。
  • array-element-typeが定数伝搬しません。インライン関数の中で同じelement-typeの配列を作りたい場合等に困るかもしれません。array-element-typeのdeftransformをコピペすれば解決しますが、そんなことをしなくても必要なら型を手打ちすればよいです。version 1.5.0で解決
  • CS Academy: version 1.4.16
  • HackreRank: version 1.4.15
  • CodeChef: version 1.3.13
  • HackerEarth: version 1.3.1
  • 2の累乗にexptを適用した時にビットシフトに変換されません。ashを使いましょう。version 1.2.10で解決
  • sb-int:%hash-table-alistがなくて、sb-impl::%hash-table-alistにあります。そもそもユーザーが使うためのものではないですが…… version 1.2.9から
  • logcountpopcntにならないので多少遅くなります。非想定のwavelet matrixなどでぎりぎり通したい場合には関係あるかもしれません。version 1.2.8で解決
  • sb-mpfrがない。version 1.2.0で解決
  • AtCoder: version 1.1.14

SBCLはかなり昔から安定しているので、処理系が落ちるようなバグはまず無いと思っていいです。私自身は、AtCoderでdynamic-extent絡みのバグを踏んだことが1回ある程度です。(詳細を忘れました)

入出力のTips

大量の入出力をこなす場合(目安としては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"になります。
  • SWANKの標準IOはbivalentでないため、SLIME上で編集している時は代わりに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))))))
  • バッファサイズはコンパイル時に与えるべきなので、マクロにしました。

read-lineとの比較ですが、105行以上のデータを読み込むなら200msくらいは得できるイメージです。最大で800msほど速くなるパターンを経験しています。

ただ、リードにしろパースにしろ、1文字ずつ読むならストリームから直接処理したほうが良くなりますし、read-sequenceなどを使う手もあるでしょう。以下にそのやり方も紹介しますが、read-lineや上の関数が役に立つこともよくあります。ストリングを介した行単位の処理は柔軟で、変則的な入力にも対応しやすいためです。

整数を高速に読み込む(使用頻度: ◎)

大量の整数を読み込んで処理する問題は頻繁に出ます。整数が10510^5個を超えたあたりから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))))
  • 上と同様の理由で、SLIME上とそれ以外で入力方法を変えています。

read-fixnumは、読み込む整数がfixnum(=(signed-byte 63))とわかっている場合のreadの代替であり、わたし自身、ここに挙げた関数の中でもっとも頻繁に使っています。

read-bignumも用意してありますが、ほとんど使ったことがありません。AtCoderでは多倍長整数をそのまま扱えないと厳しい問題はそうそう出ないと思いますし、出ても1つ読むだけならreadが十分速いです。6 どのくらい大きな整数を扱えるかは感覚で覚えるしかありませんが、目安としては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)))

これは場合によってはかなり効きます(400ms以上の得になったりする)。マクロ化すると次のような感じでしょうか。

(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)))))

ただし、大昔の問題はメモリ制限が64MBなので、string-output-streamに全部ためるとMLE(Memory Limit Exceeded)になってしまうことがあります。最近の問題は256MBまたは1GBなので、この点を気にする必要はありません。

小数を出力する(使用頻度: △)

SBCLのformat~F~$は遅いです。特に、~,5F~5$のように小数点以下の桁数を指定した場合、出力だけで時間切れするレベルのボトルネックになったりします。

単純な解決策としてはwriteprincをそのまま使うことが挙げられます。この場合、出力に指数表記が混じることになりますが、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通常の表記で出力する関数も用意してはいます(がほとんど試していないので注意)。

小数を高速に読み込む(使用頻度:✕)

小数を大量に入力する問題は意外にも見ないですね。SBCLのリーダーをいじったものをいちおう用意していますが、ほとんど試していません。

なお、readで読む場合、デフォルトではsingle-floatでパースされるので意図せず精度が落ちてしまう可能性はあります。これが問題になったケースは経験がありませんが、やはり*read-default-float-format*を変更すればよいです。

結び

最後に、いろいろ述べましたが、特にAtCoderでは事前準備(ライブラリの整備)はさほど重要なポイントではないので、気おくれすることはありません。入出力絡みはそれなりに注意を払う必要があるので上で紹介しましたが、そこをクリアすればあとは考察力がすべてです。

ということです。競プロ、楽しいですよ。


  1. コンパイルを重くしすぎると1秒近く使ってしまうケースはありえて、ここまで失うとさすがにTLEのリスクがあります。ただ、わたしの経験の範囲では、コンテスト中にこれで失敗したことは一度もないくらいにレアな事象です。 ↩︎

  2. ただし、SBCLではただのキューで良ければsb-queueが十分使えます。また、src/code/target-bst.lisp(バージョン1.5.0より前)かsrc/code/avltree.lisp(1.5.0以降)に平衡二分木が一応あったり、src/code/timer.lispに二分ヒープがあったりしますが、これらはユーザーが使うことを意図したものではないでしょうし、汎用的に作られてはいません。 ↩︎

  3. AtCoder上のSBCLについては、コードテストで(print (sb-alien:extern-alien "thread_control_stack_size" sb-kernel::os-vm-size-t))を送れば確認できます。 ↩︎

  4. 標準の関数のうち、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があり、これらも明示すればインライン化されます。 ↩︎

  5. 一応、displaceしたベクタをソートして副作用を利用するという方法はあります。おそらく未定義動作ですし、simpleでなくなるので遅いですが、SBCLでは意図通りに動くはずです。 ↩︎

  6. いっぽう、SBCLのparse-integerは多倍長整数をパースするのが遅いので注意。10100000を読むのに2秒以上かかります。 ↩︎

2020年3月18日水曜日

CODE FESTIVAL 2014 予選B C - 錬金術師

CODE FESTIVAL 2014 予選B C - 錬金術師

最大流で解ける。source, sink, S1, S2と26種類のアルファベットに対応する頂点の計30頂点を用意する。source→S1, source→S2に容量NNの辺を張り、S1から各アルファベットccに向かってS1に含まれているccの総数に等しい容量の辺を張り、S2についても同様にする。最後に、各アルファベットccからsinkに向かってS3S3に含まれているccの総数に等しい容量の辺を張る。このネットワークに容量2N2Nのフローが流せればYESということになる。


第一感がフローなのは成長なのか退化なのか。

2020年3月17日火曜日

TTPC 2015 G - titech分離

TTPC 2015 G - titech分離

文字の数があわないなどの自明ケースは先に考慮しておく。

実際にtitechという文字列をいくつか作りかけながら、文字列SSを先頭から走査していくことを考える。たとえばtitという文字列が2つできているときに次がeだったら、どちらに追加しても区別できない。したがって、長さxxの列をdp[x]dp[x]個持っているとしてdp[0]:=S/6dp[0] := Sの長さ/6と初期化しておけばよく、eを見たらdp[3]dp[3]を1減らしてdp[4]dp[4]を1増やすという感じで遷移すればよい。ほかの文字についてもだいたい同じで、最後まで走査できたらYesということになる……のだが、問題は文字tで、010 \rightarrow 1232 \rightarrow 3の二通りに追加できる。これはDFSで全探索すればよさそう。

しかし、計算量がどうなるかわからなくてしばらく逡巡していた:

  1. titechは最大で16個作れてこの時tは32個だからDFSの末端の数は23241092^{32} \simeq 4 \cdot 10^9以下。
  2. 010 \rightarrow 1232 \rightarrow 3は同じ回数だけ選ぶ必要があるから(3216)6108\binom{32}{16} \simeq 6 \cdot 10^8以下。
  3. 最初は010 \rightarrow 1、最後は232 \rightarrow 3を選ぶ必要があるから(3015)1.5108\binom{30}{15} \simeq 1.5 \cdot 10^8以下。
  4. 010 \rightarrow 1を選んだ回数が常に232 \rightarrow 3を選んだ回数以上でなければならないから、カタラン数でC15107C_{15} \simeq 10^7以下。

逆から貪欲でいいらしい。なんと……

TTPC 2015 L - グラフ色塗り

TTPC 2015 L - グラフ色塗り

赤い辺だけ張ったグラフに最大フローを流したあとの残余グラフを考える。このグラフにできるだけ多くの青い辺を追加しつつ、sourceがsinkにつながらないようにする必要がある。これは青い辺をすべて張ってから最小カットを求めることと同等である。したがって、2回最大フローを流せばよいことになる。

ただ、赤い辺の容量を1にして流すと、入力例3のように赤い辺がボトルネックになって正しい答えが得られない。赤い辺は十分に大きい容量(1000とか)にする必要がある。


バチャ中に適当にやったら通ってしまったのだけど、最後のポイントを納得できていない感じがする。

2020年3月16日月曜日

CodeChef Match Challenge 2020 - Inverse of a Function

CodeChef Match Challenge 2020 - Inverse of a Function

まずは与えられた数列の美しさを求める方法を考える。数列(ai)(a_i)ii桁目が11の数がd(i)d(i)個含まれているとき、d(i)d(i)個から奇数個選べば残りの数をどう選んでもxorのii桁目が11になる。つまり、ii桁目だけに限ってxorの総和を取ると、d(i)>0d(i) > 0なら2i2^i

2Nd(i)((d(i)1)+(d(i)3)+...)=2Nd(i)2d(i)1=2N1 \begin{aligned} & 2^{N-d(i)} \biggl( \binom{d(i)}{1} + \binom{d(i)}{3} + ... \biggr) \\ = & 2^{N-d(i)} 2^{d(i)-1} \\ = & 2^{N-1} \end{aligned}

個足されることになる。すなわち、ii桁目が立っている数が(ai)(a_i)の中に1つでもあれば、ii桁目の総和は2N12i2^{N-1} 2^iであり、ひとつもなければ00である。したがって、全体の総和はbitwise orを使って

2N1i=1Nai2^{N-1} \bigvee_{i=1}^{N}a_i

と表すことができる。これが(ai)(a_i)の美しさである。

次にF(N,B):=F(N, B) := 長さNNで美しさBBの数列の数を求める方法を考える。上の式を見ると、BBが与えられたときにB/2N1B/2^{N-1}の立っているビットを考えればよいことがわかる。つまり、B/2N1B/2^{N-1}ii桁目が11なら、NN個の数のうちの少なくとも11つの数のii桁目が11であればよく、ii桁目に限定したNN個の数の選び方は2N12^N-1通りとなる。いっぽう、B/2N1B/2^{N-1}ii桁目が00なら、NN個の数の対応するii桁目はすべて00でなければならないので、選び方は11通りである。したがって、整数xxの立っているビットの総数をc(x)c(x)で表すとき、

F(N,B)={(2N1)c(B/2N1)(B2N1)0()F(N, B) = \begin{cases} (2^N-1)^{c(B/2^{N-1})} & \qquad (Bが2^{N-1}で割り切れる)\\ 0 & \qquad (それ以外) \end{cases}

と書ける。

さて、解くべき問題はF(N,B)Xmod  MF(N, B) \equiv X \mod Mを満たす最小のBBを求めるというものだった。上の式を見ると、(2N1)kXmod  M(2^N-1)^k \equiv X \mod Mを満たす最小のk0k \ge 0が求まれば、kk個の11を並べてN1N-1回左シフトしたものが求める最小のBBということになる。これで離散対数問題に帰着できた。

ただし、上の式からわかるように、N2N \ge 2の時は美しさ11の数列がないので、X=0X=0に対しては常に11が答えということになる。(もちろんM=0M=0なら00)。