今までに作った問題たち
そろそろ作った問題たちが増えてきそうなので、それらをまとめて感想を書いておきます。
まとめるのも面倒になるほどたくさん問題を作るぞ:punch:
- Codeforces #162 Div1C/Div2E Choosing Balls
- 初めて放出した問題。最初はa,b>=0だったり、クエリーじゃなくてO(NlogN)も許さざるを得ない感じだったけどsnukeやりんごさんの助けでCに置けるぐらいの問題になった。そもそもこの頃は問題のテストケースとかも作らなければいけないとは知らなかったなあ。初めてpolygon(CFの作問プラットフォーム)を使った。
- Codeforces #263 Div1A/Div2C Appleman and Toastman
- この問題は特に思い入れなし。ハフマン記号と考えてもいいし、貪欲が思い浮かんだら確信できると思うなあ。
- Codeforces #263 Div1B/Div2D Appleman and Tree
- 原案は僕で準備はsnuke。B問題が却下されたけど、日程は決まってしまったっぽいので大急ぎで作ったのがコレ。割と典型っぽいし特に思い入れは無し。
- Codeforces #263 Div1E Appleman and a Game
- snukeと一緒に原案を作った。僕だけだったらここまで難しくはできなかったなあ。ちなみにこのCFは夏ごろに3人でsnuke宅に集まって色々しながら原案を作ってた。楽しかったしこういう形式の作問もいいと思う:) この問題は難しい知識もいらないけどちゃんと難しい問題になってて好きです。（まだあんまり作ってないから何ともだけど）
- B: 道路工事 - AtCoder Regular Contest 032 | AtCoder
- 初めてのARCへの放出。ふつうの簡単な問題です。画像の作り方を教わりました
- C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder
- これも割とふつうの問題。問題文はもっと注意して書こうと思いました。
- Codeforces #286 Div1D Mr. Kitayuta's Colorful Graph
- evima&yosupoとの合作回。想定解だと、ただ次数の小さい方に注目するだけでオーダーに√Qが出てくるのが面白いなあ、と思ったけど、ふつうの平方分割解もあるし、やっぱり√系の解法のものはFull Feedbackの場所に出すべきという思いを強くしました。div2のはこれの簡単版
今年の目標を振り返る
恒例。放ったらかしでは意味がないんじゃ。
今年の目標 - hogloidのブログ
必須目標
- CF Rating で2350をつける
- つきました
- TC Rating で2550をつける
- つきました
- 進級
- まだよくわかんない
これぐらいは
AOJ 2374 RabbitLunch
解法
O(NlogN),O(Nlog^2N) のやり方もいくつかありますが、O(N) で解くことをオススメします
ヒントはフロー(僕はこれをsnukeに教えてもらった)
かなり面白いので、すぐに見ないほうがいいかも。
見たい人は下までスクロール
与えられた条件を二部グラフのフローの形にしてみると、
source-人参(流量は人参の個数)
人参-キウイ(m*n の辺を張る。流量はすべて1)
キウイ-sink(流量はキウイの個数)
の辺を張る。
求める値はこのグラフでの最大フロー
これは最小カットに等しい。
source-人参の辺からK本、キウイ-sinkの辺からL本カットに入れると、
人参-キウイの(M-K)*(N-L)本を切ればよい。
よって、source-人参の辺・キウイ-sinkの辺 を切るときは、流量の小さいものから切っていけばいい。
source-人参の辺の切る数をiとして0...Nまで動かす。
人参-キウイ、キウイ-sink での最小カットは、
X軸にキウイ-sinkの切る辺の数を取ると、
この2つのグラフを合わせたような感じになる。
キウイ-sinkのグラフは、切る辺は小さい順に並んでいるので、下に凸
人参-キウイのグラフはそもそも直線
となり、和を取ったグラフも下に凸
なので、局所解が大域解になってる
ところで、iを1つ大きくした時、キウイ-sinkのグラフは変わらず、
人参-キウイのグラフは傾きが小さくなる。
このとき、キウイ-sinkの切る数の解は少なくなる方向にのみ動くことがわかる。
よって、iを増やしながら、しゃくとり法をすればいいことが分かる。
ソートをバケツソートで行うと、すべてO(N)
g++拡張・tree
g++拡張にpb_ds(policy based data structure)というのがあって、その中に便利なtreeというのがあります。
細かい使い方まとめみたいなページは見つかりませんでしたが、コンテストでの主な用法をまとめておきます。c++のsetの上位互換みたいな感じで使えます。
CF・TopCoderでは使えます。
用意:
g++の新しそうなやつを使う
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
宣言:
tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update> var_name;
いきなり長いです。さすがにtypedefするべき
keyに順序関係の定義された好きな型を入れてね
使えること:
setでできるものは大体できます。insert,erase,iterator関連・swapなど。
その他に使えるのが、いずれもO(logN)で
- find_by_order 関数
- var_name.find_by_order(k) でk番目（0-indexed）のiteratorを返します。
- order_of_key 関数
- var_name.order_of_key(key) でkey以上の最初の要素が、treeの中で何番目か返します。
が使えます。
このおかげで自前で何かを書く手間が省けるときもあるかも？
実は
- split 関数
- var_name.split(key,tree) でkey以降の要素をtreeに移す
- join 関数
- var_name.join(tree) でtreeを後ろにくっつける
という関数もありますが、どうやら変な実装のせいでO(N)かかるそうです。（少しテストしてみたところメチャクチャ遅かった）
同じkeyは複数保持できません。
null_type を別の型にすると、keyに紐付けされた別の要素を保存できます。
tree_order_statistics_node_updateのところを自前で欲しい要素を付け足した関数オブジェクトを書くと、例えば平衡二分探索木を使ったRMQなどが実現できますが、やっぱりsplitとjoinのせいで使え無さそう。
参考ページ
Implicit cartesian tree in GNU C++ STL. - Codeforces
C++ STL: Policy based data structures - Codeforces
Codeforces Round #230 (Div. 1) E. Deleting Substrings
暗黒時代のCFなのはわかるがEditorialぐらい復活させてくれ :@
http://codeforces.com/contest/392/problem/E
概要
N要素からなる数列{w}がある。以下の操作を繰り返して、スコアを最大化せよ
- 数列の連続する部分を取り除き、その長さをLとすると、v[L]点稼げる。ただし、取り除く部分は隣接する項が絶対値で1ずつ異なっていて、山型でなければならない。(➚→➘)（操作が終わると、取り除かれた部分の左と右はくっつく。また、全部消さなくて途中で終わっても良い）
N<=400 , |v[i]|<=2000 w[i]<=10^9
解法
DP
con[i][j]:=w[i],w[j-1]を公差1,-1の等差数列で結ぶとき、{w}の[i...j)で余ってしまうものを先に使うことになる。先に使うもののスコアの最大値
dp[i][j]:=w[i],w[j-1] を両端とする山型の形を作るときの、その範囲のスコアの最大値。{w}の[i...j)での山型の形の数列に入らないものは先にすべて使うことになる。
dp2[i][j]:={w}の[i...j)をすべて使うときのスコアの最大値。
このDPができると、
res[i]:=[0...i)までのスコアの最大値
をdp[i][j]を使って更新できる。
上のDPは、j-iが短い順にやると実はできる.
con[i][j]は、iの次のくるものを[i+1,j)の中で全部調べる。
dp[i][j]は、山のてっぺんになるものを[i,j)の中で全部調べる。
dp2[i][j]は、dp[i][j]を代入したあと、分割される場所を全部調べる。
時間O(n^3),空間O(n^2)
http://codeforces.com/contest/392/submission/7438155
Codeforces Round #259 E. Little Pony and Lord Tirek
http://codeforces.com/contest/453/problem/E
問題概要:
ポニーがN匹一列に並んでいる。ポニーiは最初siのManaを持っており、毎時間riのペースでManaを増やすが、Manaはmiまでしか持てない（それ以上になるとmiで止まる）
クエリがM回ある。それぞれのクエリで、時刻tiに[l,r]の範囲のポニーのManaを全部刈り取り、その合計を答える。刈り取られると彼らのManaは0になる。
クエリーはtiが狭義単調増加になるよう与えられる。
解法
初期条件siは面倒なのでとりあえず無視。
セグメント木上の区間で、その区間に属するポニーを「刈り取られてからManaが増加する時間」の長さでソート。(mi/ri)
この並びのポニーで、miの累積和、riの累積和を取る。
これで、あるセグメント木上の区間が時刻Tに刈り取られ、その後時間difが経った時にまた刈り取られるとすると、増加時間が dif以上、以下でポニーを分割し、増加時間がdifより少ないポニーたちについてはmiの総和、大きいポニーたちについてはriの総和*difで刈り取る合計が求まる。①
クエリーごとに、刈り取る範囲のポニーの列を、いつ最後に刈り取られたかの区間で分割する。
いつ最後に刈り取られたかの区間について、セグメント木でlogN個の区間に分割できる。
区間K個と重なる範囲を刈り取るとすると、それぞれlogN個に分割し、①の方針でやると二分探索を含むのでO(Klog^2N)の時間がかかるが、刈り取る範囲に完全に含まれる区間は刈り取りの後全部一緒になる。ここから考えるとならしでO(Mlog^2N)になることが分かる。
いつ最後に刈り取られたかの区間はsetで持って重なるものをイテレーションしてもできるが、
以下の方法でもできる：
セグメント木上のあるノードに含まれるポニーが全員同じ時刻に刈り取られたなら、そこで①の感じで処理。
そうでないなら、刈り取る範囲に完全に含まれているとしても、さらに分割。
この方針で、刈り取られた時刻が同じ区間それぞれについて処理している事になる。
あるノードの刈り取られた時刻が一緒かどうかは、刈り取った時にそのノードにフラグを建てておき、下のノードへは使うときに伝播させる。あるノードを更新したら、それらの上のノードで刈り取られた時刻が同じかどうかを確認する、という一般的な処理。
初期条件siがあるので、最後に刈り取られたのが時刻0の場合は、何があってもノードがひとつになるまで分割。
時間O(Mlog^2N)
空間O(NlogN)
