phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

M-SOLUTIONS プロコンオープン C. Best-of-(2n-1)

問題

高橋くんと青木くんが、どちらかが合計N回勝つまでゲームを繰り返す。
1回のゲームでは、高橋くんが勝つ確率はA%、青木くんが勝つ確率はB%、引き分けになる確率はC%である。

ゲームが行われる回数の期待値を出力せよ。
ただし、期待値は小数ではなく、互いに素なP,Qを用いて期待値がP/Qと表せるとき、R*Q=P (mod 10^9+7)となる整数Rで答えよ。

制約

  • 1 <= N <= 10^5
  • 0 <= A,B,C <= 100
  • 1 <= A+B
  • A+B+C = 100
  • 入力はすべて整数

解法

(解説の方法)
Nの制約からO(N^2)な解法は許されない。

まず、引き分けについて考える。
引き分けは、そこまでのゲーム内容とは無関係にC%の確率で起こる。
そのため、勝ち負けが決まるようなゲームの内容に依存せずに考えられる。

依存するのは、勝ち負けが決まるようなゲームの回数で、これがM回だった場合、引き分けの回数の期待値が求められる。(ゲームを遅滞させていると考えられる。どのぐらい遅滞させるか?)
これは、「勝ち負けが決まるゲームが行われる確率が(100-C)/100、引き分けになるゲームが行われる確率がC/100のとき、勝ち負けが決まるゲームがM回行われる場合の、ゲームの行われる回数の期待値は?」という問題と考えられる。
これは、E_{勝ち負けが決まるようなゲームの回数}を残り何回ゲームを行うか?の期待値として、1回分だと、

E_0 -> E_1
↓↑

のような遷移であり、
E_0 = 1 + (100-C)/100 * E_1 + C/100 * E_0
E_1 = 0
と書けるので、
E_0 = 100/(100-C)
となる。
M回分で考えると、E_M = M * 100/(100-C)となる。
よって、勝ち負けが決まるようなゲームの回数がM回の場合、引き分けも含めて行われるゲームの回数の期待値は「M * 100/(100-C)」回である。

あとは、勝ち負けが決まるようなゲームの回数がM回であるような確率を求められれば、上記の回数に掛けることで全体の期待値を求められる。


勝ち負けが決まるゲームで考えた場合、N回以上2N回未満の回数で勝負が決する。
これをM回と置くと、M回のうち、高橋くんが勝つケースでは、M回目は高橋くんである必要があり、M-1回目までで高橋くんがN-1回勝っている必要がある。
これは、組み合わせを用いて、{M-1}_C_{N-1} * (A/(A+B))^N * (B/(A+B))^{M-N}の確率で起きる。
青木くんについても同様で、{M-1}_C_{N-1} * (B/(A+B))^N * (A/(A+B))^{M-N}の確率で起きる。
よって、上記の2つを足し合わせたものが、M回で勝負が決する確率になる。

あとは、MをN~2N-1でループを回し、Mの時の確率と上記の期待値をかけたものを足し合わせていけばよい。
(mod_conv, mod_inverse, mod_powあたりが必要)

反省

コンテスト中はO(N^2)な解法から計算量を落とそうと考えて、ごちゃごちゃいじっていたら終わってしまった。。。

O(N^2)の解法は、
E_{x,y} := 高橋くんの勝ち数がx、青木くんの勝ち数がyのとき、ゲームの残り回数の期待値
と考えると、

E_{x+1,y} <- E_{x,y} -> E_{x,y+1}
               ↓↑

のような遷移になっていて、再帰的に、
E_{x,y} = 100/(100-C) + A/(A+B) * E_{x+1,y} + B/(A+B) * E_{x,y+1}
E_{N,*} = E_{*,N} = 0
E_{0,0} = ?
と書ける。
(引き分けの部分も依存してしまっていて分離できなかった)

ABC128 F. Frog Jump

問題

N個の蓮が一列に並んでおり、0~N-1まで番号がついている。
最初、0の蓮におり、以下の手順に従ってゲームを行う。

1. 正の整数A, Bを決める。得点は最初は0。
2. 現在の位置xとして、y=x+Aとする。xの蓮を消してyに移動する
このとき、y=N-1ならゲーム終了。そうでなく、yの蓮があるなら得点s_yを得る。yの蓮がない場合は得点を10^100減らして終了。
3. 現在の位置xとして、y=x-Bとする。xの蓮を消してyに移動する
このとき、y=N-1ならゲーム終了。そうでなく、yの蓮があるなら得点s_yを得る。yの蓮がない場合は得点を10^100減らして終了。
4. 手順2に戻る

最終得点をできるだけ大きくしたい場合、最終得点はいくらになるか。

制約

  • 3 <= N <= 10^5
  • -10^9 <= s_i <= 10^9
  • s_0 = s_{N-1} = 0

解法

問題文から以下がわかる。
経路の動きとしては「0 -> A -> A-B -> 2A-B -> 2A-2B -> ... -> N-1」のように推移する。
また、手順3ではN-1に達することはできないので、手順2の時にN-1にたどり着くように終わらないといけない。よって「(x+1)*A-x*B = N-1」となるようなxがある。

単純にA,Bをループで回すとxはO(1)で決まるが、スコアの計算にO(N)かかってしまう。全体としてはO(N^3)で間に合わない。

ここで、「(x+1)*A-x*B = N-1」を変形して「x(A-B)+A = N-1」と考えて、xとA-Bでループを回すことを考える。(これに気付くためにはAとx、Bとxとかも考えていればたどり着ける?)

C=A-Bとして、これはループを回すとして固定して考える。
x=1からループを回すと、AとBが決まるので、どういう蓮を通っているかを表示してみると、左右からCずつx個取るような対称形の法則性がでてくる。

この法則性を活用すると、取る蓮が同じになるようなものをまとめて、かつ、xを順番に増やすことで効率的に求めていける。

気を付けることとしては、
・x*Cが範囲を超えないようにする
・A,Bの条件をちゃんと満たすかチェックする
・左右から取っていったときに、すでになくなった蓮だった場合は条件を満たせないので、すでに取った蓮かどうかを記録しながらxを増やしていく

Cとxのループは、ΣN/iのような形になるのでO(NlogN)の計算量になる。

ABC128 E. Roadwork

問題

東西に無限に続く1本の大通りがあり、数直線とみなせる。
大通りでN回の工事が行われ、i番目の道路工事はSi-0.5からTi-0.5の時刻にXi地点を通行止めにする。
Q人の人が座標0におり、i番目の人は時刻Diで出発し、速度1で進む。
しかし、工事中の通行止めの地点に到達するとそこで止まる。
各人の進む距離を求めよ。無限に進む場合は-1を返せ。

制約

  • 1 <= N, Q <= 2*10^5
  • 0 <= Si < Ti <= 10^9
  • 1 <= Xi <= 10^9
  • 0 <= D1 < ... < DQ <= 10^9
  • 同じ地点で複数の工事が時刻が重なるように実施はされない

解法1

各工事について、いつ出発すればその工事地点で止まることになるかを考える。
これは簡単で、[Si-Xi, Ti-Xi)の時間に出発する人がこの工事地点で止まりうる。
ただし、複数の工事がある場合は、一番Xiが小さいところで止まる。

範囲更新できればよいので、座標圧縮したものに対して遅延セグメント木でXiが大きい方から入れていき、小さい時刻から人の出発時刻とセグメント木の値を見比べて答えていけばよい。

(座圧の時に、各人の時刻も一緒にいれておくと、簡単に問い合わせできる)

解法2

遅延セグメント木ではなく、setを使って求めることができる。

setに各人の時刻を入れておき、工事のXiが小さい方から、[Si-Xi, Ti-Xi)の範囲にある人を取り除いていけばよい。
Si-Xiをlower_boundで探して、イテレータを回してTi-Xi未満の人をeraseしていく。

類題

atcoder.jp

Chokudai SpeedRun002 J. GCD β

問題

整数のペアがN組あり、i番目の整数のペアは(Ai, Bi)で与えられる。
すぬけくんは各ペアからちょうど1つずつ整数を選んで、選んだN個の整数の最大公約数として考えられる最大値が何になるか知りたい。

制約

  • 1 <= N <= 5*10^4
  • 1 <= Ai, Bi <= 10^9

解法

最初にA1かB1の約数の集合を考えると、A2かB2の約数の集合と共通する約数のみを残していくイメージをすると、どんどん集合サイズが減っていくイメージになる。
なので、結局、最初のA1かB1の約数の集合が最大サイズで、この約数だけが答えの候補になっている。
10^9以下の整数の最大の約数の数を持つものでも1344個程度(高度合成数)しかないので、A1とB1の約数を列挙して合わせて、その約数から条件を満たせるものを選べばよい。

Chokudai SpeedRun002 I. カツサンドくんβ

問題

N種類の食べ物があり、食べ物iの体力がAi、攻撃力がBiで与えられる。
この食べ物同士を戦わせ、最強の食べ物を決めたい。

最強の食べ物は、以下のような対戦を行ったとき、どの他の食べ物と戦っても勝利できるような食べ物とする。

食べ物iと食べ物jが対戦する場合、以下のような流れで行われる。
1. 互いに攻撃する。このとき食べ物iの体力はBj減り、食べ物jの体力はBiだけ減る。
2. 体力が0以下になった食べ物が戦闘不能になる
3. いずれの食べ物も戦闘不能になっていない場合は1に戻る
4. 両方が同時に戦闘不能になったら引き分け、片方のみが戦闘不能ならもう片方を処理とする

最強の食べ物を求めよ。

制約

  • 1 <= N <= 2*10^5
  • 1 <= Ai, Bi <= 10^9
  • 入力される値はすべて整数

解法

最強の食べ物が存在する場合は、どう戦っても必ず勝つはずなので、N種類の食べ物が順番に現れて勝ち抜き戦をするような感じで求めればよい。
引き分けの場合は、いったんどちらかを選んでおく。
最後に勝ち抜いた食べ物が最強候補だが、引き分けの食べ物があったかもしれないので、最後に、他のすべての食べ物に勝てるかチェックすればよい。

解法2(未証明)

勝敗判定を考えると、iとjが戦った場合にiが戦闘不能になるまでのターン数は(Ai+Bj-1)/Bj)-1?回なので、iが勝つには「floor( (Ai+Bj-1)/Bj ) > floor( (Aj+Bi-1)/Bi )」である必要がある。
floorを外して小数考えると、整数部分が違う場合はただしく不等号比較ができているが、整数部分が同じ場合にfloorでは等号になるものが不等号の比較になってしまう。
これは、本当は引き分けなのに、どちらか優劣をつけることになるが、上記の解法でのいったんどちらかが勝ち残るのと同じ感じになる。
floorを外して小数で考えて、移項して整理すると「(Ai - 1)*Bi > (Aj - 1)*Bj」である必要がある。
したがって、(Ai-1)*Biでソートしたときに一番大きい値になるものが最強候補といえるので、他のすべての食べ物に勝てるかチェックして答えを求めればよい。

ABC127 E. Cell Distance

問題

N*Mのマス目のKマスに1つずつ駒を置くことを考える。
ここで、K個の駒が(x1,y1), ...., (xK,yK)と置かれるときの配置コストを
Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|)
とする。
駒のすべての配置の仕方のコストを考えたとき、その配置コストの総和を10^9+7で割ったあまりで求めよ。

制約

  • 2 <= N*M <= 2*10^5
  • 2 <= K <= N*M
  • 入力はすべて整数

解法

問題は、
Σ_{すべてのあり得る駒の配置} Σ_{i=1}^{K-1} Σ_{j=i+1}^K (|xi-xj| + |yi-yj|)
= Σ_{すべてのあり得る駒の配置} (すべての駒のペアについてそのマンハッタン距離を求めたときの合計値)
を求めよ、ということを言っている。

ある2つの駒が(xi,yi)と(xj,yj)に置かれる状況を考えると、この2つの駒がそこに置かれるような配置は、この2つ以外の駒がこの2か所以外に置かれる通りだけあり得るので、(M*N-2)_C_(K-2)通りだけ答えの中で出現している。
しかし、これを使って求めるのだとペアを決めるのにO(N*M * N*M)かかってしまうため、もっとまとめ上げて計算してあげる必要がある。


まず、マンハッタン距離の性質として、x軸とy軸は独立に求められるので、xだけを考える。(ただし、駒の配置は2次元のまま考える)

まとめあげとして、|xi-xj|を求めたいので2つの駒の距離に注目すると、この距離がdであるような場合を考える。
距離がdであるようなx軸の選び方は(M-d)通りあり、選んだ軸の左側と右側それぞれN通り置き方があり得るので、結局、(M-d)*N*N通りあることがわかる。(距離dは1~Mまで考えればよい)

したがって、求めたい値のx軸については以下のようになる。
Σ_{d=1}^{M} d * (M-d)*N*N * (M*N-2)_C_(K-2)
これをNとMをひっくり返してy軸についても同様に求めてあげれば答えが求まる。

計算量は、組み合わせの計算の部分が重くて実装方法次第だが、O(N*M)程度。

反省

  • 問題を誤読&制約を見間違っていた(N,Mと思ったがN*Mだった)
    • 制約はなんか同じような見間違いをしていた人が多かった模様
    • なんか問題読解にミスってることが最近多い気がするので、ちゃんと時間かけて読むようにする
  • 組み合わせ問題は、言い換えが重要なので、どういう言い換えをしているかなど知見を貯める

ABC126 F. XOR Matching

問題

以下の条件を満たす長さ2^{M+1}の数列aが存在するなら1つ構築せよ。

  • 数列aには、0以上2^M未満の整数がちょうど2つずつ含まれる
  • a_i == a_jになるi,jについて、a_i xor ... xor a_j == Kとなっている

制約

  • 0 <= M <= 17
  • 0 <= K <= 10^9

解法

明確にわかる条件から抑えていく。

M=0のときは、K=0しかだめで、そのときの答えは「0 0」。
M=1のときは、同じくK=0しかだめで、答えは「0 0 1 1」か「1 1 0 0」。「0 1 0 1」のようなものは、0で挟まれる部分が1で、1で挟まれる部分が0になってしまう。

M=2の場合を考える。
まず、Kは2^M以上の場合、XORを取ってKが作れないので、構築できない。したがって、「K < 2^M」である必要がある。

M=2のときに現れる数字は、0 0 1 1 2 2 3 3の8つ。
実験として、これをnext_permutationで全通り試して、条件を満たすものを出力して観察すると、「Kを作って、それを両側から挟んでいるような形」が多く見受けられる。
具体的には、「X Y 0 K Y X」や「X Y K Y X」のような形ができている。

ここから、あるKについて、その両側を挟んでいくような形で考えると、同じ数字はxorを取ると0になるので、満たすことがわかる。
なので、Kを置いてその両側を挟むように他の数字を対象に置いていけばK以外の数字は条件を満たす。
ただ、Kが1つ余っており、これをどこかに置く必要があるが、すでに置いたKの両側には、0から2^M-1までの数字でKを除いた数字が並んでおり、このxorを考えるとKになっている。
(「0から2^M-1までの数字でKを除いた数字のxor」とKのxorが0にならないといけないため、Kであることがわかる)
したがって、「Kの両側に対称となるようにK以外の数字をならべ、最初か最後にKを置いたもの」は条件を満たすため、これを返せばよい。

Google Code Jam 2019 Round 2 A. New Elements: Part 1

0完だった。。。(点数分布的にAのlargeは通さないとACDのsmallだけでは無理そうだったので時間をかけてたけどsmallすら通せなかった・・・)

問題

CodiumとJamariumという新しい元素を研究しており、これらの原子量に関する統計を調べたいと思っている。
過去の研究より、これらの原子量は厳密に正の値であることはわかっている。

今、N個の分子が与えられている。この分子は上記の2つの原子のみが何個か組み合わさって構成されており、i番目の分子のそれぞれの原子の構成要素数が(Ci, Ji)で与えられる。
分子の重さは、原子量の合計値で表される。

最初の調査として、原子量によってはこの分子を重さ順に並べたいと思っており、「厳密に増加するように並べる並べ方が何通りありえるか?」を知りたい。何通りあるか、答えよ。

例:分子が「(1,1), (2,1), (1,2)」の3つの場合、
Codiumの原子量がJamariumの原子量よりも重い場合は、(1,1), (1,2), (2,1)。
Jamariumの原子量がCodiumの原子量よりも重い場合は、(1,1), (2,1), (1,2)。
同じ原子量の場合は、(2,1)と(1,2)が同じ分子の重さになってしまうため、厳密に増加しないため、条件を満たさない。

制約

  • 1 <= T <= 100
  • 1 <= Ci, Ji <= 10^9
  • 与えられる分子で構成要素が同じものはない
  • 2 <= N <= 300
  • 制限時間は20秒以内
  • メモリ制限は1GB

解法

元々の原子量がわかっていないので、それを変数として考えたい。
それぞれの原子量を(x, y)と考えてもよいが、片方の原子量がXとして、もう片方はその比率wをかけたX*wで考えると、定数Xが与えられた下では1変数wだけで扱える。
そこで、Codiumの原子量をXとしてJamariumの原子量をX*wとして考える。


i番目の分子の重さは、「Ci * X + Ji * X * w = X * ( Ci + Ji * w)」と書ける。
問題文の条件から、0 < wである。
ここで、各分子の重さを横軸w、縦軸分子の重さとした2次元平面にプロットすると、各分子の重さは直線で表現でき、wがw'の場合の順序はグラフのw=w'と直線の交点(下から上にぶつかる順)になる。

ここで、プロット図を観察すると、交点の位置は同じ重さになっている点なので、上記の条件を満たさない、かつ、その左右で分子の重さの大小関係が必ず入れ替わっているということがわかる。
ただし、Sampleの#2のような交点が同じwで2つ以上ある場合やw=0の点で交点がある場合もあるので、ユニークや0になる場合を含めずにカウントしてあげれば、「その交点があるwの数+1」の領域が並べ方の数になる。

2つの直線の交点は、Xは関係しないので直線を「Ci + Ji * w」とすると、
y=ax+bとy=cx+dの交点はa!=cの時w=(d-b)/(a-c)になるので、それを使えばよい。
小数で扱うと誤差が怪しいので、有理数でカウントする(gcdなどで既約にして扱えばよい)。

反省

  • 原子量の重さが(1,1), (1,∞), (∞,1)だけを考えればよいのでは?とか答えは1か2だけ?とか最初に思ってしまって、その方向で嘘解法を生成してた(謎に先入観にとらわれすぎてた)
  • smallだけの解法も結構難しい、、、

Google Code Jam 2019 Round 1B C. Fair Fight

問題

N種類の異なる武器が2つずつ並べてある。
あなたは審判で、まず(L,R)の範囲を指定する。
対戦者のCharlesとDelilaは、その範囲内の武器の一つを選んで対戦を行う。
また、それぞれ人の武器の熟練度がCiおよびDiで与えられ、それぞれ範囲内で一番熟練度が高い武器を使って戦うことがわかっている。

審判として、フェアな戦いとなるようにしたいので、選んだ武器の熟練度の差が高々Kとなるような(L,R)の選び方をしたい。そのような範囲の選び方はいくつあるか?

制約

  • 1 <= T <= 100
  • 0 <= K <= 10^5
  • 0 <= Ci, Di <= 10^5
  • 制限時間は30秒以内
  • 8ケースがN = 10^5、それ以外は1 <= N <= 1000

解法

あるiが必ず含まれるような範囲を考える。
このとき、範囲はざっくりと以下のような形になっている。

[条件を満たさないLの範囲][条件を満たすLの範囲][条件を満たさないL,Rの範囲(iを含む)][条件を満たすRの範囲][条件を満たさないRの範囲]

各範囲は、0個かもしれないことに注意。

このとき、iを必ず含むような範囲の個数は「(条件を満たすLの範囲)の個数 * (条件を満たすRの範囲)の個数」で求められる。


すべてのiについて求めることを考えると、上記の範囲をO(logN)程度以下で求めたい。
そこで、二分探索で上記のそれぞれの範囲の境界を見つけることを考える。

LとRはそれぞれ同等の方法で求められるので、Rについて考える。
次のように3つの条件に分けて考える。
(1) max(Ci, ..., Cj) <= Ciを満たす範囲
(2) max(Di, ..., Dj) <= Ci+Kを満たす範囲
(3) max(Di, ..., Dj) < Ci-Kを満たす範囲

iからjの累積和をsum(0,j)-sum(0,i-1)で求める様な感じで、「(2)かつ(1)の範囲」から「(3)かつ(1)の範囲」を引くことで、上記の「条件を満たすRの範囲」の個数を求めたいが、それぞれのmax値はセグメント木などでO(logN)で求められるので、十分高速に求められる。

また、Ciが同じ値の場合などで重複してカウントしてしまう可能性があるので、(1)で範囲を求めるときに、すでに計算を行った領域を使わないようにしたい。
これは、Ciが大きい順からiを処理していき、Ciが同じ場合は、iが小さい順から処理して、Lの(1)の計算時に前のところを含まないようにしてあげればよい。

Google Code Jam 2019 Round 1B B. Draupnir

問題

「X-day ring」というものがあり、これは、X日ごとに分裂し、2倍の個数になるリングである。
最初は、1-day ringから6-day ringまでの6種類のリングがそれぞれ何個か(0個以上100個以下)ある。

今、1日目から500日目までのいずれかの日でのリングの合計数を2回だけ問い合わせることができる。
ただし、数が大きくなりすぎるため、2^63で割ったあまりが返ってくる。

最初の日(0日目)にあったリングのそれぞれの個数が何個だったかを答えよ。

制約

  • 1 <= T <= 50
  • 問い合わせ回数W = 2

解法

何日か経つと、リングの個数がかなり大きくなることがわかる。
また、2の累乗の倍数のいずれかになるため、0日目のi-day ringの個数がRiとすると、「(2^x) * Ri」のような形で書くことができる。

ここで、数が大きくなりすぎた場合、2^63で割ったあまりが返ってくることから、2^xの部分が2^63以上になったら2^63の倍数となるため、Riに関する要素が合計数に含まれなくなる。

また、0日目のリングの個数は100個以下であることがわかっているので、7bit以下で表現でき、「(2^x) * Ri」のxの部分がうまく7以上はなれるような日が見つけられれば、ビット部分からRiを求めることができる。

なので、「1-dayから3-dayが2^64の倍数となるような個数、かつ、4-dayから6-day ringが7bit以上離れるような日」で4,5,6-day ringの個数を求め、「1-dayから3-dayが7bit以上離れるような日の合計値から4-dayから6-day ringの個数を引いたもの」から1,2,3-day ringの個数を求めれば、0日目にあったリングの個数をすべて求められる。

Google Code Jam 2019 Round 1B A. Manhattan Crepe Cart

問題

グリッドがあり、各交差点は0からQまでの番号の組で表現できる。
今、P人の人が交差点に立っており、それぞれ、東西南北のいずれか一方を向いている。
各人は、向いている向きの方向に1交差点進んだ領域のどこかの交差点に用事があることがわかっている。(例えば、(Xi,Yi)で北を向いている場合は、北をy軸の正方向とすると、y>Yiとなる領域の交差点のどこかに用事がある)

今、各人の用事がある可能性がある領域で一番人数が多い交差点を見つけたい。
ただし、同じ人数の場合は、一番南西にある交差点を答えよ。

制約

  • 1 <= T <= 100
  • 1 <= P <= 500
  • 20秒以内
  • Q = 10^5

解法

2次元領域だが、各軸は独立に考えることができる。
なので、各軸についてimos法などで範囲更新して、一番数が多いところを見つける。
あとは、それぞれの数が多いところの和が2次元領域でも一番数が多いところになっているので、そのなかでも一番南西となる地点を答えればよい。

Tenka1 Programmer Contest 2019 D. Three Colors

問題

N個の整数aiが与えられる。
この整数に赤、緑、青のいずれかの色を塗る。
このとき、以下の条件を満たすような塗りかたの通り数を998244353で割ったあまりを求めよ。
「それぞれの色で塗った整数の和をR,G,Bとするとき、三辺の長さがそれぞれR,G,Bであるような正の面積の三角形が存在する」

制約

  • 3 <= N <= 300
  • 1 <= ai <= 300

解法

三角形が正の面積を持つ条件は、「三辺のどれか一辺が他の二辺の和より長い」と言える。
三辺の和は整数の全部の和で得られるので、和をSとすると、「すべての辺は長さ1以上で、一番長い辺の長さ < S/2」であればよい。

これを直接求める代わりに、余事象・包除原理っぽく考える。
求めたい通り数は、
(全塗りかた) - ( R>=S/2 ) - ( G>=S/2 ) - ( B>=S/2 ) + (R>=S/2かつG>=S/2) + (R>=S/2かつB>=S/2) + (G>=S/2かつB>=S/2) - (R>=S/2かつG>=S/2かつB>=S/2)
で求められる。


塗りかたは3色のいずれかなので、全塗りかたは3^N。
対称性からGとBの計算はRと同じなので、「R>=S/2」と「(R>=S/2かつB>=S/2)」はそれぞれ求めたものを3倍にすればよい。
「R>=S/2かつG>=S/2かつB>=S/2」はそのようなのは作れないので0通り。

「R>=S/2」は、dp[i][j]:=i番目までで赤に塗った整数の合計がjとなるような通り数、を求めて、dp[N][S/2以上]の合計を求めればよい。
(更新式は、GまたはBを選んだ場合「dp[i+1][j]+=2*dp[i][j]」、Rを選んだ場合「dp[i+1][j+v[i]]+=dp[i][j]」で遷移すればよい)


「(R>=S/2かつB>=S/2)」は、それぞれが等号の場合しか成り立たないので、Sが2で割り切れるときのみ考慮する。
これもdp[N][S/2]の通り数で求められる。

エクサウィザーズ2019 C. Snuke the Wizard

問題

N個のマスが並んでおり、各マスには1体のゴーレムと1文字が書かれている。
ここで、呪文を唱えると、ある文字の書かれたマスにいるすべてのゴーレムを右か左に1マス移動させることができる。
マスの外側に移動させられたゴーレムは消滅する。
Q回の呪文が与えられるので、最終的にマスに残っているゴーレムの数を答えよ。

制約

  • 1 <= N, Q <= 2*10^5
  • 文字は英大文字のみ

解法

あるマスxにあるゴーレムが左側から消滅する場合、マスx-1にあるゴーレムも(通過するはずなので)必ず左側から消滅する。(右側も同様)
なので、消滅するか否かを二分探索で位置を求めればよい。

反省

本番中は、両端から消滅ゴーレムは連続するのは気づいたけど、呪文を逆順にして消滅する範囲がどこまでか?を見つける様な方法でアプローチしてしまった。
これの場合、

2 2
AB
A R
A L

のケースでは、1つ目のマスのゴーレムが落ちる様な計算をしてしまうが、そのゴーレムは呪文1で2つ目のマスに移動していてゴーレムがないので、消滅するゴーレムはない。
なので、消滅しない範囲に移動したかどうかも同様な感じで求めればいいか?と提出したけど、両端からの範囲が重なるようなケース

2 3
AB
B R
A R
A L

など、いろいろ嘘だった。

Topcoder MM108 CrosswordPuzzler

概要

1週間マラソンはきつい。
最終順位は、20位(58人参加)で、結構良かった。

問題

W*Hのグリッドと辞書(単語の集合)が与えられるので、グリッド上に単語を敷き詰めたい。
このとき、グリッドに敷き詰めたときに、縦方向か横方向に2文字以上が並んでいる場合、必ず辞書にある単語になるようにしなければならないし、2回以上同じ単語がでてくるようにはしてはいけない。
スコアは、フィボナッチ数列fib(x)を用いて「Σ_{グリッドに出現する単語i} fib(i)」とするとき、スコアができるだけ高くなるようなグリッド敷き詰めを返せ。

最終的に提出したアプローチ


  • ベースはビームサーチ
    • ただし、計算時間の都合で、グリッドのサイズでパラメータを調整
    • 単語は、真ん中付近(サイズが小さかったら微妙にずらしたものも候補に入れた)
  • 評価関数は「単語スコア合計+文字を置いていないマスの数-使ったマス数」
    • お気持ちは、重なりが多いほどよさそうと思ったので、できるだけマスを使わずにたくさん置いた方がいい、という感じ
    • 単純なスコアにしてしまうと、終盤までスコアに差が出ずに、ビーム幅を必要としそうだったので、できるだけ序盤でも差がでるようにしたかった
  • 辞書は、長さ順にkグループに分け、順番にビームサーチで最適化するようにした
    • 単語数が減るので、最適解が得られない可能性があるが、計算量が減らせて、辞書サイズが多くてもまわせた

振り返り

1週間マラソンで、土日が腰痛でダメで何も手を付けられなかったのがかなり痛かった。

方針決め

これまでのマラソンの反省として、「最適解の形がどんな形か?」のイメージをミスるとお話しにならないと思ったので、ざっくりでも最適解の形を考えた。

具体的な形まではわからなかったけど、

  • 長い単語をできるだけ使う
  • 単語がクロスしている方が、少ないマスで表現できるので、よさそう

は間違いなさそうで、クロスを多く作るような形を目指すことに。

(最初の時点での理想イメージとしては、以下のような図でいくつか歯抜けになるようなものなんじゃないか?を考えていた)
f:id:phyllo_algo:20190311005756p:plain

最初は、焼きなましが適用できないか?と考えていたけど、単語を消したときの処理が面倒そう、と思ってビームサーチ方面で考えることにした。
(この時点で、最適解はぐちゃぐちゃ絡み合ったイメージを持っていたので、greedyな解は無理では?と思って除外してしまっていた)

面倒そうというのは、辞書が{aaa,ccc,bacb}の場合、

-a--
-a--
bacb
--c-
--c-

と置いて、bacbを消した場合、acを残してもacが辞書にないのでinvalid、acも消してもaa,ccがinvalidになるので、invalidを許すか、invalidを許さない場合は連鎖的に単語を削除していくイメージ。
invalidは最後まで残すと解消が無理そうだし、invalidを許さない場合、単語の連鎖が多くなりそう、と思ってあきらめた。
(終了後、onigiri(utmath)さんとの感想戦で「消せないなら消さない」というのもあるよね、というアイデアは考慮できていなかった)

テスター、ビジュアライザ

今回、testerがエラー出力を握りつぶしていたり、visualizerが付いていなかったので、デバッグが非常につらく、途中からc++で書き直したりしてた。

visualizerはなかったので、テキスト出力で見てたけど、縦長になってしまったり、クロスしている文字がどこなのか見にくく、ちゃんと整形して表示するものだけでも作るべきだった。

(結局、終わってからビジュアライザを作ったらそんなに時間かからずできたので、作るべきだったかも・・・)

ビームサーチの調整

ビームサーチをやろうと思ったら、結構生成される近傍が大きくなってしまって探索空間が大きそうというのにハマる。

妥協案として、真ん中付近に一番長い単語を置いて、そこからできるだけ長い単語をクロスするように設置していく(クロスできないならできるだけ長い単語を適当に置く)方法を試す。
結局、これ以外の方法などは時間がなくて試せなかった。

感想戦で、「いうほどクロスが多くない」という話が出ていて、ビジュアライザを作っていれば気づけたかもしれないと思う・・・

パラメータの調整

単純に上記の探索だと無駄な探索も多くて時間がかなりかかっていたので、ある程度時間内に終わるよう調整を考えた。

一つ目は、長さが小さい単語は使う必要があまりないor後で設置すればよさそうかもと思い、辞書を長さごとにグループ分けして、計算量を減らすことを考えた。

二つ目は、サイズが大きすぎるときのパラメータ(ビーム幅や辞書の分割数など)を調整してた。けど、あんまりやりたくなかったので、適当に時間に間に合いそうな値にして提出して、結局最後までそのままだった。。。

その他

盤面や辞書の生成ルール的に、「大きいケース」と「小さいケース」に偏りがあると思って、見ていた。
計算してみると、だいたい、マスのサイズが1000以下になるのが63%ぐらい、1000より多くなるのが37%ぐらいで、半分以上がマスのサイズが1000以下の小さいケースのようだった。

辞書サイズも小さいので、できるだけ小さいケースは十分な探索をできるように調整したかったけど、最終提出には入れられなかった。

反省

  • アプローチ
    • 今回は様々な手法が有効だったようで、
      • greedyに単語(またはフレーム)を置いて、それをランダムに繰り返す感じ
      • より多くの交差、より長い単語が最初になるような多くのrandom searchを試す
      • 焼きなましで配置や追加削除を試す(+様々な工夫)
      • 市松模様っぽく単語を配置しつつ、できるだけ単語を串刺しにする感じを焼きなましする
      • など
  • visualizer

ビジュアライザ

終わった後で、ビジュアライザを作った。
GitHub - jetbead/TopCoderMM108_Visualizer: Topcoder MarathonMatch 108 Visualizer

課題意識としては、

  • 最終状態の出力ではなく、焼きなましやビームサーチなどの途中状態も見れるようにしたい
  • ファイルに書き出す方法だと膨大な量になってしまったり、読み込み面倒なので、できるだけC++で完結させたい
  • macで手頃で使えるのにしたい

というのがあった。

QtやGTKなどはやや大がかりすぎるような気がして、OpenSiv3Dは新しめのコンパイラを必要とすることから、一番手頃そうなSDL2を試してみた。(「ゲームプログラミングC++」という本でも使われていたのを見たので)
悪くなさそうなので、他の手段も調べつつ、いろいろ使ってみたい。(できれば、visualizerで必要な要素をまとめたい)

第3回RCO日本橋ハーフマラソン予選 参加記

概要

第3回RCO日本橋ハーフマラソン予選に参加してみた。
atcoder.jp

結果は、A問題が102位、B問題が45位の総合67位でした。(結構善戦できたと思う)

問題

A. ツーリストXの旅行計画

N個の都市を1度だけずつ順番に巡って最初の年に戻ってくるようなルートを考える。
都市間の移動距離をの分散ができるだけ小さくなるようなルートを見つけよ。

N = 200
0 <= x_i, y_i <= 500

B. ファーマーXの収穫計画

N*Nの区画の庭があり、i行j列目の区画にA_ijの品質の野菜がある。
各区画からは1度だけ野菜を収穫できる。

次の操作をX回実行できるとき、収穫する野菜の品質の合計値をできるだけ大きくなるように操作の計画を立てよ。

  • 手入れ:選んだ区画の品質を1増やす。収穫済みなら何もしない
  • 収穫:選んだ区画とその周辺の条件を満たす野菜を収穫する
    • 選んだ区画の野菜が品質Kのとき、まだ収穫されていない隣接する品質がKの野菜をまとめて収穫できる
    • ただし、まとめて収穫する野菜の数がK個以上でないと収穫できない。K個未満なら何もしない

N = 50
M = 2500
1 <= A_ij <= 9

最終的に提出したアプローチ

最終提出の解(input_1.txt)

f:id:phyllo_algo:20190213015559p:plain
rcohalf3a
f:id:phyllo_algo:20190213015654p:plain
rcohalf3b

  • A問題
    • 点swapの焼きなまし
  • B問題
    • 収穫を目指す品質をxとして、品質y ( < x )のものをxまで育てることを考える
    • 上記をやったとして、できるだけ多く収穫できるものからgreedyに取る
    • xを9から1まで、yはいくつか探索して、最終的に良いスコアのものを返す

時系列での振り返り

進め方の方針
  • A問題1時間、B問題1時間を使う
  • 残り2時間はA,Bの進捗具合で決める
開始~1時間
  • 問題を読む
  • 焼きなましが有効そうなのは見てわかるが、TLEが2秒で十分探索できるか不安
  • とりあえず組んでみてどの程度スコア行くか見てみる
  • 近傍はとりあえず2点swap、細かい高速化はあとで
  • そんなに悪くなさそう?
  • 一旦提出
1時間~2時間
  • 問題を読む
  • 方針が難しそうなので、greedy解をとりあえず考えてみる(以下考えてたアイデア)
    • 3x3枠とかで全部9にするとか?
    • 区画をすべて1本の線でたどるようなものを作ってどうとるのが最適化考える?
    • グラフで考えてクラスカルっぽくとることはできないか?
  • 9をできるだけ取りたいが、コストが小さくとるために7とか8を育てて9にできるならうれしい
  • いったん7と8を9に育てたとしてどの程度の塊ができるか見てみる
  • 結構塊ができてる
  • 結局全部を収穫するのは無理なので、ある数値以上を収穫したい品質まで育てて、取れるものだけ取る、方針でいくことにする
2時間~3時間
  • Bの進捗がまずいのでBにいったん1時間使うことにする
  • とりあえず適当に組む
  • 品質9で収穫するのに7以上を育てたほうがいいのか、6以上を育てたほうがいいのかなど、細かく考えるとうまい実装を考えないといけなそう
  • とはいえ、適当にやってもそんなに悪くない解にいけそうなので、いったん収穫したい品質ごとに独立に計算するように実装
  • 一旦提出
3時間~3時間半
  • 提出してみると全然時間を使っていない
  • 上記のパラメータをいろいろ調べてみるのはありかも
  • 実装を変えようと思ったけど、時間が厳しいので、途中でやめて簡単にできるところだけにしようと方針転換
  • 下限だけいくつか変えてみるのを試してみるとちょっと良くなりそう
  • B再提出
3時間半~終了
  • Aの1位のスコアがヤバいことになってる
    • 逆算してみると平均分散が10を切っているよう
  • 近傍?チューニング?バグ?そもそも別方針?などテンパりつつどうするか考える
  • 近傍をいじるのはやや大変だと思うので、とりあえず時間を延ばして実行して温度調整で様子を見る
  • あんまり上位を狙えるものではない
  • 近傍は2点swapだと4辺変化してしまうので、普通に2辺swapにするだけでやや良くなるだろうけど、どんなもんか
  • 別方針としては、あんまり大きくない辺のみを使って計算することで無駄な辺を考えなくて済むようになる?
  • 辺を禁止する方はすぐできそうだしやってみる
  • うまくいかなった
  • 残り10分で2辺swapに書き換えられるか
  • あー間に合わないー
  • 終了

反省

  • 焼きなましは近傍が大切というのは何度も経験してたはずなのに適当に組んでしまったのはいけなかった
  • 結局2optにして分散をO(1)計算にするだけで330万点ぐらいがでてしまった
    • 提出スコアは47万点
    • そもそも2optの実装がうまい方法を自力で出せなかったので時間内に実装できても140万点ぐらいだった模様
  • 近傍は小さいのを最初から選択すべき
    • 今回だと3optみたいなやや重でもよい近傍を選べるなら有効だったよう
    • また、今回みたいなのは、辺スワップはreverse操作があって重いので、undo操作ではなく、スコア計算を先にしてundoしないとわかってからreverse操作をするような実装にすべき
  • Bの方は他の人を見てもそんなに大筋は外していない方針だったのでよかった
  • コスパが悪いものを取らない」はすぐに入れられた要素だったのに入れられてなかったのは悪かった