Hardを頑張ってちょいちょい解いていきたい。メモ。
k
o
r
e
h
a
k
u
u
h
a
k
u
[0, A)のフィボナッチ表現のi桁目の立っているbitの個数の偶奇がわかれば良い(いつもの)
桁を固定して考えると、直感的にフラクタル的な感じになりそう…と決めうちして考えると、フィボナッチ文字列みたいになっていることがわかる
あとは適当に計算すればOK。計算量はO(log2)かlog3か
SRM 658 Med
概要
3*Nの行列が与えられる。
K回、以下の動作ができる。
- 異なるi, j, kを選ぶ。(1, i)と(2, j)と(3, k)の値を1ずつ減らす。
どういう行列なら、すべての値を0以下にできるか？
というのが本質部分です。
これについて考えていたら、面白い結論が出たのでメモします。
解法
実は、すべての列とすべての行について値の総和がK以下であることが必要十分です。
一般化
N*Nの値が非負整数の行列が与えられる。
K回、以下の動作ができる
- 順列a1, a2, ..., aNを選ぶ。(ai, i)の値を1減らす。
どのような行列ならばすべての値を0にできるか？
思考
実はこの問題も同様に、すべての列と行について値の和はKであることが必要十分になるはずです。
数学的帰納法で考えると、以下のような問題になります。
N*Nの行列が与えられ、すべての列と行について和の値はKである。
以下の条件を選ぶようにマス目をN個選べるか？
- どの列も1個選ばれてる
- どの行も1個選ばれてる
- どのマスの値も1以上である
こういう選び方をすれば、K -> K-1という遷移ができるのでOKです。
ここで、ネットワークフローを考えます。
左に頂点がN個、右に頂点がN個あります。s -> 左の頂点の容量と、右の頂点 -> tの容量は全て1、さらに、左の頂点から出て行く辺の容量と右の辺に流れ込む辺の容量の和は全てK。このようなグラフで必ず最大マッチングはNとなることがわかればOKです。
ですが、これはホールの結婚定理を使うときれいに示せます。左側の頂点を幾つか選んだ時に、対応する右側の頂点の集合の数は、辺の容量の和の制約から必ず左側の選んだ数より大きくなるからです。
元の問題
これが言えると元の問題が解けるのか？というと非自明です。(これだけでもD1easyくらいはありそう)
以下白字(にしたかったんですが、画像はどうしようもない)
3*Nの行列について、(列と行の値の和がK以下 => K回の取り除く動作で全て0以下になる)
が言えれば良い(逆は自明)。
3*Nの行列を、(3+N) * (3+N)の行列へ拡張することを考える。
まず、3N -> 3(N+3)への拡張だが、これは下図のようにする。
いい感じにa, b, cを設定することで、行ごとの和が全てKになるようにできる。
このあと、下にN*(3+N)をくっつけるが、これもいい感じに加えると、全ての列の和がKになるようにできる。
これは一般化した問題なので、K回の取り除く動作で全部の値が0に出来る。その操作を3*Nの行列について取り出せば、いい感じ。
DDPC 参加記
前日
特に理由は無いけど酒を持って__math家にお邪魔する。飲酒は最高。飲酒したら気づいたら寝ていた。
朝
なんかよく眠れなかったし微妙に頭が痛いしコンディションが悪い。迎え酒で万事解決。
コンテスト
冷えました。
A問題: 記憶に無い B問題: 嘘解法を2回ぐらいやって酷かった C問題: 俗に言う反射というタイプの問題。エンバグしまくった。 D問題: なんかSCCに気づいたらあとは場合分けしまくったら解けた。Submitデバッグしないと通りそうになかったためサブマリンやめた(そして実際Submitデバッグになった)。 E問題: 30点を取ればいい感じの順位になると焦ってしまった。残念。
C問題のデバッグに使った時間が戦犯だった。酒はやめましょう。
チョコレートフォンデュ
やっぱり印象的だった。
社内見学
予想より面白かった。
収穫
きゅうりシール。
AOJ-ICPC 1000点 非幾何まとめ(ネタバレ含む)
Cellular Automaton以外を解きました。Cellular Automatonはあまりに意味不明なので解説を見ました。
Do use segment tree
問題, 解法ともにめっちゃ有名ですね。ライブラリチェック用問題。 HL分解かL/C Treeを貼ります。おすすめは後者
Common Palindromes
方針が悪く非常に大量のライブラリを使った。大変。 回文列挙はmanacher + rolling hashで可能。 後は文字列についてそれがいくつ出てくるかを判別できれば良い、これはSuffix Array + LCP + RMQ
Palindrome Generator
解法はすぐに思いついたんだけど、微妙に方針が良くなかったようでMLEで苦しんだ。きらい。 (スタート位置, ゴール位置)のペアを頂点とするグラフを考えれば良い。 強連結成分->DAGでDPしようと思ったら死んだ。クソみたいな改善で通した。
姉妹港
なんか適当にごにょごにょしたら解けた。 解法説明困難。
Brilliant Starts
簡単だった。
次数が少ない頂点から順にDPすればよい。
ねこ鍋改造計画
見るからに戻すDPっぽいのだがそのままでは不可。
dpの値を、YES/NOからそれを達成する組み合わせ数 mod 適当な数 にすればよい。この考え方は数列色ぬりで学んだ。圧倒的成長。
一般化ポーカー
面白かった。
説明困難だけど、値が2以上離れてる手札は詰めて良い。[1,2,3, 59, 60]と[1,2,3,5,6]みたいな。 こういうのを統合すると状態数がめっちゃ少なくなる。
よくわかる二重魔法
問題文読解が本質。以上。
Crystal Jails
クソ
Point Distance
FFTって面白いですね。
Air Pollution
面白い。
めちゃいじいじしてたら解けたけど、どうやら累積和で考えれば一瞬だったらしい
CarrotBreeding
大体のパターンはすぐできる。
細かいのはモンテカルロした。
Lapin Noir
面白い。
嘘解法で通してしまった…
Exhibition
dp[n][a][b][c]とdp[n-1][a][b][c]が列挙できれば後は簡単。
3次元凸包になるのだが不可能なので、dp[n][a] := 2次元凸包 みたいにした。これでも十分状態数は少ないっぽい。まあ最悪ケースとか設定上作れそうにないし。
CODE FESTIVAL 2015 沖縄
楽しかったです。今年は少し写真も撮りました。人の写真は顔の写ってないのを選びました。問題があったら教えてください。
1日目
めっちゃ早く空港に着く。そういえばラブライブ！で出てくる空港ってどっちなんやろと検索したら13話と5thは羽田で映画は成田らしい。13話で出てきた場所を巡ったりする。屋上は飛行機がたくさん見れてキレイでした。それでも時間が余ったのでカッフェでソフィーのアトリエする。
人々が集結。PSVitaの電池がなくなりそうなのでケーブルをMi_Sawaに借りて飛行機に乗る。結局あんまり使わずに寝る。カボスを知らなかったらmitakiさんにマジかされる。残念。
沖縄についた。バスに乗りスィーって行ったら即ホテル。近い。あとリーダーに就任する。ちなみにこの旅行中でリーダーというものは何の役割も果たしませんでした。完全に一発ネタ。
事前調査によりホテルにはツインルームしかないと知っていたので、また一人でツイン使うのかと思ってたらさすがに相部屋だった。sugimさんとだった。知ってる人でよかった〜
なんかsugimさんとnatriumさんで、natriumさんの好きな交差点を見に行く(意味不明)らしいのでついていく。とつぶやいたら8人くらいからリプライが飛んできたので放棄。ごめん
こんなことをしてたら夜ご飯を食べる時間なので向かう。鉄板焼きらしい
たくさん飲んで良い気分になる。
異常なペースで食べ物が襲いかかってきて大変だった。でも美味しかったです。
ホテルに帰る。hogloidに部屋番号を聞かれたが、僕は天才なので一瞬で睡眠時間の危機を感じだんまり。しかしsugimさんが部屋番号を晒したため終了。
一瞬で部屋の人口密度が終了。盛り上がってきた。ていうかクソ暑い。どう考えてもツインに10人以上集結するのは想定されてなさそう。
japljの勧めにより沖縄限定特殊飲料を買いにいく。
まるで明日コンテストがあることを見据えたかのようなキャンペーンを行っていた。
特殊飲料は見つからず残念。
帰って(多分snukeの？)ボードゲームをやる。ていうかなんでsnukeいるんや。
突然japljが特殊飲料を持ってくる。冷蔵庫が終了する。
さすがに明日コンテストということもあり人々が帰るので風呂に入って寝る。
2日目
朝ごはんを食べに行く。美味しかったです。
sugim「帰ったらもう一眠りします」
hogloid&sigma「おうお前の部屋行くぜ」
sugim「全然イケます」
なんなんや一体。
気づいたらコンテスト時間ってワケなので飲み物を買ったのち会場に向かう。
非常に美味しいお弁当があったのだが朝ごはんが遅かったためほとんど食べられない。悔やまれる出来事。
確かここらへんで爆弾が投下されていたらしい
爆弾↓
コンテストが始まる。どうやらsnukeは前回優勝者枠だったらしい。Eで激はまりしてもう終わったなと思ったらいつの間にか1位になっていた。不思議。と思ったら異常な速度で8完され2位で終了。また入賞してしまった(ただし優勝はできない)。ところで国内1位と2位は僕とsugimさんなんで全く睡眠時間の影響なかったですね(ガハハ)。
夜ご飯を食べる。酒を飲む。非常にいい気持ちになる。ご飯は美味しかった。
昨日部屋での騒ぎが迷惑を与えていたという噂が出てきたため、hogloid&sigma部屋に移住。
今日もボードゲームを行ったりする。案の定部屋はクソ暑い。
適度な時間で寝ようとしたけどsugimさんと話し込んで終了。まあ明日は観光しかないため大丈夫。
3日目
朝ごはんを食べる。昨日と違う場所で騙される。なんか目玉焼きに激ハマりしてめっちゃ目玉焼きばっか食べてた。調味料は塩胡椒です。
観光ということで観光をする。
まずは謎の陶器？を作る場所。
陶器製作は自由度があまりにも低いため、めちゃくちゃにするなら軽く息を吹き込むとこで圧倒的肺活量を見せるしかないみたいな話をする。いいこなので実際にはやらない。
順番待ちの間、うずくまって体調が悪いのかと思って心配をしたら英語をやっていた人。
あとせっかくなので冬にアイスを食べるという贅沢を行う。
沖縄そばを食べ、首里城に向かう。スイーツの心を失っていたため沖縄そばの写真はないです。
首里城の鳩。
なんかここら辺から写真がない。なんで観光フェーズでだけ写真を撮らなかったのか謎が深まる。普通逆では。
首里城情報。
あっ、きゅうりいるじゃ〜ん pic.twitter.com/hjsEDwgTIA
— Drafear (@Drafear) 2015, 12月 21このあとは沖縄国際通り(だっけ)にいく。
お土産を買う。今年はたくさん買いました。
あとウーロンミルクティーというものを飲む。美味しい。
空港に向かう。短い3日間。
飛行機でウェーイって東京に行く、ソフィーのアトリエをやるつもりがあんまりやらずに寝ていた。
羽田に帰ってくる。
延長戦
sigmaと__mathの家に押しかける。害悪。
Distance Sum
考察パート
求めたいのは木の重心みたいなやつ。
今見てる点に、markされた木の半分以上を持つ部分木があったらその方向に動く、みたいなのを繰り返すと行き着く場所。
頂点を1,2,...,nと塗っていって、その度にこの重心を求め、その点までの距離の総和を求めるという問題。
で、i+1番目まで塗られた時の重心はi番目まで塗られた時の重心と、頂点i+1のパスのうちどっかにあるってことがわかる。これが最重要。
これがわかるとHL分解やらLC-Treeで解ける。今回はLC-Treeを使った。
変数はいつもの(親と子のポインタとreverse_flagとsize)抜いて7個。めっちゃ大変。
Do use + 考察 + 更に実装 という感じでDo useよりは難しいと感じた。
ちょっと重いSegTree
http://www.adventar.org/calendars/850の3日目の記事です。
微妙に役に立ちそうで役に立たないSegTreeテクニック
SegTreeで1点を更新するクエリを処理することを考えます。
これはおおむね
- SegTreeの対応する位置の葉を更新する
- そこから登っていき, ノードを更新する(そのノードの左右の子の情報をmergeしたものを自分の情報にする)
という2Stepからなります。
たとえばRMQならば上のStepはvalue = x, 下のStepはvalue = min(left->value, right->value)となります。
大体のSegTreeにおいて下のStepの計算量はO(1)ですが、必ずしも定数時間で行う必要はありません。
計算量がO(logN)だとしても、全体での計算量はO(log2 N)に収まります。
つまり下のStepにおいて、その頂点の子になんらかのクエリを飛ばすこともできます。
SegTreeには、
- 変更クエリ
- 取得クエリ
を持たせることが多いと思いますが、変更クエリで値を更新していくときにも取得クエリを使うイメージです。
階段状の点を持つ
これは僕が昔出した問題です。(http://yosupo.hatenablog.com/entry/2015/03/09/000435)
- 点を追加する
- 点を削除する
- 点を左上から右下への階段状にしたとき、幾つの点が含まれるか調べる
という3種類のクエリに答える問題です。
階段状の点とは、その点の右上に点がないものを列挙したものです。想像すると階段っぽさがありますね。
点をx座標でsortしてSegTreeで管理するのですが、上記のテクを使うとO(log2 N) / queryで処理できます。
詳しくはURL先を読んでください。
Convex Hull Trick(削除付き)
- kが与えられるので、直線の中で, x=kにおいてもっともy座標が小さいものを求める
- 直線を追加する
- 直線を削除する
というクエリを処理するのを考えます。オフラインクエリです。
このクエリが上記のテクを使えばO(logN)/query(取得, 追加), O(log3 N)/query(削除)で処理できることに気づいたのでこの記事を書きました。
まず、オフラインクエリなので直線を全部列挙しておいて、傾きでsortします。直線をy=ax+bとしたら、左側であるほどaが大きくなるようにします。
その後、その直線列をSegTreeで処理することを考えます。
本質は削除クエリなのですが、とりあえずは取得クエリから考えます。
直線を傾きでsortしておくことにより、非常に良い性質が生まれます。
凸包を想像してもらえれば分かりやすいと思いますが、左右のノードについて、左側のノードに含まれる直線から作られる凸包と右側のノードから作られる凸包、交点が1つしか存在しません。
なのでノードに持たせる情報は単純明快、この交点のx座標です。
すべてのノードがその交点のx座標を持っていた場合、取得クエリはとても簡単になります。
そのx座標が求めたい座標より大きいなら左、小さいなら右のノードに再帰的に潜っていけばいいだけです。
最終的に到達した葉が持つ直線が求める直線です。
では、次に追加/削除クエリを考えます。
もちろん重要なのはノードのmergeです。これをO(log2 N)で処理します。これができれば追加、削除クエリがO(log3 N)で処理できます。
要するに交点の座標を求めれば良いのですが、これは簡単で、x座標で二分探索をします。二分探索をしてその座標では左右のノードのどちらの方が大きいかを求めれば良いですが、これは左右のノードに対して取得クエリを飛ばせば良いです。
これでクエリの計算量はO(log2 Nlog(座標/eps))になりました。あとはちょっと頑張るとO(log3 N)になります。 追加クエリは頑張るとO(logN)になります。ならないかも。
本当はもう一個logが落ちてくれたら出題したかったのですが、O(log3 N)では微妙なため供養します。
頑張ったらもう一個ぐらい落ちてくれるかもしれません。ぜひ考えてみてください。
ちなみに平方分割だとO(sqrtN)で解けます。
他の例
もう一個ぐらい考えたかったけど特になかったです。
明日はantaさんの記事です。楽しみですね
