2020年5月28日木曜日

JOI2010 春合宿 - Sengoku

JOI2010 春合宿 - Sengoku

(i,j)(i, j)を通る傾き11の直線の切片はjij-iで、傾き1-1の直線の切片はi+ji+jになる。

とりあえず重複のことは忘れて番兵毎に数えると、傾き11の直線の通るマスはLijL - |i-j|個あり、傾き1-1の直線の通るマスはi+j<Li+j < Lのときi+j+1i+j+1個、i+jLi+j \ge Lのとき2L(i+j+1)2L - (i+j+1)個あることがわかるので、まずはこれらの総和が基本になる。

次に、重複を除くことを考える。まず、切片と傾きが同じ直線は完全に重なるので、登場した切片を記録しておいて、前に見たものは無視することで重複を避けられる。

最後に傾き11の直線と傾き1-1の直線の交点の数を引く必要がある。まず、交点が格子点になるのは切片が偶数同士、奇数同士の場合なので、切片が偶数の直線についてのみ考えることにする。(奇数のものの交点も同様に数えられる。) 傾き11で切片がCCの直線と傾き1-1の直線が与えられた領域内で交わるのは、後者の切片が[C,2(L1)C[|C|, 2(L-1) - |C|]に入っているとき、またその時に限るので、ソートしておいてそれぞれ二分探索で数えられる。

JOI2009 春合宿 - Pyramid

JOI2009 春合宿 - Pyramid

ピラミッドを高さの降順にソートしてBFSのイメージで埋めていく。具体的にはH:=3000H:=3000から降りながら次を繰り返せばよい:

  1. 頂上の高さがHHのすべてのピラミッドについてHHを答えに足し、その座標(x,y)(x, y)を(スタックなりキューなりに)積んでおく。
  2. 前のループで高さH+1H+1として積んでおいた頂点の八方を調べて、それぞれ訪問済みでなければHHを答えに足して座標を積んでおく。

メモリ制約が厳しいのでいろいろ使いまわす必要がある。

2020年5月25日月曜日

CodeChef May Cook-Off - Chefina on a Trip

CodeChef May Cook-Off - Chefina on a Trip

無向辺を2つの有向辺と見て、スコアが下がる向きに重み1-1、上がる向きに+1+1、変わらないなら00を付与すると、ある有向パスが上りになっているmin\Leftrightarrow \minクエリが11である、下りになっているmax\Leftrightarrow \maxクエリが1-1である、と判定できる。

ダブリングLCAの構築をする時に、同時にmin/maxについてもダブリングのテーブルを作っておけばパスuvu - vがbeautifulかどうかは適当に判定できる:

  1. uuから根に向けてスコアが上がる限りダブリングで上る。LCA(u,v)LCA(u, v)の深さより上(inclusive)に行けたら3に行く。
  2. さらに根に向けてスコアが下がる限り上る。LCA(u,v)LCA(u, v)の深さより上に行けなかったらfalseを返す。LCA(u,v)LCA(u, v)の深さより上に行けたら頂上がuLCAu- LCAの側にあると記録しておく。
  3. vvから根に向けてスコアが上がる限り上る。LCA(u,v)LCA(u, v)の深さより上に行けたらtrueを返す。頂上がuLCAu-LCAの側にあるのにLCA(u,v)LCA(u, v)の深さより上に行けなかったらfalse。
  4. さらに根に向けてスコアが下がる限り上る。LCA(u,v)LCA(u, v)の深さより上に行けたらtrueを返す。
  5. falseを返す。

山のイメージに従って書くだけなので特に難しいとは感じなかった。でも、振り返ってみると、uuvvを完全に対称に扱ったほうがいい気がする。

2020年5月24日日曜日

パ研コンペティション3日目 E - 美しい和音

パ研コンペティション3日目 E - 美しい和音

f(i,x):=A1,...,Aif(i, x) := A_1, ..., A_iを使って作れる総和xxの美しい和音の総数、とする。ffの漸化式はAiA_iを使う/使わないの二択の和でf(i,x)=f(i1,x)+f(i2,xAi)f(i, x) = f(i-1, x) + f(i-2, x-A_i)と書ける。これでDPすれば部分点が取れる。

また、DPのほとんどの枝で不可能な状態の遷移をしていることに注目すると高速化できる。例えば、A1,...,AiA_1, ..., A_iから作れる美しい和音の最大スコアg(i)g(i)がDPで求まるので、これを事前に求めておいて、g(i)g(i)xxより小さくなったら枝刈りしてよい。これで満点が取れた。


でも、計算量がよくわからない。

2020年5月21日木曜日

ふか杯 5th contest E - すごろく

ふか杯 5th contest E - すごろく

f(i):=f(i) := マスiiからゴールするまでにサイコロを振る回数の期待値、として降順にDPしたいが、振り出しに戻る場合の扱いを考えなくてはならない。

通常、ループを含む確率DPは左辺と右辺の両方にf(i)f(i)が登場する式が立式できて、f(i)=...f(i) = ...となるように整理すると遷移がわかるはずだが、この場合は紙の上で式変形するのは難しそうに見える。そこで、f(1)f(1)の係数も別にDPで求めることにする。つまり、f(i)=a(i)+b(i)f(1)f(i) = a(i) + b(i)f(1)と表して、a,ba, bを降順で求める。

xi>0x_i>0なら

a(i)=a(i+xi)a(i) = a(i + x_i)

b(i)=b(i+xi)b(i) = b(i + x_i)

xi=0x_i = 0なら

a(i)=16(a(i+1)+...+a(i+6))+1a(i) = \frac{1}{6}(a(i+1) + ... + a(i+6)) + 1

b(i)=16(b(i+1)+...+b(i+6))b(i) = \frac{1}{6}(b(i+1) + ... + b(i+6))

xi=1x_i = -1なら
a(i)=0a(i) = 0

b(i)=1b(i) = 1

これでa(1),b(1)a(1), b(1)が得られるので、答えはf(1)=a(1)/(1b(1))f(1) = a(1)/(1-b(1))と求まる。

2020年5月18日月曜日

ABC 168 F - . (Single Dot)

ABC 168 F - . (Single Dot)

縦線と横線で分割される(N+1)(M+1)(N+1)(M+1)個くらいの矩形について、隣接している矩形との連結性を調べながらBFSすればよい……のだが、なかなか通らなかった。

Ci=CjC_i = C_jのような場合の扱いが問題だった。そういうケースがありえることは承知していて、間に面積0の矩形があると考えて問題ないと思っていたのだが、(3,1)(5,1),(4,1)(6,1)(3, 1) - (5, 1), (4, 1) - (6, 1)のように縦線が重なっている場合(AiBjAjBi\Leftrightarrow A_i \le B_j \land A_j \le B_i)に、前者の左にある矩形→中間の(面積0の)矩形→右の矩形、のように本来移動できないところを迂回して移動できてしまう可能性があることに気づいた。結局、前処理の時点でつながっている線分は1本につなげてしまうことで解決した。

第一回日本最強プログラマー学生選手権予選 C - Cell Inversion

第一回日本最強プログラマー学生選手権予選 C - Cell Inversion

区間の組み合わせの総数が求まれば、操作の順番の総数はN!N!を掛けて得られるので、前者を求めればよい。

SSを左から走査して、閉じていない区間を保持しながらDPすることを考える。つまり、

dp[x][y]:=x\operatorname{dp}[x][y] := x文字目までみて、閉じていない区間がyy個あるような場合の数

というDPをする。xx文字目がWWyyが偶数、もしくはxx文字目がBByyが奇数なら、ここでyy個の(閉じていない)区間のどれかを閉じるのが正しいので、

dp[x+1][y1]+=ydp[x][y]\operatorname{dp}[x+1][y-1] \operatorname{+=} y \cdot \operatorname{dp}[x][y]

xx文字目がBByyが偶数、もしくはxx文字目がWWyyが奇数なら、さらに新しい区間を開始して反転を1増やすべきなので

dp[x+1][y+1]+=dp[x][y]\operatorname{dp}[x+1][y+1] \operatorname{+=} \operatorname{dp}[x][y]

このDPはO(N2){\mathcal O}(N^2)の形になっているが、実際にやってみると各xxについて有効なyyは高々1つしかないことがわかるので、線形で書ける。


コンテスト当時にはまったくわからなくて、解説を読んでも天才解法に見えた問題だった。今見ると、いわゆる箱根駅伝DPを書けばアドホックな考察をしなくても解けてしまうことがわかる。

ただ、O(N2){\mathcal O}(N^2)のDPが見えているときに、それの延長として想定解が導ける場合とかなり難しい場合があって、コンテスト中にそちらにどこまで頭を使うかは微妙なところとは思う。今出ても、ムーブ次第ではまりかねない気がする。

2020年5月17日日曜日

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

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

GCJ Round 2に出たが、Round 1に引き続いてSBCL絡みのトラブルにあってしまった。

以下の(特に意味のない)コードをSBCL 1.3.8 ~ 1.4.5に打ち込むとコンパイルが終了しない。

(defun test (n graph)
  (let ((vector (make-array n :initial-element 1)))
    (setf (aref vector 0) 0)
    (let ((value 1))
      (dotimes (i n)
        (dolist (v (list 1))
          (setf (aref vector v) value)
          (dolist (y (aref graph v))
            (print y)))))))

1.3.7→1.3.8と、1.4.5→1.4.6の変化を眺めた感じでは、make-arrayの最適化に関連して低レベルの問題が起こっていそうで、(declare (fixnum n))(declare (notinline make-array))を宣言すると問題が解消するのでおそらくそうなのだろう。詳細はわかっていない。

Security Updateのvisibleをとりあえず通しておこうとして起きた現象で、この対処に時間を費やしてしまった。自分の準備にも問題があって、ローカルではバージョン1.4.14を使っていたので単純に問題の把握が遅れたというのがある。(GCJの環境は1.3.14だが、Windowsリリースはないし、CodeChefの1.3.13で問題が起きたことがないので気にしていなかった。) 本格的にWSL環境に移ることを考えたほうがよいのかもしれない。

しかし、こんな基本的なコードが落ちるのはさすがに驚く……


コンテスト後にはさすがに凹んだけれど、去年よりは確実に強くなっている。来年も頑張ろう。