phyllo’s algorithm note

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

ABC137 E. Coins Respawn

問題

1からNまで番号がついたN頂点M辺の有向グラフが与えられる。
頂点1から頂点Nまで辺を辿っていくことを考える。
辺iは通過するのに1分かかり、通るたびにコインがCi枚もらえる。
頂点Nにたどり着いておいてあるボタンを押すと「それまで回収したコインの総数から経過時間*P枚を引いたコイン枚数」が得られる。
(コインが足りない場合は0枚になる)
得られるコインが最大になるように行動した場合、何枚得られるか?
最大値が存在しない場合は-1を返せ。

制約

  • 2 <= N <= 2500
  • 1 <= M <= 5000
  • 1 <= Ai, Bi <= N
  • 1 <= Ci <= 10^5
  • 0 <= P <= 10^5
  • 有向グラフは1からNまで到達可能

解法

最長経路は辺のコストの正負を逆転させることで最短経路と同じ要領で求められる。
ただし、ループがあると最大値が無限に大きくできてしまうため、それを検出できるベルマンフォードで適用を考える。

単純に適用しようとすると、サンプルにある通り、「頂点1からたどり着けない頂点」、「頂点Nにたどり着けない頂点」も含めて閉路を検出してしまう。
なので上記のたどり着けない頂点をチェックして、その頂点を除いたグラフで適用すれば良い。

反省

「たどり着けるか?」の頂点のチェックにdfsではなくbfsで書いてしまったが、

queue<int> que;
while(!que.empty()){
  int x = que.front(); que.pop();
  visit[x] = true;
  FOR(it, g[x]){
    if(visit[it->dest]) continue;
    que.push(it->dest);
  }
}

のように書いてしまうと、O(N^2)で、
1->2, 1->3, ..., 1->N, 2->3, 2->4, ..., 2->N, ..., N-1->N
のようなグラフでTLEになってしまう。

AGC036 A. Triangle

問題

整数Sが与えられる。以下の条件をすべて満たす6つの整数X1,Y1,X2,Y2,X3,Y3を1組求めよ。

  • 0 <= X1, Y1, X2, Y2, X3, Y3 <= 10^9
  • 二次元平面上の3点(X1, Y1), (X2, Y2), (X3, Y3)を頂点とする三角形の面積がS/2

制約

  • 1 <= S <= 10^18

解法

変数が多いので、1点を固定して考える。(X1, Y1) = (0, 0)とする。

ここで、三角形の面積を求める方法を調べると、「直交座標による式」が出てくる。
三角形 - Wikipedia

面積 = |X2*Y3 - X3*Y2| / 2

これが2点の関係式になるので、これを満たす2点を探す。

例えば、(X2, Y2) = (10^9, 0)としてみると、S = 10^9*Y3である必要があるが、Sが10^9で割り切れないといけない。
しかし、(X2, Y2) = (10^9, 1)とすると、S = 10^9*Y3 - X3となり、これはY3を「Sを10^9で割った切り上げ」とすると、X3 = 10^9*Y3 - Sとなる。

これは以下のようになっている。(解説放送より)
f:id:phyllo_algo:20190722234447p:plain

ABC134 F. Permutation Oddness

問題

1からNまでの順列pの「奇妙さ」を「Σ_{i=1}^N |i - p_i|」と定義する。
奇妙さがkであるような順列の個数の10^9+7で割った余りを求めよ。

制約

  • 1 <= N <= 50
  • 0 <= K <= N^2

解法

「1からNを並べたもの」と「順列p」のペアを考える。
順列pでの数字を線でつないで表現すると以下のように書ける。
f:id:phyllo_algo:20190722221152p:plain
この場合、右側の順列pは{3, 1, 4, ?, ?}に対応する。

ところで、問題の「奇妙さ」は、「数字の間に引いた線」と「ペアの線」の交点(赤色の点)の数で考えることができる。
これを元にDPを考える。


そのまま考えると、つないでいない点を保持する必要がありそうでbitDPになりそうだが、以下のように考えると、点の個数だけ保持すれば良くなる。

状態は、
dp[i][j][k][l] := iペア目までで、まだつないでいない左側の点がj個、まだつないでいない右側の点がk個、ここまでの奇妙さの合計がlである順列の個数
だが、jとkは実は常に同じになり、片方だけで良いので、
dp[i][j][k] := iペア目までで、片側でまだつないでいない点がj個、ここまでの奇妙さの合計がkである順列の個数
となる。


遷移は、配るDPで考えると、dp[i][j][k]について、(i+1)ペア目をどうするかで4パターンありえる。

  1. 両方共、点を繋がない
    • 横線と交差する点は2*(j+1)個になるので、dp[i+1][j+1][k+2*(j+1)] += dp[i][j][k]
  2. (i+1)ペア目同士を繋ぐ
    • 横線と交差する点は2*j個になるので、dp[i+1][j][k+2*j] += dp[i][j][k]
  3. (i+1)ペア目の片方を、iペア目以前の繋いでない点のどれかと繋ぐ
    • 横線と交差する点は2*j個になるが、iペア目以前のどれに繋ぐかでj通り、どちら側かで2通りなので、dp[i+1][j][k+2*j] += dp[i][j][k] * 2*j
  4. (i+1)ペア目の両方を、iペア目以前の繋いでない点のどれかと繋ぐ
    • 横線と交差する点は2*(j-1)個になり、iペア目以前のどれに繋ぐかが左右でj通りずつあるので、dp[i+1][j-1][k+2*(j-1)] += dp[i][j][k] * j*j

初期値はdp[0][0][0] = 1通りで計算すればよい。
答えはdp[N][0][K]になる。


これは、箱根駅伝DP(箱根DP)とも呼ばれるらしい。
Hakone | Aizu Online Judge

yukicoder No.848 なかよし旅行

問題

N個の町がM本の道でつながっており、道の移動にかかる時間が与えられる。
今、2人が町1にいるが、T分以内に町Pと町Qを回って町1に戻ってきていなければならない。
町Pと町Qは2人のうちどちらか1人でも回ればよい。
ただし、道の途中で引き返すような行動はとれない。

2人はできるだけ一緒に行動したいが、最大で何分一緒に行動できるか?
不可能な場合は-1を出力せよ。

制約

  • 3 <= N <= 2000
  • 2 <= M <= 10^5
  • 2 <= P <= Q <= N
  • 1 <= T <= 10^9
  • 1 <= ある道の移動時間 <= 10^9
  • すべての町は町1から歩いていくことができる

解法

まず、全部一緒に回れるかどうかを考える。
1->P->Q->1と一緒に回る時間がT分以下だった場合、適当に待ち時間を入れることで答えをTにできる。

上記でない場合は、何分かの間、別行動が発生する。
別行動をしている時間をtとすると、答えはT-tになる。

ある頂点xまで行って、それぞれP,Qに別々に移動して、xに戻ってくることを考えると、x->P->xかx->Q->xの長い方の時間だけかかる。
しかし、例えば、x->Pが1、x->Qが10のような場合、x->Q->xの20だけかかるが、P->yが10、Q->yが1のようなyが存在する場合、x->P->yとx->Q->yが11ほどとなり、y->1が1->xと同じでもそのルートを通った方が短くなる。

したがって、x,yのペアをすべて確認し、t={x->P->yかx->Q->yの長い方}として、T-tで一番長いものを求めればよい。

反省

さっと思いつくgreedyの「同じ場所xに戻る」のが嘘解法だというのに気付くのが難しい、、、

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次元領域でも一番数が多いところになっているので、そのなかでも一番南西となる地点を答えればよい。