CODE FESTIVAL 予選B D問題

この問題はかなり苦労しました。というのも、動的SegmentTreeで解こうとすると空間計算量が非常に厳しくなるからです。

ですが、よく考えると動的SegmentTreeの空間計算量がO(log|区間の幅|)というのは変な気がします。なので少し考えてみたら、平衡二分木を使うことでO(log|クエリ数|)(もちろんクエリ数 < 区間の幅とする)に落とせたのでメモします。

この問題の想定解はsetを使いますが、もちろんそれではなく、あくまで動的SegmentTreeとしてsetを使ったという話です。

基本的には葉にのみ値をもたせる木を考えます。 普通のSegmentTreeと違うのは、葉が長さ1より大きい区間を持つかもしれないということです。なので、if (n->sz == 1)では葉の判定ができず、ノードごとにそれが葉であるかというフラグを持たせる必要があります。

クエリ処理ですが、区間[l, r)にアクセスしたいときは、inscut(l)とinscut(r)をしておいてからクエリを投げるという方針で考えます。inscut(k)とは、木の葉が [..., k), [k, ....) となるように区切りを入れる関数です。

これは木を葉まで潜って行って、葉に当たったら[0, sz)を[0, k), [k, sz)に変更するだけです。これは平衡二分木のinsertで実現できます。

この関数さえ作れば、あとはよしなになんとかなります。というのも、この関数を使っておけば、区間の端が葉の途中に来るということがなくなるので、普通にSegTreeのように木を潜るだけでクエリが解決できるようになるからです。

Submission #561168 - CODE FESTIVAL 2015 予選B | AtCoder

作問リスト

  • JAG夏合宿2014

夕食。原案。

  • Kagamiz Irregural Contest 03 (KCS)

4題。爆散。

  • Yosupo Wetterberb (KCS)

スペルは適当。5題。爆散。

  • Yosupo Contest 2 (KCS)

3題。爆散

  • CF #286

2題。

Problem - A - Codeforces

Problem - C - Codeforces

  • TTPC

5題原案。そのうち4題準備。

某バはおおっぴらに言っていいのか不明(解説スライドに書いてあるけど。) 計8題。探して。

CODE RUNNER 予選B

せっかく1位だったので参加記書きます。

最初10分で大体読みます。

1分ごとに5%減ということでgoogleに0.95 ** xのxを変えていろいろ突っ込んでみる。

どうやら減衰はかなり激しいが、max scoreなのでさっさと強力なAIを書いたら有利だなぁと思う、がこういうので強いAIというのがわからない。

1秒ごとに攻撃するプログラムを書くが、カス。

0.25秒ごとにinfoを読んで、自分の攻撃力, 自分の総和, 敵の情報だけを表示するプログラムを書いて眺める

とりあえず, 眺めて適当な戦略を突っ込む

まずは

  • 自分の攻撃力 * 1.1 > 先頭の敵の体力なら攻撃

これだけだと先頭が弱くて次に強力なのが待っていた時にオワコンするので以下

  • 攻撃力 * 1.2 < 先頭から2番目の敵の体力ならとにかく待機

さらに、先頭が強くて次が弱い時は他人が攻撃して弱いのが回ってきてオワコンするので以下

  • 攻撃力 > 先頭から2番目 && (残り二人の攻撃力の和) * 1.05 > 先頭の敵の体力 なら攻撃

1.1とか1.2とか1.05とかの微妙なパラメーターは、他人のちょっと先を取るということを意識した。具体的な数値は 1 + eps から適当に選んだ

とりあえずこの3つだけで回すが、案外勝てる

ここら辺でいい感じにゲーム木探索することを考えるが、難しい

そもそも1時間でかけるものなんてたかが知れてるので、どんどん戦略を追加していく方針に

myrankを見ると、どうやら1位を取るためには少なくとも60Mぐらいのポイントが必要っぽい。なので

  • 攻撃力が10M以下だったら必ず待機

という戦略を入れる。これはかなり勝率に関与した気がする。

これだけでガンガン勝てるようになった

ここら辺で1桁順位にはなっていたのだが、kyuriに勝てそうにないため、考える。

とりあえずここら辺で戦略かぶりが見られるようになった、戦略かぶりは本当に最悪で、誰も攻撃しなくなって1分間犠牲になる。

1分間犠牲になると、たとえ1位が取れても点数が下がるのでクソ、そもそも8割は勝てていたためさっさと放棄して次の試合に行ったほうがいい。なので

  • 20秒パワーが溜まったらアホモードに移行

という戦略を入れた。アホモードとは

  • 攻撃力 * 1 > 先頭の敵なら攻撃

という戦略のみで動くモード。とにかく最速で勝負を終わらせることだけ考えている。

また、

  • もし残りの敵を全部他人に取られても勝てるならアホモードに移行

という戦略を入れた、絶対に勝てるなら変な事をする必要はない。

これらでぶん回したら40000点を超えた。やったぜ

この後も回し続けるが、そもそも他人が強くなってしまいどうしようもないためどんどん点数は下がる。

当然40000点をもう一度とるのは不可能だけど何もせず点数が下がっていくのも寂しいので細かい戦略を追加していく。

運もあったがcurrent1位で終了できたので良かった。

RBSTはコピー可能は嘘

まずこちらをご覧ください。

RBSTがコピー可能は嘘という疑惑 - よすぽの日記

これをちょっと変更すると以下のコードになります。 このコードを実行すると木の高さが5000近くに到達すると思います。

gist.github.com

これを利用して、AtCoderのグラフではないのアンチRBSTケースを作ることができます。

しかし、メモリが足りなくなった時の処理に、木を破壊して再構築する方法を取っている奴を落とす破壊力はありません。頑張れば落とせる奴も作れるのかなぁ(その他Mark & Sweep, JavaのGC等を使っている奴は大体落とせるんじゃないかと思います)

テストケースメーカーは以下のコードです。

gist.github.com

RBSTがコピー可能は嘘という疑惑

コピー可能なRBSTを持っている人は以下の疑似コードっぽい動作をやってみてください。多分結構な確率で高さが300を超えます。

gist.github.com

永続が必要な時は赤黒木とか使うと良さそうです

HL decomposition+SegTreeのlogを1個消す

はじめに

この記事はHL分解について書きます。

HL分解+SegTreeでパス上のクエリに答えると、最悪ケースで O(log2 N) per query ですが、これを O(logN) per query に改善したいと思います。

アイデア

HL分解の詳細についての解説は省きます。たくさんネットに資料は転がっているので探してください。

HL分解+SegTreeでパス上のクエリに答えるのは

  • 木をHL分解でパスに分解し
  • パスをSegTreeで管理する

という 2ステップからなります。パスに分解してまとめた後の木の高さが O(logN)、そのパスへのクエリが O(logN) で、合わせて計算量は O(log2 N) です。

実は 2つめのステップで、あえてアンバランス(完全二分木ではない)なSegTreeを使うことで、logを1つ落とすことができます。 1つめのステップは普通のHL分解と全く同一です。(ただし、最も子の中で部分木のサイズが大きいものをheavy-pathとして選ぶものとする。)(本家は部分木が小さいのばっかだったらheavy-pathを選ばない？)

まず、ノードごとに以下のように重みを定義します。

  • weight[p] = pの部分木のサイズ - pのheavy-pathに選んだ子の部分木のサイズ(もしpがheavy-pathの末端なら0)

そして、Segtreeは普通、左右のNodeの数が等しくなるように分割していきますが、これをweight[p]の和が左右でできる限り等しくなるように分割していくだけで計算量が改善されます。

具体的には、"2段降りるとweightの和が1/2以下になるように"構築することができます。(多分)

計算量解析

Mi_Sawaさんに行けそうじゃないこれ？と言ったらいい感じの説明が帰ってきました。↓です。

再帰的に考えます。サイズAの木について、その根から生えるheavy-pathを考えます。そのheavy-path上の頂点pについて、weight[p] = B と仮定したらpは上から何段目に存在するでしょうか。

これは2段降りるとweightの和が1/2以下になることを考えると、O(log(A/B)) + O(1) です。

そしてその後はサイズKの木について考えれば良いので、結局 O(log(A/B)) + O(log(B/C)) +O(log(C/D)) ... = O(logA) が成立し、左辺の足し算の項の数は O(logN)個なので、良さそうです。

実測

一応実装しました。 実験の題材はかの有名なDo use segment treeです。 AOJに投げるとなんか遅いです。普通のHL分解+SegTreeと速度が変わりません。考えさせられますね。びっくりしました。

遅いケース(test8)を手元で動かすと最速タイ(LinkCut, 0.23s)とほとんど速度が変わらないのでお手上げです。

というわけで、手元で計測する卑怯な方法に出ます。

計測法は3回測って平均です。クソ適当。

木の形は完全二分木 (N=217 -1 = 131071) クエリは Q=1,000,000 で完全ランダムのテストケースメーカを作り、実験しました。

普通のHL分解が 3.06sec で、今回のHL分解が 2.66sec、LC-Treeは4.10sです。 クエリ数が多いとやっぱり有利です。

また、HL分解の最悪ケースっぽいものを作って実験しました。 これはN=196606, Q=1,000,000 です。

普通のHL分解が 4.17sec で、今回のHL分解が 2.53sec、LC-Treeは3.27sです。

なお、比較対象の普通のHL分解ってのは定数倍が遅いです。配列に展開せずポインタですし。実装に疲れてしまった。

コード

テストケースジェネレーター

完全二分木

gist.github.com

悪質ケース

gist.github.com

HL分解

37行目と38行目をいじることで普通のHL分解と今回のHL分解が変えられます。

gist.github.com

天下一プログラマーコンテスト 2015 参加記

Klabさん主催の天下一プログラマーコンテストという大会に参加してきました。3位でした。

F問題

A, Bはペナルティが無いらしいし、問題を見る限り高々80点しか差がつかないので放置

とりあえず一番配点の低いFを考える

根へのパスに1を足すこととパスの値を求める事さえできれば二分探索でできるなとなる。

そこから頭のいい解法を考える事すらせずに殴って終わらせてしまった。反省。

E問題

とりあえずブロックを高い順に追加して考えると見通しが良くなりそう

期待値の線形性でガリガリやると、どうやらO(N)時間で解ける事が判明

式を書き写してAC。最近10億7に強くなってきた気がする(といっても天下一に出るような人の平均よりはまだダメだと思う。今回は運が良かった)。

C問題

うわぁなんだこれ

行列と置換が交互に置かれるような形になるので最初行列累乗の線で考えていたが、流石に無理。

どうしようもないので、とりあえず部分点を取ることを考える。

それはダイクストラでホイだった(本当は01-BFSするべきだったが、H=100なのでどうとでもなると思った、実際は危なかった？)

D問題

部分点が60点とは思えないがパッと書いてパッと提出。ジャッジに無限時間かかる。

この後Cを考えるがわからず、どうしようもないのでA,Bに移ることに

B問題

10点は流石に秒殺。 さすがに少しは真面目な戦略を考えたい 次数でsortしてdfsを考える。それなりに良さそうだったので書いて提出

A問題

とりあえずいい感じのグラフを考える。 特に思いつかないので、頂点を50個50個に分けて間にランダムに辺を追加、を繰り返すことを考える。 これは前述のB問題で次数に注目したため、使う頂点と使わない頂点での次数の分布を同じにすることを考えたから。 よく考えたら自明に二部グラフなため、危なかった。(まあこの短時間コンテストで二部グラフの処理の追加までできる人はそうそういないと思うため大丈夫)

多重辺の処理を忘れていてWAを連発する。相当焦る。死ぬほど焦る。

が、ギリギリ気付けて投げることができた。危ない。

さすがにAB合わせてラスト20分は危険すぎた。もう少し早めに片付けておいたほうが良かった。

ブレイクタイム

ABの結果で順位が3位から7位まで変動するため気が気ではない しかもABで特に力を入れたわけではない(つもりだった)ので…

何とは言わないがB問題の結果があれしてかなりあれなことがわかったのでこれはもしかして…？みたいになる

結果発表

BどころかAもかなり上位で、無事3位になることができた。とても嬉しい。 実際20分でこれはかなり勘が冴えていたのではないかと思う。

感想

Klab問題の無慈悲難易度本当勘弁してくり〜

Gを読みもしなかったのは勿体無かったですね(といってもこのタフセットで誰も解いていない問題を読みにいくのは戦略上どう考えてもミスだと思うので、これで正しいとは思う。)

Eはシンプルで面白かった。

Cはなー、さすがに頭がこんがらがって無理。EFの前の元気なうちに取り掛かっていればあるいは…？(これも結果論で、F->E->Cの順で解いたのは正しいから言うだけ無駄。)

問題はG以外(まだ読んでいないので判定できない…ゴメンナサイ😞)すべて(A, Bも含めて！)面白かったです。