2020年4月21日火曜日

天下一プログラマーコンテスト2012 予選B C - 席が足りない

同じ席に座れる関係を無向グラフGGで表すことにすると、可能な席数を求める問題はGGをいくつかのクリークに分割する問題と解釈できる。したがって、この問題は最小クリーク被覆問題そのものなので、補グラフの彩色数を求めればよい。

彩色数を求めるO(2nn)O(2^nn)アルゴリズム:
https://ei1333.github.io/luzhiled/snippets/graph/chromatic-number.html
https://codeforces.com/blog/entry/57496
https://www.slideshare.net/wata_orz/ss-12131479

2020年4月12日日曜日

ABC 162 F - Select Half

前の整数を取ったら、次の整数は取れないし、前の整数を取らなかったらだいたい次の整数を取る必要があることに注目してDPする。

後者の場合は必ずしも取らないといけないわけではなく、何回かはパスする必要がある。NNが偶数の場合はちょうど1回パスするべきで、NNが奇数の場合はちょうど2回パスするべきである。したがって

dp[x][y][z]:=\operatorname{dp}[x][y][z] := a1,...,axa_1, ..., a_xまで見て、整数axa_xを取り(y=1)(y=1)/取らず(y=0)(y=0)、今までにパスした回数がzzである場合の最大値

としてDPすればよい。ただし例外として、最後の整数aNa_Nを取らなかった場合はパスしたとみなす必要がある。

2020年4月11日土曜日

Google Code Jam 2020でのSBCLのトラブル

GCJ Round 1Aに出てメモリエラー(?)にハマってしまったのでメモ。

Square Danceのhiddenを落としてしまったのだが、ローカルでいろいろ調べても落ちるケースが見つからない。テストサブミットでしつこく調べていると、どうも入力が大きい時に無条件で落ちているようだった。まさかと思って、dynamic-space-sizeを増やしたSBCLを別に起動して投げてみたら通った。ヘッダを以下のようにする:

(unless (member :child-sbcl *features*)
  (quit
   :recklessly-p t
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--dynamic-space-size" "8GB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))

必要なサイズを調べてみると

  • 1GBに設定 → 落ちる
  • 2GBに設定 → テストケースごとにgcすれば通る
  • 4GBに設定 → 一回gcすれば通る
  • 8GB、16GBに設定 → gcしなくても通る

という感じだった。

しかし、メモリ制約が1GBなのに8GBが必要なのは不可解ではある。たまに起こる現象として、使用量500MBあたりで新たにメモリを確保しようとするときに、1GB以上確保しようとしてheap exhaustedになるというのがあるが、それは2GBや4GBに設定してもだめな理由を説明していない。そもそも、roomとかで調べてもそんなにたくさんメモリを使っているようには見えないし…… ローカルでroswellのsbcl-bin/1.3.14を使っても起きない問題なので、調べるのが難しい。

次のroundの方針は迷うけれど、

  • 最初からdynamice-space-sizeを大きめに設定する。(とりあえず16GB?)
  • 1つ目のテストケースの前に(gc :full t)する。(コンパイルでけっこうメモリを使うので)
  • テストケース数が多すぎなければ一回ごとにgcする。

でいくことにする。

SBCL環境

GCJ 2020のSBCLの詳細は以下の通り:

事前コンパイルはないが、今年も長めのTLでまとめてテストするスタイルなので、コンパイル時間のぶんのロスは気にしなくてよさそう。


上の問題は不運ではあったけれど、そもそもPascal Walkをバグらせてしまったのが悪いとも言える。チャンスはまだあるので、早めに気づけてよかった。

2020年4月4日土曜日

BCU30 F - 数列と計算

区間[l,r)[l,r)に関する掛け算alal+1...ar1a_l a_{l+1} ... a_{r-1}が何回足されるかを数えればよい。区間の右端を揃えて数えると下の表のようになる:

1 2 3 4 5
a123a_1 \cdot 2^3 a1a222a_1a_2 \cdot 2^2 a1a2a32a_1a_2a_3 \cdot 2 a1a2a3a41a_1a_2a_3a_4 \cdot 1 a1a2a3a4a51a_1a_2a_3a_4a_5 \cdot 1
a222a_2 \cdot 2^2 a2a32a_2a_3 \cdot 2 a2a3a41a_2a_3a_4 \cdot 1 a2a3a4a51a_2a_3a_4a_5 \cdot 1
a322a_3 \cdot 2^2 a3a42a_3a_4 \cdot 2 a3a4a52a_3a_4a_5 \cdot 2
a422a_4 \cdot 2^2 a4a522a_4a_5 \cdot 2^2
a523a_5 \cdot 2^3

(幅の関係でN=5N=5でやったけど、N=6N=6くらいのほうがわかりやすいかも)

上の表から、axa_xを右端とする掛け算の総和からax+1a_{x+1}を右端とする掛け算の総和を得るには、だいたいax+1/2a_{x+1} / 2を掛ければよいということがわかる。この係数で帳尻を合わせるために少し改変すると、次のようになる:

0 1 2 3 4 5
242^4 a123a_1 \cdot 2^3 a1a222a_1a_2 \cdot 2^2 a1a2a32a_1a_2a_3 \cdot 2 a1a2a3a41a_1a_2a_3a_4 \cdot 1 a1a2a3a4a51a_1a_2a_3a_4a_5 \cdot 1
232^3 a222a_2 \cdot 2^2 a2a32a_2a_3 \cdot 2 a2a3a41a_2a_3a_4 \cdot 1 a2a3a4a51a_2a_3a_4a_5 \cdot 1
232^3 a322a_3 \cdot 2^2 a3a42a_3a_4 \cdot 2 a3a4a52a_3a_4a_5 \cdot 2
232^3 a422a_4 \cdot 2^2 a4a522a_4a_5 \cdot 2^2
232^3 a523a_5 \cdot 2^3
232^3

したがってdp[0]:=2N1\operatorname{dp}[0] := 2^{N-1}で初期化したあと、dp[x]:=dp[x1]ax/2+2N2\operatorname{dp}[x] := \operatorname{dp}[x-1]\cdot a_{x}/2 + 2^{N-2}と更新していけばよさそう。ただし、最後だけは1/21/2を掛けずにdp[N]:=aNdp[N1]+2N2\operatorname{dp}[N] := a_{N}\operatorname{dp}[N-1] + 2^{N-2}とする。

dp[1]\operatorname{dp}[1]からdp[N]\operatorname{dp}[N]までを、不要な2N22^{N-2}を引きながら足していけば、答えが得られる。


端が含まれると足される回数が変わるということを整理するのに時間がかかった。