Atcoder Regular Contest 079 E - Decrease (Judge ver.)

問題

arc079.contest.atcoder.jp

解法

二分探索をする。操作を全要素に+1、特定の要素に-(n+1)として見ると、k回の操作で全要素をn-1以下にできるかどうかはaの各要素の値xに関して$ \lceil \frac{x-(n-1-k)}{n+1} \rceil $の和をとってkと比較するとわかる。

普通に二分探索をしようとすると単調性が成り立つは微妙に嘘とわかるのでちょっと工夫をする。

check(x) := x回の操作で全要素がn以下になるか とする。

あるk回の操作ですべての要素をn-1以下にできると仮定すると全要素に操作をするかんじにすれば(たぶん)k+n回の操作でもすべての要素をn-1以下にできる。加えて最大のやつから減らす操作は最大のやつを減らさないとどうしようもないのでたぶん最適で、よって check(k) -> check(k+n) が成立する。

よって区間を2nの大きさの区間に分割して、分割後の2nの大きさの区間のなかで全要素をn-1以下にできるようなものがあればその区間はtrueといったかんじのことをやる。そして二分探索で初めてtrueとなるような区間を求める。そしてその区間内を線形探索する。

計算量はたぶん $ O(n^{2} log{\sum a[i]}) $

ソースコード

今回の想定解みたいな計算量の評価が難しい解法を思いつくのが難しい。

AOJ 1604 デッドロック検出

問題

Deadlock Detection | Aizu Online Judge

解法

dp[今、各スレッドでロックしている資源をあわせたものの集合] = (次にどれかのスレッドが確保する可能性のある資源の集合の集合) みたいにする。

そして最終的に $ \exists S, \exists e \in dp[S], e \subset S $が成り立つとそこで行き止まりになるのでデッドロックとなる。

マージを高速に行いたいので集合を表すデータ構造としてはbitsetを使う。

計算量は $ 3^{10} \times 10 \times 2^{10}/64 + (2^{10})^{2} \times 10 $ くらい

コード

感想

最初紙に書かずに考察していたらひたすらごちゃごちゃしてごちゃごちゃしてごちゃごちゃした。

紙に書くの、大事

ICPC 2017 国内予選 参加記

チームnasubidenamidaでふるやん(@furuya1223)さんといないち(@37dbye)さんと出た。10位を取れた。

ふるやんさんの参加記はこちら。

www.creativ.xyz

コンテスト前

ゼミを早退してコンテスト会場に来て準備をする。模擬予選から特になにもしておらずほげ。

コンテスト中

模擬予選と同様にAを僕が担当する。まあやるだけ。

次にふるやんさんがCを書き始めDを考える。題意をつかむのに若干苦労したけど積制約でminに着目するのは典型なので割りとあっさり解ける。そしてE、Fを読み始めたあたりでCの実装が終わり、いないちさんがBを書き始める。ふるやんさんにDの解法をチェックしてもらい、よさそうとの意見をもらう。

次にEとFにふるやんさんととりかかる。とりあえずFはアドホックな考察ゲーっぽかったのでふるやんさんに投げ、僕はEを考える。最初はどこから手を付けていいかわけわからんとか思っていたけど16文字以下の制約を見て全探索を考え始める。計算量としてもA(N) = A(N-1)+2A(N-3)みたいな漸化式になって間に合いそうみたいな気分になる。実装が大変そうだったので実装方針を詰める。横でふるやんさんがめっちゃ紙にゴリゴリ考察してて強そう。

いないちさんのBがバグったとのことでとりあえずソースを印刷して僕がDの実装に取り掛かり始める。その最中でいないちさんがバグを取れたらしく、いないちさんにバトンタッチ。サンプルが通ったらしくsubmitしACを取る。その後Dの実装に戻り若干バグらせるもAC。この時点で29位。2チーム通過を狙うならもう一問解きたい。

Fはまだ考察中らしくPCがあいていたのでEの実装にとりかかる。バグらせる気しかしなかったのでかなり集中してとりかかる。かなり大変そうとか思っていたけど取り掛かってみると意外とそこまででもなくてなんとかAC。この時点で11位になって完全にゲームクリアみたいな気分になる。するとふるやんさんがFを解けた(!)と主張し実装を始める。Gを適当に考察して適当なことを言っているうちにふるやんさんがFの実装を終え提出。ACをとり9位(!)になる。ふるやんパワーすごい。

そしてふるやんさんがGに関して右手法っぽくやればいけそうと主張し間に合わないと思いつつ実装を開始。 終了5分前になって先輩チームがざわつき始め順位表を見てみると一気に2完(!)しておりびっくりする。そしてGの実装は当然間に合わずコンテスト終了。

最終順位は10位でギリギリ一桁を逃す。

コンテスト終了後

先輩チームにハイタッチをねだりに行く。

阪大からはおそらく全チームつくば進出でめでたい。

そしてふるやんさんにFの解法を尋ねたりする。よくわからなかった。IQを感じた。

感想

今回脳をまったくつかってないのでつくばまでにはちゃんと脳を使えるようになるたいと感じた。アドホックな考察力ってどうやったらつくんですかね。

RustでUnion-Find実装してみた

atc001.contest.atcoder.jp

をRustで解いた。

コード

速度

Rustでの実装(Submission #1334290 - AtCoder Typical Contest 001 | AtCoder)とC++での実装(http://atc001.contest.atcoder.jp/submissions/1334930)を比較するとRustのほうが10倍近く遅くなっているけど書き方が悪いのかな?

どうしたら速くなるんだろう。

AOJ 2170 Marked Ancestor

問題

Marked Ancestor | Aizu Online Judge

木に対してノードをマークするというクエリと、あるノードに対してマークされた最も近い祖先を答えるというクエリに答えよ。

解法

ノードをマークするというクエリは子全体に対するmax更新クエリとみなせ、最も近い祖先を答えるクエリは子に記録されたmaxを答えるクエリとみなせる。

よってEuler Tour Technique + 遅延評価セグメント木 で殴る👊👊👊

$ O(n log{n}) $

コード

SRM610 Div2 Hard MiningGoldEasy

問題

TopCoder Statistics - Problem Statement

解法

xとyを独立に考える。

任意の動き方に対してx,yのそれぞれに対して座標の変化が起こらないような区間を考える。 すると関数  f(x) = \sum_{i=0}^{n} {|x-a[i]|} f(a[i]) のうちのどれかを最小値としてとるような凸関数であるので、 event_i、event_jに含まれるような座標の組み合わせに対する動き方のみ考えればよい。

よって座標圧縮してDPすればよい。

コード

証明が本質?

Codeforces Round 381 Div2 D Alyona and a tree

ダブリングでそれぞれの頂点がどこまで支配されるのかを求めた後、各頂点に+1, -1を記録し木上でimos法みたいなことをします。 O(Nlog(n))

gist2622f3016f0d316048b64712fa3894dc

500msくらいかかっていて結構遅い