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(log² N)に収まります。

つまり下のStepにおいて、その頂点の子になんらかのクエリを飛ばすこともできます。

SegTreeには、

• 変更クエリ
• 取得クエリ

を持たせることが多いと思いますが、変更クエリで値を更新していくときにも取得クエリを使うイメージです。

階段状の点を持つ

これは僕が昔出した問題です。(http://yosupo.hatenablog.com/entry/2015/03/09/000435)

• 点を追加する
• 点を削除する
• 点を左上から右下への階段状にしたとき、幾つの点が含まれるか調べる

という3種類のクエリに答える問題です。

階段状の点とは、その点の右上に点がないものを列挙したものです。想像すると階段っぽさがありますね。

点をx座標でsortしてSegTreeで管理するのですが、上記のテクを使うとO(log² N) / queryで処理できます。

詳しくはURL先を読んでください。

Convex Hull Trick(削除付き)

• kが与えられるので、直線の中で, x=kにおいてもっともy座標が小さいものを求める
• 直線を追加する
• 直線を削除する

というクエリを処理するのを考えます。オフラインクエリです。

このクエリが上記のテクを使えばO(logN)/query(取得, 追加), O(log³ N)/query(削除)で処理できることに気づいたのでこの記事を書きました。

まず、オフラインクエリなので直線を全部列挙しておいて、傾きでsortします。直線をy=ax+bとしたら、左側であるほどaが大きくなるようにします。

その後、その直線列をSegTreeで処理することを考えます。

本質は削除クエリなのですが、とりあえずは取得クエリから考えます。

直線を傾きでsortしておくことにより、非常に良い性質が生まれます。

凸包を想像してもらえれば分かりやすいと思いますが、左右のノードについて、左側のノードに含まれる直線から作られる凸包と右側のノードから作られる凸包、交点が1つしか存在しません。

なのでノードに持たせる情報は単純明快、この交点のx座標です。

すべてのノードがその交点のx座標を持っていた場合、取得クエリはとても簡単になります。

そのx座標が求めたい座標より大きいなら左、小さいなら右のノードに再帰的に潜っていけばいいだけです。

最終的に到達した葉が持つ直線が求める直線です。

では、次に追加/削除クエリを考えます。

もちろん重要なのはノードのmergeです。これをO(log² N)で処理します。これができれば追加、削除クエリがO(log³ N)で処理できます。

要するに交点の座標を求めれば良いのですが、これは簡単で、x座標で二分探索をします。二分探索をしてその座標では左右のノードのどちらの方が大きいかを求めれば良いですが、これは左右のノードに対して取得クエリを飛ばせば良いです。

これでクエリの計算量はO(log² Nlog(座標/eps))になりました。あとはちょっと頑張るとO(log³ N)になります。 追加クエリは頑張るとO(logN)になります。ならないかも。

本当はもう一個logが落ちてくれたら出題したかったのですが、O(log³ N)では微妙なため供養します。

頑張ったらもう一個ぐらい落ちてくれるかもしれません。ぜひ考えてみてください。

ちなみに平方分割だとO(sqrtN)で解けます。

他の例

もう一個ぐらい考えたかったけど特になかったです。

明日はantaさんの記事です。楽しみですね

CODE FESTIVAL(コンテスト)

本戦

A, B, C, D, E

パパパッと解く もちろん後半に比べると簡単ではあるんだけども、C,D,Eは自明ではなかった

D問題imosで解けなかったのダメかもしれない(StarrySkyTree並感)

E問題は面白かった

F

1時間ぐらい使う。無理。

G

O(N⁴)はすぐに思いつく。ウンウン考えてたら天啓が降ってきてO(N³)になる。やったぜ

H

読んだ感じ区間を適当にsortしたのちにSegTreeで処理するタイプの問題っぽいなと思う

区間を適当にsortしたのちSegTreeで処理したら解けた

I

木+データ構造やんけ、これは勝ったな(確信)

ウンウン考えてたらUTPC2013の支配と友好っぽいことをすればいいと気づく

あんまりデータ構造要素はなかったけど面白い

F

再び戻る

ぐるっと回るのはたかだか2周でいいというところまではわかっていて、ウンウン考える

式をウンウンいじったらいつの間にか辺を使う回数の式が出ていた。常勝

J

• 読む
• 無理
• 終了

エキシビジョン

• Bでライブラリ貼るだけと信じてやまなかったのでBから読む
• 線をつなぐ？これはLink-Cut Tree待ったなしですね

• 無　慈　悲　な　1　0　億　7

• Aを読む

• オッフローじゃ〜ん
• 部分点はさすがに自明だったのでとりあえず0点回避に向けて動くことにする
• 自明だけども実装が重い、けど20点を取る
• 満点は流し戻し的なことをするのかなぁと思う

• ちなみに会場からSCCという単語が聞こえてきていた。耳栓をしていてもマイクを使って発言されるとどうしようもない

• Bを考える

• お絵描きして色々調べる
• 結構形の制約は厳しいことがわかる

• いややっぱり無理じゃない？

• Aを考える

• 残余グラフでの連結性だけ調べればよくて、結局フローを流すのは最初だけで良いことがわかる

• 場合分けして、なんかSCCとか使ったら解けた。

• Bを考える

• サイクルがあるなら必ず長さ4のサイクルがあることに気づく
• でも全然解けなかった。終了。

CODE FESTIVAL 2日目

(あさ)

• Mi_sawaとコンビニへ行く。買ったオレンジジュースを2秒で飲み干してた
• 非常に眠い

(あさプロ)

• 適当にやる
• 頭が寝ているのが自分でもわかるぐらいに寝ていた
• 45分ぐらいたったらエンジンがかかってきた
• エンジンがかかってもCは厳しい
• 結局8位だった

(コンテンツ)

• お弁当を食べた
• iwiwiさんと話した
• ちょくだいさんの話を見たりタイピングをしたりした
• りんごさんのクイズを見た
• ランカーのプレイングを見た

(チーム対抗リレー)

• とりあえず本戦の順位でsortしてその順に解くというアレ
• 最後の問題を読む
• これは実験系ですね…間違いない
• 考えていたがわからん(表の作成を間違えていた)
• 間違いを修正できたけども、1 2 1 4 1 2 ...からフラクタルしか想像できず死亡
• 開始75分間かけてようやく規則を見つける。今思うとPCの空き時間があったからそこで表を列挙するべきだった

(ハッピーアワー)

• 三上和馬

• ジェイポウジュさんとtozangezanとダベってから帰った

CODE FESTIVAL 2015 参加記(1日目、コンテスト除く)

1日目

• 適当に起きる
• 赤坂から行ったら微妙に迷う
• 飲み物をたくさん買った
• 早めに行っても暇しないだろと思ってたけど結構暇だった
• ついでに競プロ勢スタッフ各位もめちゃ暇そうにウロウロしてた、気のせいかも。
• いろんな人と話す、プロコンオンサイトは夏合宿以来かな？
• 置いてあったご飯を食べたりおにぎりを交換したりする
• kyuriが交通費の紙を書いてた
• なんかWifiの調子が微妙に悪いため時間になってもコンテストが開始しない。大変そう
• 微妙な緊張状態でずっと待機することになったのでつらかった

(コンテスト)

• 900点で2位でした。hogloidとの差が4分とかで悔しい
• Fで詰まってしまったのがつらかった、けどまあ仕方がない
• http://code-festival-2015-final.contest.atcoder.jp/submissions/565266
• 風船ツリーは面白いと思った、最後の問題も解説を聞いたら面白かった

(コンテンツ)

• ご飯を食べる。美味しかった
• 肉巻きおにぎりは手が油まみれになった
• もうちょっと量があると嬉しい、と僕が思ったくらいだしぽよ各位は辛そう
• DDRしたらなぜか右腕がおかしいことになった
• akenshoさんのを見たりした、熱がこもっていた
• ご飯とかエキシビジョンの準備とかがあってあんまり初日のコンテンツはまともに見れなかったなぁ、早く動画化してほしい。

(エキシビジョン)

• 振り返ると僕にとっては今回のメインコンテンツになったかも
• 疲れていたので問題を解く担当は他の人で僕はエンジョイするぞと思ってたんだけど、結局めっちゃ熱中してしまった。
• 熱中してたら1位(番兵除く)を取れました
• 事前に色々な素材を用意しておいたんだけど結局小顔kyuriしか使わなかった
• PCの画面の半分が占有されるの本当に邪魔だったしkyuriは反省してほしい
• 200/7≒30, つまり約30人ぐらいには画面を見られていた計算になるし緊張しました
• 感想気になってるんで約30人の人はぜひ僕に感想を教えてください。
• 後でいろんな人に聞いたらテキストエディタで今の心情を書き連ねていくのは好評価だった、でもあれも実は結構邪魔だったりする
• エキシビジョンの賞品はぶっちゃけいらないものばかりだった
• 欲しいものを賞品にされると本当に真剣に出ないといけなくなるため良かったのかも

(ホテル)

• マクドナルドに行って__mathにスイーツをおごってもらう、やったぜ
• 今度からはおごるのは賞金をもらった中で最下位にしようなみたいなことを言われる
• 部屋でダベる、__mathはショートコーディングやってた
• ペコが消えないので後でカップ麺を買ってきて食べた
• シャワーの水圧が低かった
• zerokugiにメンヘラ発言とセクハラ発言をされる
• 寝た