ARC093 E. Bichrome Spanning Tree
問題
N頂点M辺の重み付き無向グラフGと整数Xが与えられる。
このグラフGの各辺を白か黒で塗りたいが、以下の条件を満たす塗りかたが何通りあるかmod 10^9+7で求めたい。
条件「白辺と黒辺どちらも含む全域木が存在し、そのような全域木のうち、辺の重みの和が最小のものの和はX」
制約
- 1 <= N <= 1,000
- 1 <= M <= 2,000
- 1 <= 辺の重み <= 10^9, 辺の重みはすべて整数
- 1 <= X <= 10^12
解法
そもそも題意を正しく読み取れてなかった・・・大雑把に解法をまとめておく、、
題意
入力例2の例で、全部の塗りかたを列挙して確認してみる。
辺の塗りかたは8通り考えられ、それぞれの塗り方で「白辺と黒辺どちらも含む全域木(各枠の真ん中)」と「その全域木の中で、辺の重みの和の最小値(各枠の右側)」を図示。
X=2の場合は答えが4個、X=3の場合は答えが2個になっているのが確認できる。
アプローチ
おおよそ以下のような流れで考えると良い?
- 「全域木の辺の和の最小値がx」になるためには、(x-1)以下になる全域木で使われるような辺すべてが同じ色になっていないといけないことに気付く
- そのような場合での辺の色の塗り分け方をf()として考え、そこから答えを求める
- f()の計算式(塗り分け方の式)と、計算に必要な要素を求める
上の図で、X=3の場合を考えてみる。
最小のものが2になってしまわないために、「全域木の辺の和が2になるような全域木」に使われるすべての辺が同じ色になっていないといけないことがわかる。
したがって、Xがもっと大きい場合を考えると、「全域木の辺の和がX-1以下になる全域木に使われる辺がすべて同じ色になっている」必要がある。
そこで、「全域木の辺の和がX-1以下になる全域木に使われる辺がすべて同じ色になっている」ような塗り方が何通りか?を表すf(X-1)を計算することを目指す。
このf(x)が求められれば、「f(X)とf(X-1)の差分」が題意を満たす塗りかたの通り数になる。
上図で考えると、f(2)は「全域木の辺の和が2以下になる全域木に使われる辺」というのは1-2と2-3の辺で、それが同じ色になっているような塗りかたは、「1-2と2-3の辺の色」と「それ以外の辺1-3の辺の色」がそれぞれ黒または白で、すべての頂点が同じ色になる2通りを引いた「2^1 * 2^1 - 2 = 2通り」になる。(f(2)=2)
また、f(3)は「全域木の辺の和が3以下になる全域木に使われる辺」は1-2と2-3と1-3すべての辺で、それがすべて同じ色になっているような塗りかたは、同様にして「2^1 * 2^0 - 2 = 0通り」になる。(f(3)=0)
f(1)を考えてみると、そのような辺は存在しないので「2^0 * 2^3 - 2 = 6」。(f(1)=6)
f(4)を考えてみると、すべての辺が該当するので、f(3)と同じで「0」。(f(4)=0)
X=3のケースでは、f(3)=0とf(2)=2の差分で「f(2)-f(3)=2」が答えになる。
上記の考察からf(x)の求め方を考えてみると、同じ色にしないといけない辺の数がa本ならば、どんな色で塗ってもいい辺の数は(M-a)本なので、aが1本以上なら「f(x) = 2^1 * 2^(M-a) - 2」、aが0本なら「f(x) = 2^0 * 2^M - 2」で求められる。
最後に、上記のa本は「全域木の辺の和がx以下になる全域木に使われている辺」のことで、これを効率的に求める必要がある。
例えば、一つのMSTを求めてその重みがAだったとすると、そのMSTに使われた辺は「全域木の辺の和がA以下になる全域木に使われている辺」であることがわかる。
使われなかった辺については、もしかしたらその辺を利用しても全域木の辺の和がAになる全域木を作れるかもしれない(入力例1)し、そうでないかもしれない。
ということで、ある辺eがどのタイミングで全域木に使われる辺に選ばれることになるか?を考える。
これは、「その辺eを必ず使ってMSTを作った場合、そのMSTの辺の重みの和がB」というのを求めてあげれば、「全域木の辺の和がB以下になる全域木に使われる辺」ということが言えるので、その辺eはBのとき同じ色に塗る必要がでてくるということがわかる。
これは、最初に必ず使いたい辺を選んで、残りの辺は普通にクラスカル法を適用すれば求められる。
したがって、すべての辺eについてこの値Bがわかっていれば、f(x)で必要な「a本」が求められる。
計算量は、各辺についてその辺を必ず含むMSTを求めるところが一番重くて、各辺についてpriority_queueとUnionFindを使ってだいたいO(M * MlogM)ぐらい。
yukicoder No.660 家を通り過ぎないランダムウォーク問題
問題
東西にのびる1次元の道の原点に立っており、東にN歩のところに家がある。
2*N歩以下で家にたどり着くような歩き方を、10^9+7で割った余りで答えよ。
ただし、家に一度たどり着いたら必ず歩くのをやめて家にはいり、それ以降は歩かない。
制約
- 1<= N <= 2*10^5
解法
縦軸に位置、横軸に歩数をとって、移動を図にすると以下のようになっている。
(右下か右上にしか移動しない)
求めたい答えは、「(Aまでの経路数)+(Bまでの経路数)+(Cまでの経路数)+・・・」になっている。
向きを45度回転させてみると、あるGまでの歩き方というのは以下のような右上部分がちょっとかけた経路数になっている。
この、SからGまで、下か右のみ移動できる場合の経路数を求めたい。
まず、右上が欠けていない経路を考える。
この場合、SからGまでの経路数は、縦がh、横がwの場合、「{h+w}_C_w」で求められる。
(右移動がw個、下移動がh個あって、{h+w}ステップの中で右移動の場所を決めてしまえば、残りが下移動になるため、そのような組み合わせの数になる)
次に、赤太線の部分を通る経路をここから引きたい。
図のように斜めの線を引いて、Gの位置が線対称となるようなところにGを設定した、以下のような図を考える。
この図でのSからGまでの経路は、必ず斜めの線をまたいでいて、ステップ数は{h+w}になっているので、赤線を1度は通った場合の経路数になっている。
(実際、斜めの線を超えた場合に「右移動を下移動」「下移動を右移動」に対応付けると実際の赤太線を1度は通る経路に対応づく)
この経路数は「{h-1+w+1}_C_{w+1}」で求められる。
したがって、右上が欠けたような経路数は「{h+w}_C_w - {h+w}_C_{w+1}」で求められるので、一番上の図のA,B,C.・・・すべてについて求めて足してあげればよい。
上記、mod_comb(n,m,MOD)を高速に求める必要がある。
予め、階乗を普通にforループとかで計算しておき、階乗の逆元はMODが素数なのでフェルマーの小定理から「a^{-1}=a^{MOD-2}」で求めておける(mod_powを使う)。
よって、「n_C_m = n! / (m! * (n-m)!)」は、求めておいた階乗と階乗の逆元から高速に求められる。
ちなみに、カタラン数は、h=w=nのケースで同様に考えれば、求められるので、「C_n = {2*n}_C_n - {2*n}_C_{n+1} = {2*n}_C_n - {2*n}_C_{n-1}」。
yukicoder No.5001 排他的論理和でランニング
問題
N個の重複のない1以上10^6以下の整数が与えられる。
ここから重複なしでM個選んですべてのXORを取ったときの値がなるべく大きくなるようにせよ。
制約
- 5 <= N <= 10^5
- 1 <= M <= N
- ただし、ジャッジには乱数で生成した値の50ケースで構成される
最終的に提出したアプローチ
最適解に1点届かない52,428,749点で10位/29人。
- 時間ぎりぎりまで以下を繰り返す
- N個から適当にM個を選び、これを初期値とする
- M個のXORを取った値の上位bitから見ていって、以下の処理をする
- 0の場合、1にするため、そのbit以下だけ変化するようなM個側の要素1つとN-M個側の要素1つをswapする
- 1の場合、1のままでよいが、よりスコアが上がりそうなswapができそうなら要素2個同士のswapを試す
- swapは「a xor b xor ... xor z = X」としたとき、aをa'に置き換えたときの値は「X xor a xor a'」で求められるので、O(1)で可能
最適解に1点足りないのは、上位bitから1になるように決めてく方針なので、最後のbitがうまく処理できないと11111110のような解になってしまうためだと思われる。
スコアが高い方がよいので、上位bitから1で埋められた方がよいと思ってそうした。
初期値をごちゃごちゃし続けるよりも、多点スタート的にいろんな初期値を試すのがスコアがよかった。
最適解のアプローチ
https://twitter.com/koyumeishi_/status/977210736685457408
koyumeishiさんがツイートされてたので理解のため、メモ。
アプローチは「使う要素と使わない要素のswapを時間いっぱい試す」でよいらしい。
(以下、理解が間違ってるかもなので注意)
まず、上記の問題を行列で考える。
例えば、要素がN=4個、2進数表記で(101,110,111,001)が与えられ、ここからM=2つ選ぶような場合を考える。
2進数表記の要素を横に縦向きに並べた行列をAとすると、「mod 2で計算」と「xの要素で1の数はM個、それ以外は0」という制約のもと、「Ax=b」形式で以下のように書ける。
( 1 1 1 0 ) ( 1 ) ( 0 1 1 0 ) x = ( 1 ) mod 2 ( 1 0 1 1 ) ( 1 ) Ax = 1 mod 2
このxを求めるのが問題。(連立1次方程式と見れる)
今回、Aの行数は、要素の最大値が10^6程度なので20bit=20行必要になる。
したがって、行列Aは、20*Nの行列。
解xが存在する場合、解の自由度はN-rank(A)。
rank(A)<=min(20, N)が成り立つので、最大でもrank(A)は20。
Nは1~10^5からランダムに選ぶので、おおよそのケースでN-rank(A)は大きい値になる。
xについて、「1の個数がM個」という制約なしで考えると、各要素は0か1なので、全部で2^N通り考えられる。
このうち、解の自由度がN-rank(A)なので、上記の式が成り立つ解xは2^{N-rank(A)}通りあると考えられる。
なので、適当にxを決めて解が見つかる確率は2^{N-rank(A)} / 2^N = 2^{-rank(A)} <= 2^{-20} ≒ 10^{-6}ぐらいになる。
したがって、10^6回探せば1回は見つかるので、比較的見つかることが期待できる。
(「解xの要素で、1の個数がM個」という制約のもとで探索する場合でも同様か、小さいケースで実験してみるとおおよそ同じ確率っぽいが、うまく式で示せない・・・orz)
ARC092 D. Two Sequences
問題
長さがNの非負整数列が2つ与えられ、それぞれA,Bとする。
1<=i,j<=Nとして、A,Bそれぞれの要素の和(a_i + b_j)がN^2個作れる。
このN^2個の数字のxorを計算せよ。
制約
- 1 <= N <= 2 * 10^5
- 0 <= a_i, b_j < 2^28
解法
単純に計算しようとするとN^2 = (4 * 10^10)個のxorを計算するので間に合わない。(頑張れば間に合う?)
整数のxorはビットごとに計算されるので、各ビットごとに分けて計算できるか考える。
想定解
今、答えのiビット目を求めることを考える。
xorの性質として、「ある整数xのb番目のビットが1である」というのは「x mod 2^(b+1)が2^b以上」というので判断できることを使う。
競技プログラミングにおけるXOR問題まとめ - はまやんはまやんはまやん
この性質を使うと、(a_i + b_j)はmodを取って、「(a_i + b_j) mod 2^(i+1)」が「2^i」以上かどうかで判断できる。
「a_i mod 2^(i+1)」と「b_j mod 2^(i+1)」をしておけば、その和は0から4 * 2^i未満に収まり、和のiビット目の判断は、
- 0以上2^i未満:0
- 2^i以上2 * 2^i未満:1
- 2 * 2^i以上3 * 2^i未満:0
- 3 * 2^i以上4 * 2^i未満:1
の4つのうちのどれかになる。
すべての要素をmod 2^(i+1)しておいたAとBの要素同士の和で、それぞれの範囲にどれだけの個数があるか?が高速に求められればよい。
これには、modを取った配列をA'、B'とすると、どちらもソートしておくと、A'の各要素a'_iについて、和がX以上になる要素数を二分探索で求める、などすればO(NlogN)で求められる。
Xとしては、2^i、2 * 2^i、3 * 2^iがわかれば、↑の4パターンにおける個数がわかるので、1となる部分の個数がわかると、それが奇数かどうかで答えのiビット目が1か0かがわかる。
結局、ビットは30ぐらいなので、O(30 * NlogN)程度で求められた。
別解
本番は、ちょっと違う方法で通した。
まずは最下位ビットから考える。
配列Aの要素のiビット目が1の数をA1、0の数をA0とし、同様に配列BについてもB1、B0とする。
すると、A1 * B1は桁上りは発生して0になるので、各要素和のiビット目が1になっている個数は「A0*B1 + A1*B0」になる。
続けて一つ上のビットについて考える。
一つ下のビットでA1*B1個の桁上りが発生しているので、1になっている個数は「一つ前のビットでのA1*B1 + A0*B1 + A1*B0」で求められる。
ここで、入力例1などで試していると、問題があることがわかる。
例えば、2進数表記でa_i=011とb_j=001のようなものがあった場合、最下位ビットでの桁上りがその二つ上のビットまで影響する。
しかし、上記のような求め方をしようとすると、一つ前のビットでA1*B1個の桁上りがあるが、どの要素の和のところで桁上りがあったかがわからなくなるので、前のビットの影響を受けての次の桁上りが何個あるのかを求められない。
ただ、上記の流れから、答えのiビット目が0か1かは「(i-1)桁からの桁上りしてくる個数 + A0*B1 + A1*B0」が奇数か偶数かで求められることはわかる。
そこで、この「桁上りしてくる個数」が求められないかを考える。
今、iビット目を考える。
桁上りが何個あるかを考えると、結局、配列の各要素のiビット未満の部分が必要であることがわかる。
具体的には「配列A,Bの各要素のiビット未満の部分について注目し、その部分の和が2^i以上になる個数」を求めれば桁上りの個数が求められることがわかる。
各配列要素のiビット未満の部分だけにした配列A'、B'を計算するのにO(N)。
A'、B'をソートするのにO(NlogN)。
A'とB'の要素の和が2^i以上になる個数を求めるのは、A'を大きい方から、B'を小さい方から尺取り的に、
int j = 0; for(int i=A'.size(); i>=0; i--){ while(j<B'.size() && A'[i]+B'[j]<2のi乗) j++; 個数 += B'.size() - j; }
のように求めるか、想定解と同じ二分探索で求めてあげればよい。
結局、桁上りの個数がこのようにO(NlogN)で求められたので、各桁について「桁上りの個数 + A0*B1 + A1*B0」を求めていけば答えが求まる。
HACK TO THE FUTURE 2018本戦参加記
概要
まぐれで予選突破してしまい、こんな機会滅多にないと思うので、参加してきました。
future-contest-2018-final.contest.atcoder.jp
普段、会場の情報とかつぶやいてくれる人とかありがたいと思っていたので、今回はできるだけつぶやくようにしてみました。(鬱陶しくツイートしててごめんなさい)
起床~移動
- 前日yukicoderちょっとだけ出るつもりがガッツリでてしまい、寝たのがAM2時過ぎ
- ちょっと緊張してたかAM8時の目覚ましで起床AC
- たまたま入場がagwさんと一緒になった
準備
- 会場がどんな雰囲気でやるのかわからなかったけど、大きめテーブルに2人ぐらいずつ座れる感じでゆったり
- agwさんとmachyさんの後ろ側の席に陣取る
agwさんとmachyさんの後ろに陣取った(^ω^) pic.twitter.com/pylDOPZKu7
— phyllo (@phyllo) 2018年3月3日
コンテスト開始
- 問題読む
- 50x50マスにいくつかの操作を行える
- 操作は、植物を植える、収穫する、更地にする、道路を設置する、など7種類あり、それぞれ見合ったお金または労働力が必要となる
- 植物は植えると、すでに植えられたマスには植物数が+1し、さらに勝手に隣接の更地マスに広がっていくが、マス内の植物数が100になると岩になってしまう
- 植物の収穫数最大となるような1000ターンの操作列を出力せよ
- 問題かなり複雑じゃないですかね・・・8時間コンテスト・・・?
- 実際のビジュアライザとかの動き見ながら40分ぐらいかけて理解(遅い)
最初の考察フェーズ
- 雰囲気的に、普通の畑みたいに区画に分けたいお気持ちになる
- ということで大雑把には「サイズXの区画を増やす、区画内の収穫をする、他の操作、についてビームサーチする」を目指したい
- 区画は、正方形とかだと移動コストが微妙にかかってしまうので、できれば1*Nか2*Nぐらいの長方形がよさそう?
- 区画内を一気に収穫する想定だけど、収穫後にもう一度植える必要があるのは1手無駄してると思う
- 道路を引くかワープ設置するかとか、道の設置のうまい方法とか考えつつ、お昼
お弁当3種類あった。いただきます。 #HTTF pic.twitter.com/O3EVcit4AS
— phyllo (@phyllo) 2018年3月3日
- お弁当用意していただいていた
「貧乏フェーズ」
- 問題の制約をよく見ると、お金の初期値が100しかない
- これは結構ギリギリな金額で、区画を作りたいと考えていたけど、結構厳しい
- 「貧乏フェーズ」と名付けておく
- 逆に、貧乏を脱出したら打てる手が増えるので、別戦略が必要そう
- 「小金持ちフェーズ」と名付けておく
- 状態の評価値はここら辺分けておきたい
折り返し地点
- とりあえず、ビームサーチしたいと思ったけど、いざ実装しようと思ったら実装がだいぶ重い
- この時点で実装の大変さが原因で途中まで書いてたコード捨てるの結構厳しい・・・
- 0点で終わるよりはと思って、厳密さよりも動くコードを優先することに
貧乏フェーズの実装
- できるだけワープ近くで、かつ、お金がかからないように1マス区画を作るのが最初にやることかなと思い、考える
..R.. .RxR. RxWxR .RxR. ..R.. R: 道か岩 x: 栽培区画 W: ワープゲート
- ↑みたいな感じで、ワープ横に栽培区画を作ってそこで99まで栽培を行えば、100ターンぐらいで400植物ぐらいが手に入る
- もちろん途中収穫などうまくできるとよさそうだけど、ここでは99まで栽培を考えてた
- 市松模様的にもうちょっと広げて上げると多少スコアも上がるので、それを書く
- 収穫とかと区画の作成とかを同時にタイミングを気にしながら手順を作る実装が地味に難しい
- 貧乏フェーズの手法のまま最後まで行った場合のコード、ちょっと変形して別な場所にワープゲートを設置してそちらでも同じことやるコードを書く
- 最終提出のコードはこれ
小金持ちフェーズの実装
- 貧乏フェーズでは1マスごとにやってしまっているので、1回あたりの収穫量が少ない
- 単純に拡張するとマスのサイズを広げてあげたい
- この時点で、残り時間が3時間もない
- standingみるとかなりやばい点数が出ている
- 貧乏フェーズのコードは手元の見積もりで170万ぐらいだけど、1ページ目にも入れていない・・・
- 「小金持ちフェーズ」だけでなく「大金持ちフェーズ」ぐらいが必要そう・・・
standing凍結(残り1時間)
- とりあえず0点は避けたいので、↑の貧乏フェーズの手法の実装を投げて177万点
- あとはどこまで実装しきれるか・・・
- うおおおおおお
- とにかく動けばいいやと書きなぐっていたら実装がバグりまくる
- デバッグが「出力→ビジュアライザ」しかなくて効率がだいぶ悪い
- 結局実装しきれず終了
むずすぎ!\(^o^)/ #HTTF
— phyllo (@phyllo) 2018年3月3日
- さすがに8時間ぶっ続けでやった後の疲労感がすごいのと、不完全燃焼感がすごい
会社紹介
- Futureの会社紹介と脆弱性検知ツール「Vuls」の開発者の方の技術紹介とか
https://thinkit.co.jp/article/10092
- ミャンマー?から帰国したばっかりらしい
- 他の社員の方で技術書出されている方とかもいらっしゃるよう
懇親会
- やっぱり決勝は予選と違って「最上位(1~10位)の順位決定」をする必要があるので、問題が難しいとのこと
- TCO finalなイメージ、らしい
- それでもオープンも含めかなり高いスコアをたたき出している人が結構いて強い
- あとは、参加者のプロな方やFutureの方などいろんな方とお話しできてよかった
- 普段はstanding上位やツイッター上でしか見れない方ばかりで恐れ多い(((((((;´д`)))))))
結果発表!!! #HTTF pic.twitter.com/BE6I2CF2cW
— phyllo (@phyllo) 2018年3月3日
- 順位発表
- 3位以上はビジュアライザ見ながら発表
- やっぱり上位は盤面全部を使い切ってる感じですごい
- それにアプローチが上位でも多様で良い問題感ある
- 最後、なんと副賞や参加賞も追加で用意していただいていた(!)
- 集合写真とって解散
AGC021 B. Holes
問題
平面上にN個穴があいている。
今、原点を中心とした半径Rの円に無作為にすぬけさんを置く。すぬけさんはユークリッド距離で最も近い穴に落ちる。
すべての穴について、すぬけさんが落ちる確率を求めよ。
制約
- 2 <= N <= 100
- 穴の座標はすべて整数、すべて異なる、|x_i|,|y_i|<=10^6
- R = 10^10^10^10
解法
穴がある位置は、円の中心付近で、円全体からして十分に小さいので細かい部分は無視できる。
どちらかというと、穴の集まる原点付近よりもはなれたの部分に置かれる割合が大きく、そのようなケースだけを考えればよい。
O(NlogN)解
十分離れたところにすぬけさんを置いた場合、すぬけさんが落ちる穴は、穴の集まりの中でも外側にある穴のどれかになる。
穴の集まりの中で、内側の方の穴に落ちるには「凸包内、かつ、他の穴より近い位置」じゃないといけないため、落ちる確率は円の大きさ的に無視できるほど小さくなる。
したがって、穴の凸包を求めて、凸包をなす穴についてだけ考える。
凸包のある穴pと両方に隣り合う穴q,rについて考える。
穴pに落ちるには、両隣の穴q,rとの二等分線を円の外側に向かって伸ばした線より穴p側に設置されていれば穴pに落ちる。(正確には、穴の近くでは他の穴の方が近くてそっちに落ちる可能性があるが、すぬけさんがそこに設置される確率はかなり小さいので無視してよい。(たとえば下の図の二等分線始まり付近に設置されたら内側の穴に落ちる))
凸包の点すべてについて、どの角度で両隣の穴との二等分線が外側に向かって伸びているかがわかれば、角度の割合から落ちる確率が求められる。
凸包を求めるのにO(NlogN)程度なので、答えもO(NlogN)。
O(N^2 logN)解
凸包を使わなくてもよい。
ある穴pに注目する。
穴pから他のすべての穴への角度を求め、ソートしておく。穴pを中心として穴qの角度はatan2(q_y - p_y,q_x - p_x)で求められる。
ソートした角度において、両隣との角度の差がθで、その最大となる角度がmaxθであるとする。(ソート後の最初と最後の角度の差を求めるときは処理が少し変わるので注意)
もし、maxθがPI(180度)よりも小さい場合は、他の穴に囲まれているため、凸包の内部の点で、答えは「0.0」になる。
もし、maxθがPI(180度)よりも大きい場合は、穴pに落ちる角度は赤い二等分線がなす角度なので、答えはmaxθから両側90度分を引いた「maxθ-PI」になる。
各点について、他の点との角度のソートが必要なのでO(N*NlogN)=O(N^2 logN)。
O(NK)解
求められる精度が少し荒いようなため、穴をすべて内包する十分大きな円の周上を等間隔でK点用意し、各点から落ちる穴を見つける、という方法でも通せるらしい。
ただ、Kや円の大きさなどのパラメータでの答えの精度の見積もりが難しい。
天下一プログラマーコンテスト2016予選B C. 天下一プログラマーコンテスト1999
問題
参加者はN人の総当たり戦の記録をアンドウくんとハシモトくんの2人が行う。
記録はN*Nの表に記録する。(1選あたり2つの記録をする)
アンドウくんは間違えずに記録するが、ハシモトくんは確率Pで正しい記録、確率(1-P)で間違った記録をしてしまう。
各記録は独立事象とし、勝ち数が多い順(同勝ち数の場合は表の並び順)から順位をつける。
アンドウくんの記録が与えられるので、アンドウくんとハシモトくんのそれぞれの記録からの順位付けが一致する確率を求めよ。
制約
- 2 <= N <= 30
- Pは「p/q」形式で与えられ、0 <= p <= q, 1 <= q <= 10
解法
順位を決める要素は勝ち数なので、まず「勝ち数」を考える。
ハシモトくんの記録での各参加者の勝ち数は確率的に変化するが、「ハシモトくんの記録でt勝になる確率」は「アンドウくんの方での記録(s勝)」「確率P」から考えることができる。
dp[s][t] := アンドウくんの記録でs勝だった人が、ハシモトくんの記録でt勝になる確率
これはハシモトくんが正しくつけた記録の数uで場合分けが必要で、
- 試合数(N-1)中、「s勝」「(N-1-s)敗」
- s勝のうち、u個正しくつけた
- u個が勝ち->勝ち、(s-u)個が勝ち->負け、(t-u)個が負け->勝ち、(N-1-(t-u))個が負け->負け
- m個の記録のうち、n個正しくつけた場合の確率は、「mCn * P^n * (1-P)^(m-n)」で求められるのでこれをdp2[m][n]とする
と、
dp[s][t] = Σ_{u=0}^{s} dp2[s][u] * dp2[N-1-s][(N-1-s)-(t-u)]
となる。
次に、ハシモトくん記録での順位変動を考える。
ある参加者について、記録間違いで勝ち数が変動しても順位が変動しない場合、というのはイメージできる。
順位が変動しない勝ち数の範囲は、他の参加者の勝ち数状況に依存しており、すべての各参加者の勝ち数を全探索することは計算量的に難しい。
そこで、動的計画法的に端から決めていく方法を考える。
順位が低い方から考える。
今、p位の人Xを考えると、p位の人Xの勝ち数がm、(p+1)位の人Yの勝ち数がnとすると、
- 表でXよりYが下の場合、m>=n
- それ以外の場合、m>n
となっていれば順位が変動しない。
この条件を踏まえて、「p位の人が勝ち数q以下で、順位変動しない確率f(p,q)」を考える。最終的な答えはf(1,N-1)。
p==Nの場合、最下位の人を考える場合で、「k=0勝~q勝でのdp[最下位の人の勝ち数][k]の和」になる。
p
- 同じ勝ち点が許されるならr=k
- 同じ勝ち点が許されないならr=k-1
として求める。
反省
実際の考えの流れは「勝ち数が重要」→「一致する確率は勝ち数に基づくdpで求められそう」→「dpの計算で必要となるハシモトくん記録で勝ち数tとなる確率、を求める方法を考える」という流れかも。
「確率の式を正しく出す」「勝ち数のdpの適用を思いつける」「場合分けをミスらない」「誤差死がでないか判断できる」など必要。
問題が解けない原因を考えたい
背景
競技プログラミングの能力を鍛えたい。
ただ、何ができなくて解けなかったのか?や、問題の難しい部分はどこなのか?など簡単な抽象的・体系的でとらえたいお気持ち。
なんとなく思ったことがあるので、それを書き出して整理してみる。
「アルゴリズムを考えること」
「アルゴリズムを考えること」=「"問題"と"アルゴリズム"を辺でつなぐこと」
"問題"が与えられたとき、"問題"を"分解または言い換え"て、アルゴリズムの"使い方や制約"を踏まえて"アルゴリズム"を適用する。
ただし、"問題"以外のノードは与えられないため、自分で利用可能なノードを増やす必要がある。
問題が解けない=辺をつなぐのを失敗すること
"問題"から"アルゴリズム"までの辺を貼ることに失敗すると問題を解くことができない。
「分解・言い換え」のノードが足りない
"問題"を「グラフにして考えてみたり」、「複数の問題に分解したり」することに失敗。
ここの部分のノードの作り方が難しい問題は、「難しい」問題の印象。
「使い方・制約」のノードが足りない
アルゴリズム自体は知っていても、その"使い方や制約"をきちんと理解できておらず、適用できない。
例えば、動的計画法というアルゴリズムは知っていても、その使い方で「状態設計」「遷移」「高速化」などがちゃんと考えられないと、ノードが作れず、辺を貼るのに失敗する。
辺が張れていない、間違って張ってしまった
ノードは用意できてもノードとノードの関連性をちゃんと理解できていないと張れると気付かなかったりして失敗。
また、張れると思って張ったら実は嘘解法で張れない辺を張ってしまって失敗。
勉強すべきこと
問題が解けない時、「ノードが足りていない」のか、「辺が張れなかった・間違って張った」のか考えたい。
ある程度、頻出パターン(頻出ノード、頻出エッジ)があるようで、効率的に勉強するには頻出パターンから攻めたほうがよく、「"使い方・制約"と"アルゴリズム"」の部分は体系的にまとめられている。
他には、グラフ系・文字列処理系・幾何系など特定分野に絞って勉強するのもよいのかも。
”分解・言い換え”ノードを増やす
あんまり体系的にまとまっていない気がするし、問題に合わせて考える考察力・発想力が問われる気がする。
"問題"側から"分解・言い換え"側を考える場合は、いろんな問題を解いていろんな言い換えや分解方法を憶えておくか、それらの発想の基となる既存の理論・学問を勉強したりとかが必要なのかも。。。
"使い方・制約"側から"分解・言い換え"側を考えることもできるかもしれなくて、ある程度関係ありそうなノードを考えて辺が張れるか考えてみたり。
また、小さいパターンで実験してみて問題に含まれるパターンを見つけたりというテクニックとかも有効かも。
典型とかもあって、「絶対値を見たら45度回転」とか「Nが小さければbitで2^N全探索できないか」とか、こう来たらこう考える、みたいなのもあるっぽい。
Weathernews Programming Competition
概要
圧縮やRangeCoderの勉強のつもりで参加。
最終順位は26927.87点で20位。
といっても、一つ前との差分値をRangeCoderで圧縮しただけのコード。
問題
5分おき4観測分の衛星データが波長(16チャネル)ごとに64枚ある。このデータすべてを可能なかぎり圧縮・回答するプログラムを作成せよ。
スコアは、bz2の-9オプションでのサイズbase_comp_sizeに対して、「max(0.0, (1.0 - 圧縮サイズ/base_comp_size) * 10^6)」で計算される。
最終的に提出したアプローチ
- 各画像ごとに、2byte単位で読み込み、直前の2byteとの差分を作成し、それをRangeCoderで圧縮
振り返り、というか勉強
ロスレスな(動)画像圧縮、ファイル圧縮あたりが関係しそうということで、そこらへんの勉強のために参加。
いくつかメモ。
画像形式
画像形式でパッとでてきたのがPNG形式で、wikipedia見てみると結構いろいろ載っていて勉強になった。
Portable Network Graphics - Wikipedia
やっていることは「フィルタ処理→圧縮」。
フィルタ処理では「左との差」「上との差」「左と上の平均値との差」「左と上と左上の値を使ったPaethアルゴリズムでの予測値との差」、圧縮はLZ77とハフマン符号の組み合わせ。
この記事を読んで「どっかの値を使う(位置を保存)」とか「ある位置との差分を使う(差分を保存)」を考えてた。
けど、ちょっと複雑な「いろんな情報からそのピクセル値の予測をしてその差分を保存」のようなアイデアは保存する情報が増えて圧縮あんまりできなそうと思ってしまっていたので、全然考えてなかった。
Lossless JPEGなど損失なしの画像フォーマットがいくつもあるようだったので、それをちゃんと調べられていなかったのは調査不足だった。
1byte単位か2byte単位か
最初、hexdumpコマンドとかで眺めてて、偶数byteと奇数byteで分けて考えてみてもよいかなと思い、それを考えた。
片方はほとんど種類数がないので結構つぶせそうで、もう片方のbyte列をどう圧縮するか?が重要かと考えていた。
しかし、「上位byte列+下位byte列」で扱うと、それぞれ別に圧縮しても、まとめて圧縮しても、あまり圧縮効果が変わらず、正の点数が取れてなかった。
他にも、差分を取って圧縮するときに「正か負か」と「差分値」を保存するよう別々に分けようとすると同様に圧縮効果があまり得られず。
結局、twitterでも見かけていた「2byte単位」でまとめて扱って~というのが必要だった。
RangeCoder
エントロピー符号化で、Huffman Codingは情報理論とかでも知っていたけど、さらに圧縮率の高い算術符号化(≒RangeCoder)があるとのことで、それを実装するのを目的にすることにした。
Algorithms with Python / レンジコーダ (range coder)
RangeCoderの実装や内容は上記のページを参考に、写経。
理解が怪しくて、1byte単位のコードはそのままでいいけど、2byteやそれ以上の単位を扱う場合の処理がうまく書き直すのに苦労してた。というか、提出コード、いろいろ変えたりして定数がおかしいまま提出してた、、、バグってるはずなのに普通に動いているよう・・・
予測符号化・変換符号化
http://www.pcsj-imps.org/archive/2013tutorial.pdf
終了後に調べた限りだけど、上記資料がまとまってた。
「予測符号化」というっぽいが、「次の値を予測し、予測値との差分値を符号化」をどうやるかがアイデアとして重要だったよう。
そもそも「隣接画素が似ている(画素の相関が高い)場合に、隣の画素を予測値として注目画素との差を取ることで、分散(値の種類数)を減らせて(冗長性を減らせて)、効率よく圧縮できる」ので、この考えだと「前の画素の値を予測値にする」の発展として、いろんな情報や予測手法(線形・非線形な手法、用いる予測器を切り替える「適応予測」など)を考える方向へ行けてたよう。
また、データを互いに相関のないデータへ変換する「変換符号化」も。
ブロックに分ける、離散コサイン変換、・・・。
Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017参加記
概要
AtCoderで開催されたマラソンマッチに参加してみた。
phyllo-algo.hatenablog.com
1stの方は比較的時間取れて取り組めたけど、2ndの方は時間がほとんど確保できず、だいたい2.5日分ぐらいしかできなかったと思われる。。
最終順位は6,961,040点で73位。
WAが2つ出てて、Timelimitを10秒で計算してるという大ポカ。
問題
重みなし無向グラフGが与えられる。そのグラフの頂点をG_embの連結な部分頂点集合に対応させる。
基礎点として5000点が与えられる。
G_embの方で部分頂点集合同士で隣接していた場合、+100点となる。
G_embの方で、ある部分頂点集合s(v)の頂点数が|s(v)|である場合、-Σ_v (|s(v)|-1)となる。
Gのすべての辺がG_emb側で隣接状態になっていた場合、ボーナスとして+100000点となる。
連結でない頂点集合だったり、不正な場合は0点となる。
最終得点が最大となるよう対応付けを求めよ。
最終的に提出したアプローチ
- 初期配置は、Gの頂点の近傍ができるだけ近くなるようにランダム配置し、それをできるだけランダムに伸ばせるだけ伸ばしたもの
- G_embの頂点を1つランダムに選び、その8近傍どれかにコピーする焼きなまし
時系列での振り返り
今回は考察重視で行きたいと思ってたけど、何が重要なポイントかは手を動かして見つけないとやっぱりダメだった。
初日~8日目(1日分ぐらい)
- HHMM1とだいたい似ていて、焼きなましが有効そうな形をしていたので、HHMM1の反省をしつつ焼きなましをちゃんと書こうと考えた
- 焼きなましについて勉強&&HHMM1の復習
- おそらく、全部焼きなましに任せるとアレなので、HHMM1と同じように「形を固定化して割り当て問題」か、「近傍のうまい定義」をすればひとまずよさそうか、とか考えていた
- 忙しかったり、体調不良であまり手を動かせず
10日目~12日目(1.5日分ぐらい)
- ひとまず、HHMM1復習のコードを流用してHHMM2用に書き直して様子見
- 実装が適当すぎて、スコアが差分計算できていないので、そこがボトルネックで回数稼げてないコードを作成
- ビジュアライザーは、テキスト出力の簡素なモノしか用意してなかった
- で、どうも、回数稼ぐよりも、初期配置が重要そうな感じだったので、初期配置を中心に考えることにしたが、前半「形の固定化して割り当て問題」を考えていた時のアイデアとか完全に忘れてて、0ベースで考え直し
- 斜めだと、線をまたぐことができるので、平面グラフ的でなくても連結にすることができそうなので、斜めが肝っぽい
- 前半の時の紙を見るに、形状のアイデアとしては、斜め直線型やダイヤモンド型をうまく配置させられれば多くの頂点に絡みそうと考えたらしい
- 直線型よりもうにゃうにゃ絡み合う方が期待できそうな気もするので、ランダムに線を伸ばす感じのコードを作成(最終提出のやつ)
- で、ここで(なぜか)ボーナス点を取りに行っていないことが気になって、上位とはそこが差になっていると考えたため、できるだけちゃんと辺をつなぎに行くような方法を考える方に走った
- グラフが大きくなってもG_emb側で全連結になるよう辺をつなぎに行けるうまい方法が思いつけず、結局時間を無駄にしてしまって終了
13日目
- あきらめて、書いてたコードを提出
- 14日目は時間取れないのがわかっていたのでここで終了
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017参加記
概要
AtCoderで開催されたマラソンマッチに参加してみた。終了30分前なので、時系列で振り返ってみる。
システムテスト前のスコア・順位は156,999点で66位/298人。おそらくシステムテスト後は順位下がる・・・
最終順位は720,841点で62位でした。
今回は知り合いと競争してて、知り合い内では3人中3位という感じで効率の悪さと実力不足が明らかになったなぁという感じ。
とはいえ、マラソンマッチはちゃんと参加できたことがなかったのに対し、今回は比較的時間使えていたので、完敗。
問題
重み付き無向グラフGが与えられる。そのグラフの頂点を別のグラフG_embの頂点にマッピングする。
もしG_embにマッピング後、G_embでの頂点で隣接辺だった場合、Gでの辺の重みが適用される。
G_embはKing's Graphというグリッドの斜め方向頂点にも辺をつないだグラフが与えられる。
マッピング後のG_embでの重みの合計が最大になるような頂点のマッピングを求めよ。
最終的に提出したアプローチ
- まずは山登り
- その後、グラフが密な場合はちょくだいさんサーチっぽいの、疎な場合は焼きなましのハイブリッド
- 頂点のマッピングは、G_embの中心から渦巻き状に広げていく形で決め打ちし、何番目にどの頂点を割り当てるかを考えた
- ちょくだいさんサーチっぽいのは、重複排除がうまくできなかったので、各番目で上位数件で切り捨てる感じで多様性を確保する感じ
- 焼きなましの方は、2-optっぽく、適当に2点選んで交換するので近傍探索。悪化した場合での採択率を山登り時点でのスコアとかで微妙に変えてる
- 評価値は生のスコア
時系列での振り返り
初日
- 問題理解自体は簡単そうな雰囲気だけど、どこらへんが難しいポイントかわからないので、数日は適当に実装しながら考えた
- 初日は「ビームサーチ」か「n手先読み」を考えてた
- 実装は適当に1点を決めてそこから8近傍に頂点を増やしていく感じで、先読みを1ターンだけするものを書いた
2日目
- 状態数が多すぎて試せる分量が少なすぎるので、8近傍に頂点を広げていくビームサーチを実装しようと書いてみた
- この時点では適当な調整をして148kぐらいだったけど、サイズが大きい場合に探索量が多くTLEしてしまったりスコアに大きな差がでてしまう問題があった
- というか、ビームサーチの時間のコントロールが難しいというのが身をもってわかった
3日目
- ビームサーチではなく、他の方法もありそうか考えてた
- 決定的な手法とか、マッチングとか
- 焼きなましとか試してみたけど、うまくいかず、ちょくだいさんサーチっぽい感じで何回も最初から最後までを繰り返す感じの探索でやってみたら悪くなさそうだったので、この方向で書きはじめ
- ここで、ビジュアライザーを作ってないことが気になったので、C#で最終状態を出力する雑なものを作成
4日目~5日目
- ビジュアライザー見ると、形がひどいときがあることに気づいた(上みたいなの)
- ある程度中央付近に固まっていた方が都合がよさそうだろうと思って、距離が離れるほど評価値が下がるように書いた
- けど、うまくいかなくて、ここで、「どこに何を」割りあてるかだと状態数が多くなりすぎるので、形を決め打ちして「何を」割りあてるかだけにすればよさそうと気づいた
- 形はいろいろ考えられそうな気がするけど、とりあえず中心からグルグル渦巻き状に増やすようなものを考えることにした
- 形の最適解の考察としては探索結果を見る感じだと平行四辺形っぽい形が多いので、辺の数的にもそういう形だろうと考えてた
- けど、最後そこまで調整たどりつけなかった
6日目~7日目
- メモリの制約からpriority_queueで保持する状態数に限りがありそうなので、適当に状態を削って探索
- ただ、サイズが大きい場合は、十分な探索ができてなくて、イマイチスコアがでない
- 他のアルゴリズムに浮気しつつ手を動かしてたけど、ダメだった
8日目~11日目
- ここらは、ちょっと細かい考察と実験をしながら、提出の方はパラメータとかちょこちょこ変更して提出する感じで進めてた
- 多様性確保のための状態の間引き方でうまい方法が思いつかず、ネットで情報調べたり勉強したり、いろいろ試してた
- いろいろ取り入れようとすると探索量が減ってスコアが下がることを繰り返しててて、つらぽよ
- あと、n手先読みとかペアを作ってからそれをくっつけてく方法とか別アプローチを試したりしてたけど、どれもイマイチで、つらぽよ
- この時点での提出の最高点は154kぐらい
12日目
- いろいろ出力して観察していたところ、どうも焼きなましっぽい動きをしてそうに見えたので、焼きなましでいけないか検討始めた
- すると、調整が雑でもスコアが結構伸びた(!)
- しかし、スコアが大きい場合、ちょくだいさんサーチっぽい方がスコアがよかったので、焼きなましとハイブリッドで実装
- この時点での提出最高点は156kぐらい
13日目~最終日
- 高速化を試していないことに気付いたので、時間計測とかintをshortにとかを置き換え
- あと、cinをscanfにしたりしたらなぜかスコア下がったりして最終提出は変えなかった、、、
- 500点ぐらい増えて最高スコアの156,999
- ただ、何回か提出してみると、上振れスコアのようで、再提出すると数百点平気で下がってしまう運任せコード
- 受理率が悪すぎて効率の悪い探索ばかりしていそうだったので、近傍の定義を効率化しようとして、ランダムに任意地点の2点をswapするのではなく、隣同士の2点を交換し続ける感じで書いてみたけどスコア悪化
- あとは冷却スケジュールと評価関数が何もできていないので、そこを最後に詰めようと実験
- 冷却スケジュールの方は、診断人さんまとめの焼きなましページを参考に、ちゃんと調整してローカルだと+600点ぐらいになったので、喜々として提出したら下がって絶望
- 評価関数はいい形悪い形とかで加点減点を追加したらスコアが下がってしまって絶望
- 頂点の辺の合計とか、何番目に大きい辺を使ってるかとか
- 最終日で調整する時間がないのに、ローカルとオンラインのスコアの相関がなくなってて、絶望しながらオンラインの提出調整するしかなかった
- 絶望
- 絶望
- 結局点数上がらないので、上の提出最高得点のコードを最終提出して、絶望のうちに終了
最終提出後~寝るまで
- 振り返ってみてみると、焼きなましの受理率がものすごく悪いし、無駄なスワップとか繰り返しまくっているのでだいぶ改善の余地がある
- 探索量とかは結構稼げてるから「焼きなまし+評価関数工夫+ヒューリスティックルール」が正解だったかなぁとか思う
- あと、問題の切り分けとして、グラフの密度が「密」「疎」「スコアが大きい」あたりで分けて考えたけど、「疎」と「スコアが大きい」時が重要なのに全然詰められていなかった・・・
- ビジュアライザーは、最終結果を見るものしか作れてなかったけど、「やりながら見る」や「やってる途中経過(探索しているもの)を確認できる」ようなものを用意しないと厳しいなと思った
- 他にも試したけどここに書いていないものは、みんなの解答出てから反省時に振り返りたい
ARC085 D. ABS
問題
N枚の山札が与えられる。上からi番目のカードの数字はa_i。
XさんとYさんが、この山札を使ってゲームをする。最初にXさんはZが書かれたカード、YさんはWが書かれたカードを持っている。
2人は交互に「山札の上から1枚以上のカードを取り除く。最後にひいたカード以外は捨てる」という行動を繰り返す。
山札がなくなるとゲーム終了で、最後のスコアは両者のカードの数値の差の絶対値となる。
Xさんは最終スコアが最大化するように、Yさんは最終スコアが最小化するように行動する場合、最終スコアはどうなるか?
制約
- 入力はすべて整数
- 1 <= N <= 2000
- 1 <= Z,W,a_i <= 10^9
解法1
ゲームの先読み。
Yさんがi番目までカードを引いたとする。
Xさんはi+1番目から何枚かのカードを引くことになるが、このとき、最終スコアがどのようになるかがそれぞれの枚数の時でわかっていれば、それで最適な枚数を引けばよい。(Xさんは最大化したいので、最終スコアが最大になる枚数を引くことになる)
int dp[pos][turn] := turnさんの番で、相手がposまでカードを引いてる場合の最終スコア
として、メモ化再帰すればO(N^2)で求められる。
// ZとWはカードの数値を入れた配列vの最初2つに入れておく int dp[2005][2]; int dfs(int pos, int turn){ if(dp[pos][turn] != -1) return dp[pos][turn]; int ret = (turn==0)?MIN:INF; REP(i,pos+1,N){ int tmp; if(i == N-1){ tmp = abs(v[pos]-v[i]); }else{ tmp = dfs(i,1-turn); } if(turn == 0){ ret = max(ret, tmp); }else{ ret = min(ret, tmp); } } return dp[pos][turn] = ret; } // dfs(1,0)が答え
解法2
想定解法はO(1)。
最初、Xさんが取れる行動はいくつかあるが、「全部取る」「1枚残す」だけ考えればよい。
全部取る場合、Xさんはa_N、YさんはWになる。最終スコアはabs(a_N - W)。
1枚残す場合、Xさんはa_{N-1}、Yさんはa_Nになる。最終スコアはabs(a_{N-1} - a_N)。
2枚以上残した場合、Yさんは1枚残して最終スコアをabs(a_{N-1} - a_N)にすることができる。
なので、Xさんの最終スコアはabs(a_{N-1} - a_N)より大きくはならない。(そうできる場合はYさんによってabs(a_{N-1} - a_N)にされてしまう)
結局、Xさんは、abs(a_N - W)かabs(a_{N-1} - a_N)かの2つしか選ぶことができないので、どちらか大きい方になるように行動するしかない。
反省
コンテスト中は無駄な状態を考えて、
dp[i][j][turn]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目でturnさんの番が回ってきたときの最大スコア
を考えてしまっていた。
けど、「1枚以上取る必要がある」ので、自分の持ってたカードの数字は保持しておいても意味がなく、結局i,jの2つ区別して持つは必要ない。
一応、メモリの持ち方をdp[N][N]にして考えることもできて(turnの部分はiとjを見て決められるので不要)、dp[i][j]として、
dp[i][j]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目のときの最大スコア
として考える。
i,jを見てどちらの手番かがわかり、かつ、手番の方のiまたはjの値は依存しないので、i,jで小さい方がiだった場合、0~j-1までのdp[i][j]の値は同じなので、1回だけ計算すればよい。
for(int i=N-1; i>=0; i--){ for(int j=N-1; j>=0; j--){ if(i == j) continue; //あり得ないパターンなので無視 if(i == N-1 || j == N-1){ //最後のカードを取った場合 dp[i][j] = abs(v[i]-v[j]); } else{ int ret = (i<j)?MIN:INF; if(i<j){//Xさんの手番 if(i == j-1){ REP(k,j+1,N){ ret = max(ret, dp[k][j]); } }else{ ret = dp[j-1][j]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー } }else{//Yさんの手番 if(j == i-1){ REP(k,i+1,N){ ret = min(ret, dp[i][k]); } }else{ ret = dp[i][i-1]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー } } dp[i][j] = ret; } } } //dp[0][1]が答え
yukicoder No.595 登山
問題
N個の地点が1~Nまで順番に直線上に並んでおり、地点iの標高がH_iで与えられる。
地点1からスタートし、すべての地点に1回以上訪れたい。終了地点はどこでもよい。
移動は2種類あり、「隣接地点に移動する場合、登る方向に移動する場合のみ標高の差」か「ワープによる任意地点への移動にはP」のエネルギーがかかる。
最小エネルギーを求めよ。
制約
2 <= N <= 2*10^5
0 <= P <= 10^9
0 <= H_i <= 10^9
解法
コンテスト時間中は、左から順に、隣が登る場合はワープして降ってくるor登るか、隣が降る場合は隣に降るかその地点にワープする感じで、
dp[i][x] := i地点までの最小エネルギーで、i地点にいる場合x=0、いない場合x=1
というのを更新していく感じで書いていた
しかし、降る場合について、右から登ってくるルートを考慮できておらず、
のような場合、「地点1→地点3→地点2→地点1→地点4→地点5→地点7→地点6→地点5」というルートを考えてしまっていた。
(この場合の最小ルートは「地点1→地点3→地点2→(地点1)→地点7→地点6→地点5→地点4」というルート)
左からも右からも降るか登るかすべてを考える必要がある。左右どちらからくるかを区別すると、
dp[i][x] := i地点に左から訪れている場合x=0、右から訪れている場合x=1の場合の、1~i地点までの最小エネルギー
とすれば、i-1とiの地点でのdpの値を考えて、
dp[0][0] = 0; REP(i,1,N){ // i-1 i // -> & -> dp[i][0] = min(dp[i][0], dp[i-1][0] + max(0LL,H[i]-H[i-1])); dp[i][0] = min(dp[i][0], dp[i-1][0] + P); // -> & <- dp[i][1] = min(dp[i][1], dp[i-1][0] + P); // <- & -> dp[i][0] = min(dp[i][0], dp[i-1][1] + P); // <- & <- dp[i][1] = min(dp[i][1], dp[i-1][1] + max(0LL,H[i-1]-H[i])); dp[i][1] = min(dp[i][1], dp[i-1][1] + P); }
のような遷移を考えられる。
答えはdp[N-1][0]かdp[N-1][1]の小さい方。
AGC017 C. Snuke and Spells
問題
N個のボールが一列に並んでおり、各ボールには数字が書かれている。
魔法を使うと、今あるボール個数と同じ数字が書かれたボールを消すことができる。また、魔法は連続的に行うことができる。
例えば、{1,3,3}だった場合、魔法を2回連続で行うと、{1,3,3}->3個あるので3が書かれたものが消える->{1}->1個あるので1が書かれたものが消える->{}となる。
各ボールは単位時間ごとに、ボール1個だけ数字が変化することがわかっており、変化する回数はM回であることもわかっている。
ここで、各単位時間ごとのボールの状態に対して、いくつか数字を書き換えて連続魔法で全消しができるようにする最小書き換え回数を求めたい。
制約
1 <= N,M <= 2*10^5
1 <= ボールの数字 <= N
1 <= 変化するボールの場所 <= N
1 <= 変化した後の数字 <= N
解法
まずは、あるボールの状態に対して、ボールの最小の書き換え回数を求める問題を考える。
魔法を発動するときのボールの位置は無関係なので、あるボールの状態をソートしたものを考える。
例えば、{1,3,3,5,5}のような場合、魔法を連続発動することで、全消しができる。
どういうときに全消しができるか考えると、
i 1 2 3 4 5 x 1 3 3 5 5
インデクスが5から5が2個、3から3が2個、1から1が1個、、、と、NからNがa個、N-aからN-aがb個、、、と続けられればよいことがわかる。
また、例えば、
i 1 2 3 4 5 x 1 3 3 4 4
の場合は、インデクスが5のとき値が4なので、全消しすることができないことがわかる。
たとえば、この4を5に書き換えると、インデクスが5から5が1個、4から4が1個、、、となり全消しができる。
ここで、全消しができる条件を考えると、各インデクスの部分について、ボールの数字で、すべてのインデクスをボールの数字の連続でカバーできるかどうか?になっている。(上だと、各数字のインデクスのところから各数字の連続ですべてのインデクスをカバーできている)
(難しいが)、これを扱うのに、数字aについて、[a-数字aの個数,a]という範囲を考える。
上の全消しができない場合の例{1,3,3,4,4}を考えると、カバーしている範囲の数を各インデクスで考えると、
i 1 2 3 4 5 r 1 1 2 1 0
のようになる。
5のときカバーできていないので、他の2以上になっているところから5のところに数字を書き換えてあげれば全面カバーができることがわかる。
ここで、書き換えてあげる必要がある数字の個数というのは、カバーされていないインデクス==0になっているところの数なので、これを求めてあげればよい。
数字が変化した場合は、各数字の個数から上のカバーしている範囲の数のところが1か所減って1か所増える、という変化を起こすので、各単位時間での変化はO(1)で更新できる。
前の状態で0の個数がわかっていればこの更新時に0になるかどうかみれば、こちらもO(1)で更新できる。
AGC017 B. Moderate Differences
問題
N個のマスの一番左にA、一番右にBが書かれており、それ以外は空白になっている。
いま、空白のマスに、以下の条件を満たすように数字を入れることができる。
- 隣接するどの2マスについてもその差はC以上D以下
このとき、条件を満たすように数字を入れることができるかどうか判定せよ。
制約
3 <= N <= 5*10^5
0 <= A,B <= 10^9
0 <= C <= D <= 10^9
変数はすべて整数
解法
Aの右隣の空白に何を入れられるか考える。
条件から、減らす方向に[A-D,A-C]と増やす方向に[A+C,A+D]の範囲の数字を入れることができる。
続けて、その隣には、ひとつ前の範囲[x,y]に対して、[x-D,y+D]の範囲が該当する。
最終的に、Bのマスまで来たとき、範囲にBが含まれているものが存在すればYESと答えられる。
しかし、この方法では、マスを進めるにつれ、範囲の数が2倍になっていくので、指数関数的に大きくなっていってしまう。
また、各マスで範囲が重なるような部分をマージするような方法をとったとしても、C==Dの時を考えればわかるように、範囲の数が多くなり、計算量が線形ではなくなるのでTLEしてしまう。
ここで気づきたいのは、各マスでは、「減らす方向への範囲更新」と「増やす方向への範囲更新」の2つの変化をさせられるが、これを行う順番はマスの位置に依存せず、それぞれを何回行ったか?だけでBのマスでの範囲が決まる。
増やす方向の回数をX回、減らす方向の回数をY回とすると、Y=N-1-Xとなる。
このとき、Bマスでの範囲は、[A+X*C-Y*D,A+X*D-Y*C]になる。
Xは、0回~N-1回まで考えられるが、それはループを回せばよいので、範囲内にBが入るかどうかを試せば、O(N)で求められる。
反省
変なコード書いてメモリ使い切ってPC再起動とかやらかしてしまっていた。
(さらに強制終了したせいでPC調子悪くなってダメ)
ちゃんと、計算量的使用メモリ的に問題ないアルゴリズムを考えてから書き始めること。