phyllo’s algorithm note

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

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の方は他の人を見てもそんなに大筋は外していない方針だったのでよかった
  • コスパが悪いものを取らない」はすぐに入れられた要素だったのに入れられてなかったのは悪かった

みんなのプロコン2019 D. Ears

問題

数直線上のある整数点から自由に左右の整数点に移動し、どこかの整数点で終わるような行動をする。
このとき、整数iについて、i-0.5の地点を通過したら、i番目の位置に石を1つ置く。

目標となるi番目の石の数A_iが与えられたとき、上記の行動を行った後で、目標の石の数にするために石を追加または除去することができる。
追加または除去する石の個数が最小となるように行動を行った時の、追加または除去する石の総数を答えよ。

制約

  • 0 <= A_i <= 10^9, (1 <= i <= 2 * 10^5)

解法

行動を行った後の石の形には法則性があり、
【0個】【0でない偶数個】【奇数個】【0でない偶数個】【0個】
のようなゾーンにわかれる(ゾーンがない場合もある)。

dp[i][j] := i番目がゾーンj(上記)だった場合の最小の追加または削除の回数
として、更新すればよい。

解法2

(コンテスト中考えていた方向性の解法で、一応通ったのでメモしておく)

行動を、ある整数iに注目すると、「左から入って右にぬける」「右から入って右にぬける」「左から入って左に抜ける」「右から入って左に抜ける」ような4パターンがあることがわかる。

ここで、右にぬけるようなパターンについてだけ考えると、i番目の地点で右に抜けるようなパターンの最小コストは、
dp1[i][0] := i番目で右から入り、0~i番目のどこかを通って、i番目で右にぬけた場合の最小コスト
dp1[i][1] := 0~i番目のどこかで入り、i番目で右にぬけた場合の最小コスト
を更新すれば、求められる。
(更新は、i-1までのdpの値から更新する場合とi-1までをすべて捨てて更新する場合を考える。A_i=0となる場合のコストに注意)

同様に、逆方向からdpすれば左にぬけるようなパターンについても同様に最小コストが求めらえる。(これをdp2とする)

あとは、ある地点iを境に左側を通った時の最小コストdp1[i][x]と右側を通った時の最小コストdp2[i][y]の組み合わせで最小となるなるものを見つければ、求められる。(dp2は通る向きを逆向きで考えれば等価)

その他

解法2の方の類題
D - 建物

ABC117 D. XXOR

問題

N個の非負整数A_iと、非負整数Kが与えられる。
ここで、f(X) = Σ (X xor A_i) (0 <= X <= K)という関数fを定義する。
この関数fの最大値を求めよ。

制約

  • 1 <= N <= 10^5
  • 0 <= K <= 10^12
  • 0 <= A_i <= 10^12

解法

関数fはビットごとに0にするか1にするかで関数の値を独立に求められるので、雰囲気、上から貪欲に求められそうに見える。
しかしこれは普通に嘘で、貪欲が適用できる場合というのは「選択しなかった場合の最終スコアが、選択した場合の最終スコアを超えない」こと(それを証明できること)が必要。
(今回の場合、Nが大きいケースなどで、下位ビットの方で大きい値が加算される可能性がある)


なので、ちゃんと(全)探索を考える。

今、i bit目を考えているとする。
i bit目を0にするか1にするかが選べるが、Kを超えてはいけないので、「そこまで決めたビットの値+(1< K」ならば必ず0にしなければならない。そして、次のbitを同様に探索すればよい。

逆に0でも1でも選べる場合、0にしたらそれ以降のビットはどう選んでもKを超えないので、下位のすべてのbitでスコアが高くなる方のビットを貪欲に選んでよい。
1にした場合は、次のbitを同様に探索すればよい。


実装は、

  • どこのビットを処理しているか: i
  • そこまで決めたビットの値: X'
  • そこまで決めたビットの分だけの関数のスコア: F'

を持ちながら再帰すればよい。

NIKKEI Programming Contest 2019予選 C. Different Strokes

問題

1~Nまで番号が付いたN皿の料理がある。
高橋くんがi番の料理を食べたときはA_iだけ幸福度が増し、青木さんがi番目の料理を食べたときにはB_iだけ幸福度が増す。
高橋くんから、交互に、2人とも「最終的に自分が得る幸福度の総和」-「最終的に相手が得る幸福度の総和」が最大化するように料理を選ぶ。
「最終的に高橋くんが得る幸福度の総和」-「最終的に青木さんが得る幸福度の総和」はいくつになるか。

制約

  • 1 <= N <= 10^5
  • 1<= A_i, B_i <= 10^9

解法

求めたい答えを数式で書いて変形するアプローチを考える。


高橋くんが取る皿の集合をX、青木さんの取る皿の集合をYとすると、
max( Σ_X A_i - Σ_Y B_i )
となる。
このままでは、XとYによって決まる変数だが、
max( Σ_X A_i + (Σ_X B_i - Σ_X B_i) - Σ_Y B_i )
= max( Σ_X (A_i + B_i) - (Σ_X B_i + Σ_Y B_i) )
= max( Σ_X (A_i + B_i) - Σ_すべて B_i )
= max( Σ_X (A_i + B_i) ) - Σ_すべて B_i
とすると、Yを消去することができる。

式の通り、A_i + B_i の和が最大になるようにXを選べばいいので、和でソートして交互に取っていけばよい。

ARC067 E. Grouping

問題

1からNまで番号がついたN人がいる。

  • どのグループも、そのグループに含まれる人数がA人以上B人以下
  • i人のグループの数をF_iとしたとき、F_iは0またはC以上D以下

このようなグループ分けが何通りあり得るかmod 10^9+7で求めよ。

制約

  • 1 <= N <= 10^3
  • 1 <= A <= B <= N
  • 1 <= C <= D <= N

解法

解説、解説放送の方法。


問題がややイメージしにくいので、具体事例を考えてみる。
例えば、「(1),(2),(5),(3,4),(6,7)」のようなグループ分けだった場合は、

グループ内の人数 グループの個数
0人 0グループ
1人 3グループ
2人 2グループ
3人 0グループ

のようになっている。
A,Bは表左の人数に関する条件、CDは表右のグループ数に関する条件を表しており、条件を満たすならこのグループ分けは1カウントに数え上げられる。


数え上げなのでdpを考えてみると、「グループ内の人数」と「それまでの確定した人数」を状態にした以下のようなdpが考えられる。

dp[i][j] := i人以下のグループのみでグループを作ったとして、その合計人数がj人であるようなグループ分けの通り数

漸化式を考えると、i-1までが求められていたとして、i人グループを作ることを考えると、グループをx個作る場合は、

dp[i][j] = Σ_x f(i,j,x) * dp[i-1][j-i*x]

ここでf(i,j,x)は「残っている人で、i人グループをx個作る場合のグループ分けの数」。


これはiとjとxでO(N^3)っぽく見えるが、xはグループの個数で、iが大きくなるほど作れるグループ数は少なくなり、xはj/i個までしか作れないので、これはO(N^2 logN)となる。
( O(N + N/2 + N/3 + ...) = O(N logN) )
したがって、f()が十分に高速に求められれば間に合う。


f(i,j,k)を求める。
N人中すでに(j-i*x)人はグループになっているので、残りの(N-j+i*x)人からi人グループをx個作ることになる。
各人は番号がついていて区別できるので、並びも考慮するイメージで、「(N-j+i*x)人からi*x人を並べる通り数 (N-j+i*x)_P_(i*x)」から、重複分の「グループ内での並びは関係ない分 ( i! )^x」と「グループ自体の並びも関係ない分 x!」を割ってあげた以下の式になる。

f(i,j,k) = (N-j+i*x)_P_(i*x) / { ( i! )^x * x! } = (N-j+i*x) ! / { (N-j)! * (i!)^k * x! }

MOD階乗、MOD累乗、MOD逆元でこれを求めてあげればよい。

その他

ベル数 - Wikipedia

A,B,C,Dの条件がない場合は「ベル数」と呼ばれる。

AGC029 B. Powers of two

問題

N個のボールがあり、i番目のボールには正の整数A_iが書かれている。
このとき、2つのボールを取り出してペアを作り、その数字の和が2ベキ(2^t)になっている場合、そのペアを取り除くことができる。
最大で何回ペアを取り除くことができるか?

制約

  • 1 <= N <= 2 * 10^5
  • 1 <= A_i <= 10^9

解法

大きい数字の方から注目すると、自身よりも小さい数字でペアを作ることになる場合、2ベキになる数字は一意に決まる(自身より大きい一番小さい2ベキになる)。

ある数字xについて、その数字以下のペアになれる数字yが存在する場合、「xを除いた集合」で「xとyを除いた集合」よりもペアを多く作れないならxとyでペアを作っておいたほうがよいが、ペア数は同数か少なくなるしかないので、結局ペアを作っておいたほうが良い。
したがって、greedyに、大きい方の数字からペアを作れたら取り除く、を繰り返していけば求められる。


c++の場合はmultisetで検索、削除などを簡単に実装できる。

  multiset<int> m;
  rep(i, N) {
    int a;
    cin >> a;
    m.insert(a);
  }
 
  int ret = 0;
 
  while (!m.empty()) {
    int x = *(m.rbegin()); //大きい数字から処理
    m.erase(m.find(x)); //(m.erase(x)にしてしまうと値xがすべて消えてしまう)
 
    ll p = 1;
    while (p <= x) p *= 2;
    int y = p - x; //ペアになれる数字は一意に決まる
 
    if (m.find(y) != m.end()) {
      m.erase(m.find(y));
      ret++;
    }
  }
 
  cout << ret << endl;

解法2

上記の解法の考察がやや自分の感覚では自身なかったので、もうちょっと無駄なことを本番では考えてた。


同じ数字のボールをまとめ上げた(数字, 個数)で考える。これをノードとみなす。
大きい数字のペアをその数字より小さい数字で作る場合は一意に決まることから、大きい数字のノードから小さい数字へのノードに辺を貼ると、これは森になっている。

ある木について考えると、ペアをできるだけ作ることを考えると、葉ノード側からできるだけペアを作るのがいいので、葉ノード側から処理してペアを作る。
最後に、2ベキな数字で残っているボールがある場合、同じ数字でペアが作れるので、それを加えれば答えが求められる。


反省

勉強不足と考察不足。ついでに実装の仕方がダメダメだった。
本番は、2ベキなボールは同じ値でしかペアになれない(嘘)、と思い違いして最初にコーナーケース的処理を入れてしてしまっていて通せなかった。。
すぐに反例が思いつくのに、間違っていないと思っている考察に対して疑うのは難しい・・・


greedy法の証明は典型らしいかも?(帰納的に考える)
「今、操作xをしなかった場合、残りの部分で操作xした場合よりスコアが高くならないならば、今、操作xをしたほうがよい」

ARC066 D. Xor Sum

問題

正の整数Nが与えられる。
ここで、2つの整数0 <= u, v <= Nであって、ある非負整数a,bが存在して、a ^ b = u, a + b = vとなるものが何通りあるか求めよ。
答えは1,000,000,007のあまりを答えよ。
上記の^はビットごとの排他的論理和を表す。

制約

  • 1 <= N <= 10^18

解法

まだイマイチ理解できていないところが残っているけど、とりあえずまとめ。
制約が非常に大きく、xorがビットごとの計算でもあるので、ビットの桁DPを考える。
以下、解説放送から。(下から桁DP)


問題がやや扱いにくいので、言い換えを考える。
a,bを用いた制約があるので、結局「(a xor b, a+b)が何通りあるか?」という話でであるが、aとbが入れ替わったものを重複しないように数え上げる必要がある。
重複する部分は、各bitがa側とb側で入れ替わったとしても最終的な結果には変わらない部分のことで、「a側が1、b側が0」の場合と「a側が0、b側が1」の場合、2重カウントしてしまう。
これを片方だけカウントするようにするため、「(a xor b, a+b)が何通りあるか?ただし、各ビットについて、(a側のビット,b側のビット)=(0,0)(1,0)(1,1)のものだけ考える」という問題に言い換える。


func(S,X):=「a+b<=S」「a^b<=X」のとき、各ビットが(0,0)(1,0)(1,1)のものだけ考えた場合の、答えの通り数」
と考えると、aとbの一番右側のビットについて、上記の3パターンで場合分けをする。
(1) aとbの一番右側のビットが(0,0)の場合
a=2a', b=2b'と表現できるので、これで考えると、
a'+b' <= S/2
a' ^ b' <= X/2
なので、func(S/2, X/2)

(2) aとbの一番右側のビットが(1,0)の場合
a=2a'+1, b=2b'と表現できるので、これで考えると、
a'+b' <= (S-1)/2
a' ^ b' <= (X-1)/2
なので、func((S-1)/2, (X-1)/2)

(3) aとbの一番右側のビットが(1,1)の場合
a=2a'+1, b=2b'+1と表現できるので、これで考えると、
a'+b' <= (S-2)/2
a' ^ b' <= X/2
なので、func((S-2)/2, X/2)

となる。したがって、
func(S, X) = func(S/2, X/2) + func((S-1)/2, (X-1)/2) + func((S-2)/2, X/2)
となる。
SやXが0や1のときは1通り、0未満のときは0通りになることを注意してメモ化再帰を実装すればO(log N)程度で解ける。

解法2

解説PDFから。(上から桁DP)


まず、xorというのは「桁上りのない加算」といえるところから、a ^ bとa + bを比べた場合、
a + b = a ^ b + (1 << (a & b))
という条件から、a ^ b <= a + bなので、「vがN以下かどうか」だけを考えれば良いことがわかる。
したがって、この単純に制約をそのままDPを考えると、
dp[i][j] := 上からiビットまで決まっているとき、j=vとなる通り数
が考えられる。


このままだと、jの部分がNまで考える必要があり、N<=10^18なので、メモリが足りない。
ここで、jを「上からiビットまでの部分だけ」で考える。
jの条件をNについてひっくり返して、
dp[i][j] := 上からiビットまで決まっているとき、N-j=vとなる通り数
にすると、jは0以上かどうかを考えればよく、さらに上からiビットまでで考えるために、
dp[i][j] := 上からiビットまで決まっているとき、(N>>i)-j=(v>>i)となる通り数
というのを考える。


このdpは、上からi-1(dp[i+1][*])ビットまでがわかっていて、iビット目を考えるとき、dp[i+1][j]でのjはiビット目で考える場合は2倍になることに注意すると、
(1) Nの上からiビット目が0の場合
j=0は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][0]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][1]
j=1は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=2は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][2]
j=3は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][2]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=4は、
・・・

(2) Nの上からiビット目が1の場合
j=0は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][0]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=1は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][0]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][1]
j=2は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=3は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][2]
j=4は、
・・・

のような遷移になる。
上記の遷移は周期性があり、j=2以上のときは、j=2以上のところにしか遷移しないため、「2以上」というふうにまとめ上げて計算してもよい。
すると、j=0,1,2以上の3パターンだけ考えれば良く、上記の遷移をまとめあげると、
(1) Nの上からiビット目が0の場合
j=0は、dp[i][0] = dp[i+1][0] + dp[i+1][1]
j=1は、dp[i][1] = dp[i+1][1]
j=2以上は、dp[i][2以上] = dp[i+1][1] + dp[i+1][2以上] * 3

(2) Nの上からiビット目が1の場合
j=0は、dp[i][0] = dp[i+1][0]
j=1は、dp[i][1] = dp[i+1][0] + dp[i+1][1]
j=2以上は、dp[i][2以上] = dp[i+1][1] * 2 + dp[i+1][2以上] * 3

とすることができる。
答えはΣ_{j=0,1,2以上} dp[0][j]になる。
上記の計算をするだけなので、O(log N)程度で解ける。(MODを取るのを忘れずに)

yukicoder No.749 クエリ全部盛り

問題

すべての要素が0で初期化された長さNの数列{a_i}が与えられる。
Q個のクエリが与えられるので、処理せよ。
各クエリ(q,l,r,k)はqの値に応じた処理を行うこと。

  • q=0: k*Σ_{i=l}^r a_iのmod 10^9+7を出力
  • q=1: l <= i <= rについて、a_iをkに変更
  • q=2: l <= i <= rについて、a_iをa_i+kに変更
  • q=3: l <= i <= rについて、a_iをa_i*kに変更
  • q=4: l <= i <= rについて、a_iをa_i+k*F_iに変更

制約

  • 1 <= N <= 10^6
  • 0 <= Q <= 10^5
  • 0 <= l <= r < N
  • 0 <= k <= 10^9

解法

範囲更新として、遅延セグメント木を検討する。
遅延セグメント木を考えるため、モノイドMと作用素Opの構造、それらの写像単位元を考える。


まず、モノイドMについて必要そうな構造を考える。
query処理で必要なのはq=0の時で、Σa_iが必要。また、q=4で、iについてのF_i値がそれぞれ個別に必要となる。
ここで、{a_i, F_i}という元を考える。
二項演算●は、和が欲しいので、{a_i, F_i}●{a_j, F_j}={a_i+a_j, F_i+F_j}で考える。
(F_i部分も、結局k倍したものの和が欲しいので、和のk倍から求めるのに和の形にしておく)
単位元は{0, 0}にする。


次に、上記のMを踏まえつつ、作用素Opについて考える。
いま必要なのは「kに置き換える」「kを加える」「kをかける」「k*F_iを加える」の4操作になる。
{a_i, F_i}に対して、「a_iにxをかける」「a_iにF_iのyをかけたものを加える」「a_iにzを加える」という3つを考えると、
「kに置き換える」 <=> (x,y,z) = (0,0,k)
「kを加える」 <=> (x,y,z) = (1,0,k)
「kをかける」 <=> (x,y,z) = (k,0,0)
「k*F_iを加える」 <=> (x,y,z) = (1,k,0)
で表現して、{a_i, F_i}に対して(x,y,z)を作用させると{a_i*x+F_i*y+z, F_i}になるように考えればよいことがわかる。


区間に対する操作で、要素数に応じて変化する部分を考える。
区間の要素を一様にx倍する場合は、要素をまとめあげた区間の構造に対してx倍するのと変わらないが、xを加える場合は、要素数*xが増えるので、考慮する必要がある。
素数がlenの区間を考えている場合は、{a_i, F_i}に対して(x,y,z)を作用させると{a_i*x+F_i*y+z*len, F_i}になるように考えればよい。


作用素同士は、
{a_i, F_i} ● (a,b,c) ● (p, q, r)<=> {a*a_i + b*F_i + c, F_i} ● (p, q, r)<=> {(a*a_i + b*F_i + c)*p + q*F_i + r, F_i}<=> {a_i, F_i} ● (a*p, b*p+q, c*p+r)
より、 (a,b,c) ● (p, q, r) = (a*p, b*p+q, c*p+r)と計算してあげればよい。

作用素単位元は、何も作用しないのと同じになる(1,0,0)を考えればよい。


ここまでで、遅延セグメント木を適用でき、十分高速に答えを求められる。
(各計算はちゃんとmodとって計算する)

Tenka1 Programmer Contest 2018 E. Equilateral

問題

HxWのグリッドにコインがいくつか置かれている。
このとき、相異なるコインの3つ組で「その3つのうち、どの2つのコインを取っても、それらの存在する座標の間のマンハッタン距離が一定」であるようなものの個数を求めよ。

制約

  • 1 <= W, H <= 300

解法

「マンハッタン距離が一定」というのは、実際に図示してみると、ある点を中心とした正方形を45度回転させたところになる。

f:id:phyllo_algo:20181028233734p:plain

他の2点はこの正方形の線上に乗っている必要がある。
適当に2点を定めてみると、該当する点の範囲(赤い領域)は以下のように絞られる。

f:id:phyllo_algo:20181028233815p:plain

しかし、単純に2点を選んで3点目を考えてしまうと、3点目がO(1)で求められたとしてもO(W*H * W*H)になってしまい間に合わない。
ここで無駄なところを探してみると、「ある点xを決めた場合、残り2点のうちどちらかは必ずxの45度斜めに存在する」、ということに気付く必要がある。


ある点xに対して、45度斜め方向にある点yがある場合、最後の3点目zは上の図の一番右の図のように赤い範囲の部分となる。
赤い範囲の部分に点が何個あるか?は、前もって累積和を求めておけばO(1)で求められるので、点xを決めるのにO(W*H)、点yを見つけるのにO(W+H)、点zを見つけるのにO(1)、累積和を計算するのにO( (W+H)*(W+H) )で、全体としてO(W*H*(W+H))≒O(N^3)程度で求められる。

実装

上記のアルゴリズムを実装するのに、単純に45度の4方向すべてに対して求めると重複で数え上げてしまうので、その分を引いてあげる必要がある。

解説放送では、盤面全体を90度回転を4回行い、それぞれの回転ごとに、以下の部分をカウントする方法が紹介されていた。

f:id:phyllo_algo:20181028235340p:plain

ある点xについて、その右上方向の45度方向にだけ点yを探し、点zの範囲のうち、一番右上の部分だけカウントしない。
もしそのカウントしない部分に点zがあった場合は、時計回りに90度回転したときにカウントされる。
右下の範囲については、180度回転した場合にカウントされ、右上のカウントしないところも270度回転したときにカウントされるので、重複なくカウントできる。(天才)

反省

添え字間違い、範囲外アクセスなどしまくった。
怪しい部分は範囲外アクセスなどしていないかチェックする。

あと、斜めのまま実装したけど、「絶対値を見たら45度回転」から45度回転した状態で処理した方がいろいろミスがなさそう。。。

AGC028 B. Removing Blocks

問題

1~Nの番号が書かれた箱が1列に並べてあり、各箱の重さは整数A_iで与えられる。
この箱を一つずつ取り除いていくことを考える。
ある箱を取り除くときのコストは、その両隣に連続している箱の重さの総和になる。
取り除き方はN!通り考えられるが、そのすべての取り除き方について、N回の取り除くコストの総和の合計を求めよ。

制約

  • 1 <= N <= 10^5
  • 1 <= A_i <= 10^9

解法

各箱について取り除かれる回数e_iがわかれば「Σ e_i * A_i」で求められる。
制約的にこの計算をO(NlogN)以下の計算量で行う必要がある。


(気付くのが厳しいが、)全事象を考えているので、確率的に考えて期待値を求めることでこのe_iを求める。


ある箱jが取り除かれるとき注目している箱iが連結している確率p_ijが求められれば、その期待値は「N! * Σ_{j=1}^N p_ij」で求められる。
jとiが連結している確率p_ijを考えると、iからjまでの連続した箱のうち、jが最初に選ばれる確率と同じであるので、p_ij = 1 / (abs(i-j)+1)と求められる。


今、MODで計算しているため、p_ijは逆元を計算しておけば整数値になる。
さらに、Σp_ijを考えるとき、p_ijは1/1+1/2+1/3+...のように連続した和になるので、累積和を求めておけばO(1)で求められる。


したがって、e_iがO(N)で求められ、Σe_i * A_iもO(N)で求められるので、全体でO(N)で求められる。

反省

DPや法則性の方向で考えてしまっていたので、確率・期待値の発想がまったく考慮できていなかった。
p_ijの形も解説のようにすぐ導出できなかったので、確率・期待値問題の練習がかなり必要・・・

yukicoder No.743 Segments on a Polygon

問題

M頂点の凸多角形の頂点同士をN本順番に線分で結ぶ。
このとき、頂点は一度線分に使われたら2度は選ばれない。
i番目に結んだ線分の頂点a_iとb_iの情報が与えられるので、追加した線分同士の交点の総数を答えよ。
(もし、ある交点が複数の線分からなる場合は、1つの交点ではなく、各線分同士の交点として数え上げる)

制約

  • 1 <= N <= 10^5
  • 3 <= M <= 2*10^5
  • 0 <= a_i, b_i < M

解法

頂点a_iとb_iを結ぶときは、始点終点ではないので、a_iとb_iを交換してもかまわないことがわかる。以下、a_i < b_iで考える。
重要な性質として、「頂点を結ぶ順番は関係ない」ということに気付く必要がある。


交点ができるケースを考えるために、多角形を直線上にのばして、線分を曲線で表した以下のような図を考える。
f:id:phyllo_algo:20181006041354p:plain
今は、太線の線分を追加する場合を考える。
交点ができるケースは、①と③のケースで、a_iからb_iの間にある頂点に、a_i以下b_i以上の頂点からの線分がある場合になっている。


図の左側付近(①と②のケース)を考える。
左側から太線の交点を作る①(a_j, b_jとする)は、a_jがa_iよりも左側にあり、交点を作らない②(a_k, b_kとする)は、a_kがa_iよりも右側にある。
したがって、「頂点を結ぶ順番は関係ない」性質から、左側から順番に線分を追加していき、すでに結んだ頂点のうち、bにあたる部分がa_iとb_i内に何個あるか?がわかればよい。
これはBITなどでO(logM)で求められる。


図の右側付近(③のケース)を考える。
しかし、③を追加する場合を考えると、これは上記の①のケースに当たるので、太線の追加時には考えなくてよいことがわかる。


したがって、追加する線分のa_iを小さい方から順番に追加していき、追加した線分のb_iをBITなどで記録しつつ、a_j, b_jの線分を追加する場合は、a_jからb_j内に含まれるb_iの個数をカウントしていけばO(N log M)で求められる。

ARC103 E. Tr/ee

問題

各文字は0または1の長さnの文字列sが与えられる。
n頂点の木について考えたとき、

  • i文字目が0なら、木からどのように辺を1つ取り除いてもサイズiの連結成分が作れない
  • i文字目が1なら、木からある辺を1つ取り除いてサイズiの連結成分を作れる

を満たすような木を実際に1つ構築せよ。
構築できない場合は-1を出力せよ。

制約

  • 2 <= n <= 10^5

解法

小さいケースで考えてみると、

  • 一番最後の文字が1の場合は構築できない
  • リーフの頂点につながる辺を除くと連結成分が1のものが必ずできるので、最初の文字は必ず1でないといけない
  • 辺を取り除いてサイズxの連結成分ができたら、対称的にN-xの連結成分ができるので、文字列は最後の文字を除いて対称になっていないといけない

ということがわかる。
以下、上記の条件を満たすような文字列について考える。


今、満たしたい連結成分集合が{1,3,5,...}のような場合を考える。
「1」は、リーフの部分の辺を切ればよい。
「3」は、木の形を考えてみると、以下のようなものになる(赤枠と交差している辺を切ればよい)。
f:id:phyllo_algo:20180930022207p:plain
「5」は、上記の形を残しつつ、5個の頂点を入れる必要があるので、以下のように青枠を考えればよい。
f:id:phyllo_algo:20180930022620p:plain
もし、「5」ではなく「6」だった場合は、以下のように頂点を増やせばよい。
f:id:phyllo_algo:20180930022926p:plain
上記のように、与えられた連結成分集合の小さい方から考えて、それまでの形を残しつつ、順次構築していけば目的の木が作れる。


上記の木は、「キャタピラ木」といい、線グラフの各頂点にいくつか頂点を生やしたような木になっている。
Caterpillar tree - Wikipedia

f:id:phyllo_algo:20180930023242p:plain
生やした部分はリーフなので、必ず連結成分は1のものができ、線グラフの部分の辺を消すことが題意に相当する。

反省

木の形はある程度限られるので、時間がもう少しあれば、いろいろな木を書いて見ている中でたどり着けたかもしれないけど、、、
「順次構築」的な発想をするようにしていれば効率的にたどり着けたかもしれない。

ARC103 D. Robot Arms

問題

m本の腕とm+1個の関節からなるロボットアームを考える。
腕iの長さはd_i。
関節iは腕iと腕i+1をつないでおり、関節1は原点に置かれ、各関節の角度は上下左右方向に指定できる。


いま、N個の平面上の整数点が与えられる。
すべての整数点にぴったり関節m+1を合わせられるようなロボットアームを返せ。
また、各整数点について、実際にその点に合わせられるような関節の指定値を出力せよ。
できない場合は-1を出力せよ。

制約

  • 入力はすべて整数
  • 1 <= N <= 1000
  • -10^9 <= X_i, Y_i <= 10^9
  • 1 <= m <= 40
  • 1 <= d_i <= 10^12, d_iは整数

解法

小さいケースで試してみると、(0,1)と(1,1)のように1だけずれた点を同時に満たすロボットアームが構築できないことはすぐわかり、この考えを進めると、座標の(x+yの)偶奇がそろっている場合しかダメなことがわかる。
以下、偶奇がそろっている場合を考える。


整数点の座標は結構大きい値だが、腕の数が40程度のため、うまく長い腕と短い腕を組み合わせる必要がある。
そのような組み合わせとして(構築ゲーでよく出てくる)2冪の長さを考える。


m=1で、腕の長さが{1}の場合、以下のような到達点になる。
f:id:phyllo_algo:20180930014406p:plain

m=2で、腕の長さが{1,2}の場合、{1}の時の到達点を上下左右に2ずらしたところになるので、以下のような到達点となる。
f:id:phyllo_algo:20180930014450p:plain

したがって、{1,2,4,8,16,...}と2冪の長さで考えると、穴なくひし形範囲内のすべての点にたどり着けるようなロボットアームを構築できる。
上記はx+yが奇数の場合だが、偶数の場合は、{1,1,2,4,8,16,...}のように1を加えたものを考えればよい。


次に、整数点への関節の指定値の構築を考える。
これは、腕の長さが長いものから{2^30, 2^29, ... , 4, 2, 1}のようにしておき、原点からスタートして、上下左右の中で一番目的に近づくように設定するものを選んでいけばよい。

反省

  • マンハッタン距離なので、x軸とy軸は独立に考えられそう
  • 単純に半分に分けるとm=20程度で10^9を作らないといけないし、mをx軸とy軸でうまく分けたとしてもどっちも10^9程度の時に破たんしそう

みたいな考え方をしてしまって、単純に2冪だけでできる方向の考察ができなかった、、、

yukicoder No.737 PopCount

問題

Nが与えられる。
 \Sigma_{i = 1}^N {i * popcount(i)}を求めよ。
(popcount(i)は、iを2進数表記したときの立っているビットの数)

制約

  • 1 <= N <= 10^18

解法

法則性がないか見るために、各数字のビットを書き出してみる。
f:id:phyllo_algo:20180929013409p:plain

1bit目が1になるものは、{1},{3},{5},{7},{9},...
2bit目が1になるものは、{2,3},{6,7},{10,11},...
3bit目が1になるものは、{4,5,6,7},{12,13,14,15},...

各bit目ごと(上の表の縦方向)に見ると、「塊が等間隔で現れている」という法則性が確認できる。
そこで、「x bit目について、N以下でbitが立っている数字の和」を求める方法を考えれば、それぞれのxで求めたものを足せば答えが得られる。


ということで、「x bit目について、N以下でbitが立っている数字の和」を考える。
最初の塊は、最初の数字が2^{x-1}で、x個続いている。
また、塊は間隔が2^xごとになっており、塊の数は、等差数列より「(N-2^{x-1})/2^x + 1」個ある。
したがって、これらは「等差数列の和の公式 Sn = n / 2 * (2*a + (n-1) * d)」を使えばO(1)で求められる。
また、Nが固まりの途中までの場合は、N+1から塊の最後の数字までの分の和を引いてあげればよい。