Hatena::ブログ(Diary)

antaの競技プログラミング練習日記

2014/03/30

今までの自分のライブラリを公開します 2014

https://db.tt/KixudqAX
ライセンスはCC0です。何でも自由に使って・コピペ・改変・再配布してよいです。これを使用した場合のいかなることにも責任を持ちません。
'#'で始まるファイルは未検証、'!'で始まるファイルは検証済みであることを表していましたが、あんまり一貫していません。それがついていないファイルもあります。サブフォルダに入っているものが別に特別ということはありません。
ライブラリまとめ.txtに自分と他の人のライブラリをまとめてあります。このファイルが一番重要かもしれません。
去年のものと特に重複は除いていません。更新されているファイルもあります。

2013/11/19

ちょっとしない解き方メモ色々 part2

part1

フィボナッチ数の小ささ

fib(n)は指数オーダーで結構大きいが、2^nよりは全然小さい。
"SRM 451 DIV1 Hard BrickPuzzle"は列DPを特定の形のブロックでするもの。ブロックの形が、下側が絶対2つ単位で隣接しているため、そのような形の状態しか覚えなくてよい。このような状態の数はfib(n+1)になる(漸化式を見ればわかる)。2^nでは大きすぎるが、fib(n+1)はギリギリ小さいため解ける。実際にはMLEにならないために状態にインデックスを付ける必要がある。

コストで直接辞書順最小を求める

part1で紹介した"辞書順ペアをコストにする"のさらなる一般化。大事なのは、計算量は漸近的には変わらない(たぶん)が、ビット並列化のようなことで高速化できるということ。
"SRM 457 DIV1 Hard TheSquareDivOne"では普通にやってはギリギリ時間に間に合わない(実際には定数倍高速化を頑張れば通る)が、これを利用することで余裕を持って通すことができる。自分は実装に固定長の多倍長整数のようなものを使ったが、「先頭から整数に収まる範囲だけやり、それを固定して次の範囲へ」というように普通の辞書順greedyとのハイブリッドにやることでもできる。
また、自作の問題"最初のコンテスト - E 辞書順最大の経路履歴"(問題文)でも同じようなテクニックが適用出来る。この場合はダイクストラ法の重みとして多倍長整数を採用する。なお、その問題はunion-find-deleteのようなもので解けるように思えるが(当時知らなかったし、今でもわかってない)…どうだろうか。

整数計画を分岐限定法で?

ヒューリスティックとかあまり実装しなくても、問題がうまくLPとフィットすれば解けるかも。
LPのboundが効率的に効くような問題では十分解けうる。変数の数が多かったりすると、ナイーブな実装ではMLEとなってしまうことが多いかもしれないので、変数の範囲はまあまああるが変数の数が少ないような問題がいいかもしれない。
"SRM 488 DIV1 Hard TheBoringGameDivOne"では何のヒューリスティクスも無しのプレーンの分岐限定法でも1ケース以外は通る。さらに、変数を割り当てる前にその範囲をLPで制限するようにしたら(これは何と呼ばれているのかわからない)全ケース通った。この問題は変数の数が9と少ない。また範囲も0〜1000と比較的少ない。しかし当然1000^9はできないわけだが、実際に解けた。
もっと実装すれば、もっと色々な問題が解けるかもしれない。解ける率を考えるとライブラリとしてそれなりのものを実装するのはありかもしれない。

浮動小数点数重みの最短路は誤差に注意

Dijkstra'sやFSPAなどは特に注意。誤差によって負サイクルができることがあり、負サイクルがあると無限ループしてしまうからだ。
最短路はそのままの形だけでなく、様々なアルゴリズムのサブルーチンとしても用いられることに注意する。特に多いのが最小費用流、特に重み付き2部マッチングである。
最小費用流のPrimal-Dualではポテンシャルを加減算する関係上誤差が大きくなりやすいように思える。
例として、"SRM 491 DIV1 Hard FoxCardGame"は浮動小数点数重み付き2部マッチングを使う。実際自分はこの無限ループのせいで1回Failしてしまった。
最小費用流のPrimal-Dualの場合、

Weight d = dist[i] + edgeCost + potential[i] - potential[j];
if(d < dist[j]) ...

のようになると思うが、これに1行足す。

Weight d = dist[i] + edgeCost + potential[i] - potential[j];
if(d < dist[i]) d = dist[i];	//*
if(d < dist[j]) ...

こうすることで解決できる。
Dijkstra'sでなく負辺も存在する場合はEPSを適切に使って比較すればよい。

サイズごとの総和で包除原理

包除原理の±はサイズによって決まる。つまり同じサイズの集合は全て同じ符号。
そのため、あるサイズの集合の総和を求めることができるなら包除原理ができる。
"SRM 498 DIV1 Hard FoxJumping"で使っている。この問題の場合はサイズごとの総和はsubset-sum数え上げのDPと二項係数などで求める。
包除原理といえば2^nかかると思ってnが大きい時できなそうだが、このようなやり方もあるということ。

Dijkstra's風で、単純な足し算以外の重み

Dijkstra'sは辺の重みを距離→距離の関数と考えたとき、その関数が広義単調増加なら正当(たぶん)。証明はしてないけどなんとなくそうっぽい?
普通の重みつき辺は重みが非負なら足し算関数はそれを満たすので正当であるといえる。
よくあるのは「ある時刻まで待つ」という重み。できるだけ早く行ったほうがいいのがわかる。
"SRM 479 DIV1 Medium TheAirTripDivOne"は周期的な区間を待つような形。これも明らかに広義単調増加なのでいけるといえる。
"SRM 462 DIV1 Hard WarTransportation"はmaxを取る。これも同様に正当性がいえる。

常識とか発想とか雑多な
  • 多項係数は二項係数のかけあわせになる。(n!/x_1!/x_2!/... = C(n,{x_1,x_2,...}) = C(n-_{j=1..i-1}x_j,x_i))
  • 隣同士に限定してもswapが自由な回数できるなら任意の順列を作れる(たぶんどんなswapなら任意の順列ができるか、とか考えられるのかな?知らないけど)
  • longest common prefix → 辞書順ソートする。"SRM 496 DIV1 Hard YetAnotherHamiltonianPath"とか"SRM 330 DIV1 Medium PrefixFreeSubsets"とか。
  • (rank(s)+k)番目を辞書順で求めたくて、rank(s)がlong longに入りきらないほど大きい時はsandwich(s≦x≦tとなるxの数)で数を数えるルーチンを作れればいける。"SRM 467 DIV1 Hard NextHomogeneousStrings"。ただ多倍長でもいけそうだが。
  • 連結成分の集合をsubsetとして数えるときには(ab)(cd)と(abcd)を重複して数えないように、連結成分が区切られる時に最低でも1つスペースを開けないといけないようにすればいい。"SRM 421 DIV1 Hard "TeamManagement"は木上。
  • greedyは分岐がある時に「片方の選択肢だったら絶対良い解になる」という優先順位をいかにつけられるかがポイント。辞書順greedyはその点自明。"SRM 429 DIV1 Hard SpecificPolyominoCovering"。
  • 平面上の矩形とかのunionの面積を求めるのはline-sweep的にやればΘ(n log n)とかでできる。"SRM 441 DIV1 Hard PaperAndPaint"。
  • 行列の足し算とか。それでバイナリ法とか。"SRM 444 DIV1 Hard AvoidFour"。この問題の解法頭良くて好き。
  • modが小さいとき、modをとった後の値ごとに考える(それが同じなら同じなので)。"SRM DIV1 Hard IncreasingNumber"。
  • できるだけ対角線上いようとするようなメモ化再帰でO(n)。"SRM 454 DIV1 Hard MegaSum"。
  • 2部マッチングで絶対使わないといけない頂点があるときは、それ以外の頂点を(k-そのような頂点数)の容量の辺に通すようにして制限する(それが負になったら絶対無理)。2部マッチング以外にも一般に同じような考え「重要なものを絶対使う <-> 重要でない物の数を制限する」が使えるだろう。"SRM 459 DIV1 Hard TheContest"。
  • 常に前の状態に戻れて、その「前の状態」という状態遷移にサイクルが無いとわかるとき、森である。"SRM 463 DIV1 Hard RabbitPuzzle"。この問題のこの状態が森で、さらに無限で一様であるから区別する状態数が少ないという議論はとても面白かった。
  • (_{i=1}^n x_i / n)以下の値x_jが必ず存在する。"SRM 468 DIV1 Hard MallSecurity"。
  • FPTの自明でないアルゴリズムであっても、DPなら柔軟性がある。"SRM 470 DIV1 Hard BuildingRoads"の解法は、steiner treeのDreyfus-Wagner algorithmの変形であるとみなせる。
  • "SRM 477 DIV1 Hard KingdomTour"のgreedyな、minimum cost flowのPrimal Dualにも似た謎アルゴリズム。practice roomの自分の解答(自分はzhuojie氏のものを参考にしたが、誰が最初に書いたかは知らない)参考。
  • Hyperplane separation theorem。2つの凸多角形が交差しないとき、それらを分割する直線が存在する(さらに多次元でも)。この直線はn^2試せば良いので、分割のし方もO(n^2)となる。"SRM 486 DIV1 Hard BatmanAndRobin"の肝。
  • グリッド上で各列で区間を決めるとき、それを領域として連結にするために区間の左と右を伸縮する順番を適切に決める。"SRM DIV1 Hard AmoebaDivOne"で綺麗に書けた。伸縮をインクリメンタルにやるDPで、縮める方を最初に縮めきってからもう片方をやれば、縮める方はもう片方より左右には縮まないので必ず連結にできるというテク。自分で思いついて、とても面白いと思った。

2013/11/18

ちょっとしない解き方メモ色々 part1

SRM400代のHardで使ったものを見てみる。最初は全部記事書こうかと思ったがめんどくさくてやめた。

桁落ち誤差回避

ほとんど等しい2つの数を引き算すると、有効桁数が減少する。
式変形をして引き算をなくしたりする必要がある。
SRM 400 DIV1 Hard CollectingBonusesではさらにlog1p関数を使ったりする。

凸多角形は上部と下部に分割できる

左・右でも同じ。
それぞれの折れ線がy座標の関数と見た時に凸・凹となることが重要。
SRM 401 DIV1 Hard NCoolでは、それを利用して多角形内の点を列挙している。
"SRM 493 DIV1 Hard AmoebaDivOne"でも凸多角形を生成するDPでこの性質を大いに使っている。

集合を求める時に順番が関係ないことを利用して、フラグで持たずにそのフラグが立っている数で持ったりする

一般的なテクニック。あえて言及するほどでもないかもしれない。
数値の辞書順最小を求めたい時には必ず桁数が単調なことを利用して数値が終わったかどうかをΘ(数値の数)の状態で持てる。SRM 403 DIV1 Hard TheLuckySumで言っているが、実際にはこの問題では桁ごとにも数値の順番を入れ替えられるので、辞書順最小ということはあまり関係ない。

変数を1つ以外固定して近づけてくサーチ

"SRM 405 DIV1 Hard ReasonableOdds"で用いられる。
一般にベクトル引数の最適化の手法としてあるものだと思う。名前知らない。

_{x=0}^[n-1} floor((a*x+b)/m) をO(log m)で

やばいアルゴリズム。
SRM 410 DIV1 Hard WifiPlanetの最重要部分。
応用は多そう。実際に全く別の問題SRM 406 DIV1 Hard ShortPathsでも使えて、漸近的な計算量を減らすことが出来る(と思う)。

凸とは限らない多角形内の何かを符号付き面積みたいに

SRM 410 DIV1 Hard WifiPlanetの1つ目のテクニック。
構造の差分上でのk番目クエリに対応しているデータ構造なら多角形内のk番目クエリにも使える気がする。

平面で領域が2色に分かれているとき、その両方のそれぞれを頂点として隣接を辺とすると木になる(?)

"SRM 411 DIV1 Hard MinimumTours"で使われる。
なんというか自明でないと思う。実際自分は解法を見た時驚いた。上の記述で合っているかどうかもわからない。
もし上の記述や理解が合っているなら応用性はかなりあると思う。

有理数上でもLCM,GCDが定義できる

"SRM 414 DIV1 Hard KPlanetaryAlignment"の肝。
"lcm(x/y,z/w) = lcm(x,z)/gcd(y,w)"。
整数上と同じく、周期を考える時に用いることが出来る。

重み付き数え上げのアルゴリズムで確率を求める(?)

"SRM 425 DIV1 Hard RoadsOfKingdom"の別解としてやばいアルゴリズムが存在する。
この問題は辺が存在する確率が与えられる時、全域木ができる確率を求める。
全域木はMatrix-tree theoremで数え上げられる。また、多重辺と考えれば重み付きバージョンもできる。
しかしそのアルゴリズムで確率が求められるというのだ。
辺がある確率をpとしたとき、重みをp/(1-p)に設定する。それで求めた後、(1-p)の総乗をかける。するとなんと確率が出るというのだ!
p=1の場合が0割りだが、特別扱いして連結成分を1つの頂点として適切にサイクルをチェックしたりしてもよいし、p=1-1e-10とするという方法もある。
なんでこれで求められるのかわかってないが、もしこれが一般的に適用できるのであれば応用は広がる。
determinantに限っても例えば有向木とかオイラー路とか平面グラフの完全マッチングなどがあるが…"もし"適用できたら面白いなあ。

Warshall-Floydで不等式を解く

うまくできる。あんまりわかってない。
"SRM 426 DIV1 Hard LongStraightRoad"や、最近では"SRM 586 DIV1 Medium History"で出されている。
SRM586ではみんな解いてるようなので、いまや常識らしい。

分割数の小ささ

分割数は指数オーダーだが、小さな方ではそれなりに小さい。だいたい(13^√n)/7n 程度。
「x個を順番関係なくいくつかに分割する」が分割数。
"SRM 427 DIV1 Hard PSequence"ではDPの状態として出た。一見制約が30で階乗オーダー・指数オーダーの解法は無理そうだが、実際の数は関係なく前の数と等しいかどうかだけを持てばいいことを利用すると分割数で抑えられて(Σ_{i=0}^30 p(i) = 28629)なので十分いける。

辞書順ペアをコストにする

"SRM 433 DIV1 Hard BarbarianInvasion"で最小カットとして出た。
最近では"Maximum-Cup 2013 - F 3人の騎士と1匹の犬"で重みつき二部マッチングの最小費用流として出た。

巡回する <-> 文字列としての2乗を考える

極めて典型的。

長くなったので分割。part2

SRM 413 DIV1 Hard TreeCount

問題 Editorial

問題

あるグラフに対して頂点集合Sがk-stableであるとは、S中のそれぞれの頂点に対して、隣接する頂点の中でSに含まれる頂点の数がk個以下であるものをいう。
木graphが与えられる。i∈[0..|graph|-1]のそれぞれでi-stable setの数をmod 112901989で求め、それをvector<int>で返せ。

  • 1 ≦ |graph| ≦ 50
  • graphは木を表している

解答

続きを読む

SRM 410 DIV1 Hard WifiPlanet

問題 Editorial

問題

整数座標x,yで単純多角形が与えられる。整数denomが与えられる。
全ての整数a,bに対して座標(denom*a,denom*b)を考える。この座標のうち与えられる多角形に含まれる座標すべてにwifiを置きたい(wifi点と呼ぼう)。wifi点はいくつあるか求めよ。

  • 3 ≦ |x| ≦ 50
  • 1 ≦ x[i], y[i] ≦ 10^9
  • 2 ≦ denom ≦ 10^9
  • i≠jなら(x[i],y[i])≠(x[j],y[j])
  • 多角形は単純。つまり、自己交差も端点以外の自己接点も持たない。
  • wifi点は与えられる多角形の辺・頂点上にはない。

解答

続きを読む

SRM 409 DIV1 Hard GridColoring

問題 Editorial

問題

rows×colsのグリッドがある。以下の操作をK回する:

  1. ランダムにセルを選び、それをAとする。
  2. ランダムにセルを選び、それをBとする。
  3. AとBを頂点とする矩形上に色を塗る

AとBは独立に選ばれる。セルは全て等確率で選ばれる。色は上書きされる。
K回操作をした後に色が塗られているセルの数の期待値を求めよ。

  • 1 ≦ rows, cols ≦ 1000
  • 0 ≦ K ≦ 100

解答

続きを読む

SRM 406 DIV1 Hard ShortPaths

問題 Editorial

問題

無向重み付きグラフで以下の条件を満たすものgraphが与えられる:

  • それぞれの頂点に対して、たかだか1つの単純閉路に含まれる
  • それぞれの頂点v,uに対して、vからuへのsimple pathはたかだか1つ

頂点start,finishと正整数kが与えられる。startからfinishへのpathのうち、k番目に短いものの長さを求めよ。ただしk番目が存在しない場合は-1を返せ。

  • 2 ≦ |graph| ≦ 50
  • graphは問題文の条件を満たす
  • 1 ≦ それぞれの重み ≦ 9
  • 1 ≦ k ≦ 10^12
  • start ≠ finish

解答

続きを読む

SRM 404 DIV1 Hard SoftwareCompanies

問題 Editorial

問題

いくつかの企業がある。それぞれの企業はデータを処理して独自形式のデータにする。
企業はそれぞれデータの処理数に上限がある。また、処理できるデータの形式にも制限がある。もちろん、データ処理の仕事の依頼にはコストがかかる。これは、処理するデータ量にかからわず、1データでも処理するなら定額のコストとなる。
i番目の企業の企業名を表すnames[i]、処理できるデータ形式の集合を表すprocess[i]、仕事依頼のコストを表すcost[i]、処理数の制限を表すamount[i]がそれぞれ与えられる。
さらに企業名company1とcompany2が与えられる。company1の形式のデータをcompany2の形式のデータに処理したい。処理できるデータ量はできるだけ多くしたい。その中でかかる合計のコストを少なくしたい。そのうちで辞書順最小の企業名のリストをvector<string>で求めよ。

  • 2 ≦ |names| ≦ 12
  • 0 ≦ cost[i] ≦ 1000000
  • 1 ≦ amount[i] ≦ 1000000
  • company1 ≠ company2

解答

続きを読む

2013/11/17

SRM 403 DIV1 Hard TheLuckySum

問題 Editorial

問題

lucky numberとは、それを10進数で表記したときに4と7しか現れない正整数である。
整数nが与えられる。nを複数のlucky numberの総和で表す。lucky numberの数を最小化したい。そのような解のうち、辞書順最小のlucky numberの列を求めよ。ただしnがlucky numberの総和として表せないときは空配列を返せ。

  • 1 ≦ n ≦ 10^9

解答

続きを読む

SRM 402 DIV1 Hard IncreasingSequence

問題 Editorial

問題

'0'〜'9'からなる文字列digitsが与えられる。
この文字列をいくつかに分割し、それぞれを整数として読む(leading zeroは許可され、単に無視される)。ただし、列はstrictly increasingでなければならない。
このような列の中で、最後の整数を最小化したい。そのような列の中で辞書順最大の列を求め、その列の総乗を求めよ。

  • 1 ≦ |digits| ≦ 2500

解答

続きを読む

SRM 401 DIV1 Hard NCool

問題 Editorial

問題

凸多角形(x,y)が与えられる。
ある整数点がN-coolであるとは、多角形の中(辺上も含む)にあって、少なくとも1つのN-coolな線分の端点となっていることである。
ある線分がN-coolであるとは、多角形の中にある整数点を少なくともN個含むことである。
nが与えられる。n-coolな整数点を数えよ。

  • 3 <= |x| = |y| <= 50
  • 0 <= x[i], y[i] <= 10000
  • 与えられる多角形の中に含まれる点の数は500000を超えない
  • 2 <= n <= 500000

解答

続きを読む

SRM 400 DIV1 Hard CollectingBonuses

問題 Editorial

問題

飲料メーカーがキャンペーン中。
ジュースのボトル1つと引き換えに、nつの異なるコードのうちランダムな1つが等確率で得られる。
kつの異なるコードを得たい。
それが達成されるのに必要なボトルの数の期待値を求めよ

  • 1 ≦ k ≦ n ≦ 10^18

解答

続きを読む

SRM400〜500のDIV1Hardを読み、77問を解いた

見た問題の表 - antaの競技プログラミング練習日記
解けてないものや、Editorialがないので解法がわからないものなどもあるが、77問は解法を見る見ないにかかわらず自分でコードを書いた。
Hardは新たなテクニックを知ることのできるからいいね。
とりえあず、解いた問題は解法を再認識するためにこのブログに記事を書く。

2013/11/16

Maximum-Cup 2013 本番

http://maximum-cup-2013.contest.atcoder.jp/

Problems

A

最初関節点???二重連結成分???とかよくわからなかった。
その後「まず最小の本数」なことをきちんと考え、「3頂点以上あれば、Hamiltonian cycleだな」と気づいた。
これは普通にbitDPすればよい。
しかしなぜか「2頂点の時は辺が1つ必要だな?」と勘違いしてWA。これはとても後になって気づいてなおしてACした。

B

入力の数が明記されてないがどうせ解けるくらいしかこないよな…と思いつつとりあえず素数列挙して試し割りするだけで通った。

C

線分交差判定するだけ。
幸い厳密な判定をするライブラリを書いてあったので簡単に通せた。

D

たぶん(G_i,G_j)の二等分線をG_kとの距離で制限した線分上のダイクストラだろうなーと最初に思った。
しかし幾何は苦手でEPSとか嫌だったので無視した。
最後に解こうかと思ったがどうも幾何は苦手でできなかった。
ちなみに上に書いてあるような線分の集合を「ボロノイ図」と言うらしい(名前は知ってたけどあんまり知らなかった)。

E

期待値の線形性でやるだけ?と。明らかに「のろのろウサギ*(N)」の節が怪しいのでClar飛ばして後に回す。でもClarでは「問題読んで下さい」としか言われなかった…
わからなかったのは「10枚目ごと」と書いてある、この初期オフセットというかなんというか。
たとえば「5,15,25…枚目に出る」となっていても問題文の条件を満たすように思えるのだけど…
まあ「10,20,30…枚目に出る」と仮定して解いた。
が、WA。と思ったらしょうもない所でミスっていた:

if(name.find("Alicia")) ...

直してAC。

F

Clar飛ばしたりしてた。
解法は割とすぐ浮かんだ。重み付き2部マッチング。
コストは(-魔力,距離)の辞書順順序のペアで持つようにすれば「魔力最大」の制約を満たす。ペアは適切なlong longで大きな基数を考えて持ってもよいし普通にペアを持って足し算・negate・比較を定義してもよい。
この優先順位のあるコストを直接大きな基数を考えたコストでやるテクニックは"SRM 433 DIV1 Hard BarbarianInvasion"でやったので思いつけた。
さて、WAった。よく考えるとMinimumCostMaximumFlowであるから、魔力0の人がいる場合にそれにマッチしようとしてしまうようだ。これは単に魔力0の人を無視すればよい。AC。

G

(階層,x,y,min(レベル,101))で持ってダイクストラやるだけ?と。とりえあず実装することに。
「階段の移動に1単位時間かかる」を見逃してデバッグしたりして、実装できて、提出。
さて、WA。
本当によくわからなかったが、最後のケースでだけ落ちているようなので基本的には問題ないはず。問題文をよく読むことに。
それなりに時間がたったのち、気づいた!思わず「あぁー!」と声を出してしまった。
今の地震の影響で現在いる階から下の階に下りられなくなっている ことが判明しました!

現在いる階から下の階に下りられなくなっている!!!!!
つまり、90階のマップが与えられているとしても初期位置が95階であったら95階から94階に行くことはできない!
それに気づけたら後は簡単。数行直して提出。AC!

H

2分探索でacyclic判定するだけ?と。
座標圧縮でp[i]∪l[i]∪r[i]だけ考えればいい。なぜなら、まず辺が張られない場所は矛盾と関係ない。次に、辺が包含関係にあるならその辺の少ないほうは無視しても同じ。だから。
速度が気になったが提出。AC。

I

最後に開いた問題。
さて、ハミルトン路。
色々考えると、へびの胴体の状態は別に保存しなくても良いことがわかった。なぜなら胴体の番号をxとすると、(x-1)ステップ以上経った後なら「この胴体は既に訪れた場所にある」、つまり「明示的に胴体を避けなくても訪れたかどうかだけ判定すれば良い」ことがわかり、(x-1)ステップ未満では「この胴体は最初に配置されている番号(x-ステップ)の胴体の場所にいる」ことがわかるので、つまり「ステップ数だけで判定できる」、また「ステップ数は既に訪れた場所の数で計算できる」。
さて、枝刈り全探索+メモ化でもするか、と。
状態は(頭x,頭y,壁または通った場所のbit mask)。
とりあえずdx,dyの順番をランダムに試すようにしたけれどこれは関係あるかはわからない。
枝刈りとして、「連結成分が2つ以上になったらもう達成できない」をやった。さらに連結成分の個数が2つ以上かどうかは(壁または通った場所のbit mask)だけで判定できるので、それを別個にメモした。
dx,dyをrandom_shuffleするところでグローバルのdx,dyを書き換えてしまうというバグで1WAして時間をつかったが、直して提出。
TLE,MLEが気になったが案外52ms/1936KBでAC。

J

明らかに座標圧縮して2次元クエリやるだけ。WaveletMatrixでもいいかなと思ったが入力数が明記されていない以上TLEが怖く、できる限り高速なFenwick木を動的に使うテクでやることにした。
実際にはインデックスを左から見ていき、a[index-k]の場所に1を足す、ということをすればよい。
あっさりAC。だが565msだったのでWaveletMatrixではTLEしていたかもしれない。
単にRMQ・あるいは単に右端もしくは左端からの最大値を単に計算などの解法で簡単にできるようだ。

結果

A: +100 (-1) (180:56)
B: +100 (22:30)
C: +100 (29:13)
E: +100 (-1) (61:21)
F: +100 (-2) (92:17)
G: +100 (-1) (147:20)
H: +100 (160:11)
I: +100 (-1) (288:47)
J: +100 (408:47)
Total: 900 (-6) (408:47)
Rank: 2/84 (正の点数のうち)

コメント

まあ良かったかな。ただ幾何の苦手さは良くないよね。それさえ上手くやれば全完行けたかもしれないわけだし。
アルゴリズムが思い浮かんだのはよかった。だがまあ難易度は比較的低めであるので全部わかるのが当たり前なのかもしれないが。
WAも全体から見たら少なめだが、深くはまらなかっただけでWA自体は6つもあるわけで。WAは本当になくしたい。

コード

A: http://maximum-cup-2013.contest.atcoder.jp/submissions/117886
B: http://maximum-cup-2013.contest.atcoder.jp/submissions/117099
C: http://maximum-cup-2013.contest.atcoder.jp/submissions/117141
E: http://maximum-cup-2013.contest.atcoder.jp/submissions/117323
F: http://maximum-cup-2013.contest.atcoder.jp/submissions/117486
G: http://maximum-cup-2013.contest.atcoder.jp/submissions/117741
H: http://maximum-cup-2013.contest.atcoder.jp/submissions/117789
I: http://maximum-cup-2013.contest.atcoder.jp/submissions/118311
J: http://maximum-cup-2013.contest.atcoder.jp/submissions/117832

2013/11/08

約1時間30分間気付かなかったミス

数を長さNで循環シフトさせて、その後の偶奇を知りたかった。

if((x - shift + N) % N % 2 == 0) ...

としなければいけないところを

if((x - shift) % 2 == 0) ...

とかしていた。
当たり前だが、((x mod m) mod n = x mod n)は一般には成り立たない。
例えば((9 mod 3) mod 2) = 0 だが、(9 mod 2) = 1。

今回の場合、1回考えて書き直したらこのバグは直っていたかもしれない。
書きなおすことも考えよう。

2013/11/02

SRM 596 DIV1 本番

少し調子が悪かった。

Coding

Easy (250)

最初全くわからず、焦った。
なんていうか2倍の操作は共有されるけどそれ以外は独立だから全部独立に求めた後上手く合成すればいけるのでは?と考える。
とりあえずDPで(数 * 2倍を使った回数 -> 最小のインクリメント回数)を求める。
さて、それを合成するにはどうしたら…
2倍にする回数は全部で固定なのでそれを全部試せばいいんじゃね?と、解けた。
テストをしてから提出。

Medium (500)

全然わからず。とりあえず辞書順最小はN*60回判定するのでいいな、とかは考える。
なんかマッチングとかフローっぽいな、とか考えながらうまく進められずに時間が経つ。
その間にいろいろ考えた。
まず、各ビットでそれを含む数の個数は2以下である必要がある。また、各数同士の無向ペアに対して少なくとも1つビットを共有してなければいけない。つまりグラフを考えるとクリークである必要がある。
ここまでわかってもそれをどう適用したらいいかがわからず時間が経つ。そして残り25分くらいの時にやっと思いついた。
(ビット位置, 各ペア)の二部グラフを考えて、そのビット位置がそのペアに含まれることができるならそこに辺を張る。そして全てのペアを使うマッチングが存在するかどうかを判定する。
さて、どこに辺を張れるかをどのようにして決めればいいのか?これは残り10分くらいでやっと思いつけた。
まず、そのビットがこのペアのどちらか片方で既に決まっていて(subsetに含まれていたり、既に決定されている)、その値が0なら張れない。
また、このビットを既に決めている数が存在して、その数がこのペアのうちどちらでも無い場合も張れない。
あとすこし引っかかったところが。辞書順最小greedyとはいっても、(subset以外の列が辞書順最小 <-> (答え = subset∪subset以外)が辞書順最小)は成立するのか?とりえあえずは成立すると信じた。
残り5分程度。テストもしたが解法に自身が持てない。しかし時間も無くしょうがないので提出。
が、落ちた。
subsetが最初から条件を満たしてない(3要素に共通するビットがある)ケースで落ちているようだった。その判定を入れたら通った。

Challenge

greedy解法とか知らないのでEasyのgreedyっぽい人のを写して、自分のものと答えが合うことを確認しただけ。他に1人だけ落とされてた。

SystemTest

遅延らしい。さて、通るか…
Medium落ちた。うーん…

結果

Easy: 227.48 / 250
Medium: Failed System Test / 500
Challenge: 0/0 = +0
Division Place: 368 / 792
Rating: 19571906

コメント

練習しよう。
落ちた理由がわからなかったのは久しぶりな気がする。
テストすればわかったよなあ。「焦っていても」コーナーケースをきちんと考えてテストをするべきだ。と、テストの重要性を再認識した。もちろん、書きながら気づけたらいいのだけれど…

コード

Easy
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
struct IncrementAndDoubling {
	int getMin(vector <int> desiredArray) {
		static int dp[1001][11];
		mset(dp, INF);
		dp[0][0] = 0;
		rer(i, 0, 1000) rer(j, 0, 10) {
			int x = dp[i][j];
			if(x == INF) continue;
			if(i*2 <= 1000 && j+1 <= 10) dp[i*2][j+1] = min(dp[i*2][j+1], x);
			if(i+1 <= 1000) dp[i+1][j] = min(dp[i+1][j], x + 1);
		}
		int n = desiredArray.size();
		int r = INF;
		rer(j, 0, 10) {
			int x = j;
			rep(i, n) x = min(INF, x + dp[desiredArray[i]][j]);
			r = min(r, x);
		}
		return r;
	}
};

2013/10/29

約40分気付かなかったミス

rep(j, a.size()) aa[a[j]] = 1;

とすべきところを

rep(j, a.size()) aa[j] = 1;

としていた。
解法がMaximumFlowであって、そっちがバグってるんじゃないかと思っていたが単純なミスだった。

解法・ライブラリ・変な所が間違ってるんじゃないかと思って確認して、それでもミスが見つけられなかったら、1回全体をきちんと見直すべきだ。

2013/10/25

SRM 595 DIV1 本番

朝のSRM。少し眠くて心配だったが緊張で眠気は吹き飛んだ。

Coding

900がMedより簡単なこと稀にあるよなーとか考え、Medより前に900を開こうと考えた。

Easy (250)

最初に、「2^(他の[L[j],R[j] ]に被覆されないiの数)?」と考えた。実際にはこれは合っていた。
しかしどうもそれが納得できなくて、罠ありそうだなーと考えてしまった。
次に「同じ色で塗らないといけないセルをまとめて、そのグループの数を数えればいい?」とおもった。
これはUnionFind(無駄に動的)でやった。
何も塗られない場所のグループは1、それ以外は2を答えに掛け算する。
結構テストして、心配ながらも提出。

Hard (900)

まず期待値といえば期待値の線形性だよな、と考えた。
それには凸包を分解する。三角形分解を考えて、それを足せばいいんじゃないか?と思った。
しかし肝心の「この三角形が凸包の三角形分解」になる確率がわからず、さらにそれは重複して数えてしまうことに気づいた。
そしてわからなくなった。Mediumが時間かかるもので解けないとだめだと思い、あきらめてMediumへ。

Medium (500)

とりあえず左右を別個に「left[i][j] = 区間[i,j)で右側の連続するG(途中でminGreen個以上出てるならminGreenで固定)」と「right[i][j] = 区間[i,j)で左側の連続するG(同上)」というように2つ計算すればいいと、割と素直に考えられた。
これの計算は普通に区間を拡張してく感じで計算してけばいい。
さて、左と右を組み合わせなければいけない。
左の区間を[i,j]とすると、この区間に対応できる右の区間は{ [k,l) | j <= k, right[k][l] >= minGreen - left[i][j] }となる。これを高速に数えるにはどうしたらいいだろうか?
この答えも素直に思いつけた。Fenwick木を動的に使えばいい。tをFenwick木とする。
jを右端から左へ移動させる。ループ中では全てのlに対してtのright[j][l]の位置をインクリメントする。
その後各i,jに対してtの[minGreen - left[i][j],∞)のsumを求めればよい。このsumが答えとなる。
テストを何回かした。その時システムが不調でテストに時間がかかって、それで30ptくらい減った。しかしテストは重要なので良い。落ちたら0点なのだから、数十点で一喜一憂してはいけない。

Challenge

4人落とされてたけど、読んでもなんで落ちたのかわからなかった。その程度のChallenge力。これは改善すべき。

SystemTest

通ってよかった。

結果

Easy: 204.51 / 250
Medium: 379.92 / 500
Hard: Opened / 900
Challenge: 0/0 = +0
Division Place: 23/455
Rating: 18201957

コメント

練習を続けよう。Challenge練習もしたいところ。
今回はMediumを速く解けたのでよかったけれど、Hardを先に開くのはやはり自分には少し早い気もする。やめよう。

コード

謎コード

Easy
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef long long ll;   
struct UnionFind {
	vector<int> data;
	UnionFind(int size_) : data(size_, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

struct LittleElephantAndIntervalsDiv1 {
	long long getNumber(int M, vector <int> L, vector <int> R) {
		int n = L.size();
		UnionFind uf(M+1);
		rer(p, 1, M) {
			bool white = true;
			rep(i, n) white &= !(L[i] <= p && p <= R[i]);
			if(white) uf.unionSet(0, p);
		}
		rer(p, 1, M) rer(q, 1, M) {
			bool b = true;
			rep(i, n) {
				bool x = L[i] <= p && p <= R[i], y = L[i] <= q && q <= R[i];
				if(x && y)
					b = true;
				if(x ^ y)
					b = false;
			}
			if(b) uf.unionSet(p, q);
		}
		ll r = 1;
		rer(p, 0, M) if(uf.root(p) == p) {
			if(uf.findSet(p, 0)) r *= 1;
			else r *= 2;
		}
		return r;
	}
};
Medium
#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(auto it = (o).begin(); it != (o).end(); ++ it)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll;

struct FenwickTree {
	typedef ll T;
	vector<T> v;
	FenwickTree(int n): v(n, 0) {}
	void add(int i, T x) {
		for(; i < v.size(); i |= i+1) v[i] += x;
	}
	T sum(int i) {	//[0, i)
		T r = 0;
		for(-- i; i >= 0; i = (i & (i+1)) - 1) r += v[i];
		return r;
	}
	T sum(int left, int right) {	//[left, right)
		return sum(right) - sum(left);
	}
};

struct LittleElephantAndRGB {
	long long getNumber(vector <string> list_, int minGreen) {
		string s;
		each(i, list_) s += *i;
		int n = s.size();
		static short dpleft[2501][2501], dpright[2501][2501];
		mset(dpleft, 0);
		rep(i, n) {
			dpleft[i][i] = 0;
			rer(j, i+1, n) {
				int x = dpleft[i][j-1];
				if(x == minGreen) dpleft[i][j] = minGreen;
				else if(s[j-1] == 'G') dpleft[i][j] = x + 1 >= minGreen ? minGreen : x + 1;
				else dpleft[i][j] = 0;
			}
		}
		mset(dpright, 0);
		rer(j, 1, n) {
			dpright[j][j] = 0;
			for(int i = j-1; i >= 0; i --) {
				int x = dpright[i+1][j];
				if(x == minGreen) dpright[i][j] = minGreen;
				else if(s[i] == 'G') dpright[i][j] = x + 1 >= minGreen ? minGreen : x + 1;
				else dpright[i][j] = 0;
			}
		}
		FenwickTree t(minGreen+1);
		ll r = 0;
		for(int j = n; j >= 1; j --) {
			rer(l, j+1, n) t.add(dpright[j][l], 1);
			rep(i, j) {
				int x = dpleft[i][j];
				r += t.sum(minGreen - x, minGreen+1);	//j <= l, dpright[l][k] >= minGreen - x
			}
		}
		return r;
	}
};

2013/10/18

SRM400〜594(今まで)のDIV1 Easy,Mediumを埋めた

見た問題の表 - antaの競技プログラミング練習日記
最近練習してなくて惨敗し続けていたのでむしゃくしゃしてやった。
さらにSRM400〜のHardをやろう。

Connection: close