2017-10-29
■ Codeforces Round #443 Div1
参加してないんですが、ACDEをupsolvingしました。最近のこどふぉらしからず(?)(B以外)どれも結構面白かったので書きます。
A
問題概要
N(<=5*10^5)回、0以上1023以下の値をAND,XOR,ORする。これと等価な操作を5回以内の0以上1023以下の値をAND,XOR,ORすることで作れ。
解法
はじめのi番目のbit(0<=i<10)が0,1だった時、操作を終えた時どうなっているかを見る。
0,1 -> 0,0となっているものは0とのANDで、0,1 -> 1,0となっているものは1とのXORで、0,1 -> 1,1となっているものは1とのORで作れるので実は必ず3回で出来る。O(N)
C
問題概要
N(<=5*10^4)人の人にK(<=10)種類のパラメーターが定まっている。
「ある2人があるパラメーターの値で競い、小さい方が敗北し、消える」
という操作を繰り返す時、1....i番目(1<=i<=N)の人に対して最後の1人になり得る人の数を求めよ。
解法
人i -> 人j iff 人iは人jに勝るパラメーターがある
として有向グラフを作る。
このとき、このグラフをSCCすると任意の2人に対し双方向、あるいは一方向の辺が貼られているのでクリークになり、
かつ全順序が定まっていることが分かる。
よって、一人ずつ追加していくと
どこかに挿入される or 連続した部分列と新規の人が一つの強連結成分になる
が起こるので、setで持って列を管理すると解ける。 O(NK log NK)
D
問題概要
K(<=12)匹の生き物が居て、N(<=10^5)種類のパラメーターが定まっている。
Q(<=10^5)個のクエリが来るので処理してください。クエリは以下の3種類:
- ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのmaxになる生き物を作る
- ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのminになる生き物を作る
- ある生き物のあるパラメーターの値を出力する
解法
2乗を1/64パワーでゴリ押す解法をしたくなるが我慢して考えると、これを思い出す。
2分探索をすることを考えると、値がmid以上 -> 1 otherwise -> 0と変換して、同じ操作をし0か1を見る、ということをすればよいとわかる。
ここで、考えられる0と1のパターンは2^K通りしかないので、2^K通りすべてに対してクエリの順番に操作を行っておくと解ける。O(2^K * Q)
E
問題概要
長さN(<=10^5)の数列aが与えられる。Q(<=10^5)個のクエリに答えよ。クエリの形式は以下の通り:
L,R(1<=L<=R<=N)が与えられるのでa[L..R]に対し
「隣接する2要素を選び(x,yとする)、削除してx+2yをその場所に追加する」
ということを要素が1つになるまで繰り返すとき、最後の値の最大値をmod 10^9+7で求めよ。
解法
2^b_i * a_iの形の値の和になることは明らかで、b_iの条件を考えると
- b_L = 0
- 1<=b_i<=b_(i-1)+1(L
となりそうなことが手を動かすとわかる(未証明)ので、
以下この問題を解く。
b_iをb_(i-1)+1にしない時のことを考えると、明らかに1にするしかないことが分かる。(中途半端な値を取るメリットはないため)
よって、b_iは0,1,2,...,x,1,2,...,y,1,2,...z,...のような階段を繰り返す感じが最適とわかる。
どこで区切るべきかを考えると、
後ろから見たときに負になったところで切るべきで、逆に負になったところで切らないのは最適ではないことが分かるから、
c_i = a_1 + 2 * a_2 + ....+ 2^(i-1) * a_i
とすると、Xが右端の階段は
c_Wはc_Xよりも大きく、かつそのようなWの中で一番右の値(Yとする)が左端になることが分かる。(ないときはL)
よって、c_iをソートし、ダブリングをすると解ける。 O((N+Q) log N)くらい?
2017-09-15
■ みんなのプロコン本選 E - 瞬間移動装置
本番ぶりに考察したら割とすんなり思いついた、良問です
問題概要
N(<=10^5)頂点のクリークからM(<=10^5)本の辺を取り除いたグラフにおいて、頂点cから頂点dに行く時の最短経路をQ(<=10^5)組求めよ。
解法
本質は、次数がN/2以上の頂点同士を選んだ場合答は1か2であることに気づくことです。(そそ)
そして、次数がN/2未満 <=> 補グラフでの次数がN/2より大 よりそのような頂点は高々2*M/(N/2) = 4*M/Nしかなく、
4*M/N <= 2*Nが成り立つのでNの値で場合分けするとそのような頂点は高々1000個くらいしかないことがわかる。
ということは次数がN/2未満の頂点からO(N+M)でBFSして答を前計算してやれば良いとわかる。
BFSのやり方は、バケツソートのような感じで距離が0,1,2....の順に見ていき
「距離Dの頂点全てに対し取り除かれた辺でつながっている頂点に+1した後、未処理の頂点をすべて舐めて今までの加算回数(=距離D以下の頂点の個数)と頂点の値が等しくないなら距離D+1として決定する」
という処理を行えばよい。(未処理の頂点をすべて舐めて良いのは、距離D+1にならない頂点を見る回数は合計で高々O(M)回、距離D+1になる頂点を見る回数は合計で高々O(N)回なので)
以上を実装すると、計算量O(sqrt(M) * (N+M))で通る。
2017-09-05
■ Codeforces Round #432 Div1 E Random Elections
めっちゃ良問だと思ったので書きます
問題概要
n個のbool値を受け取り1個のbool値を返す関数が与えられる。
この関数は「入力をflipすると出力もflipされる」が成り立っている。
今、n人の人間が3人の候補者に対しての3!=6通りの順序を独立にランダムに選ぶとき、
1人の候補者が他の2人に勝つような組み合わせは何通りあるか。
(2人の比較は各々の人間の(AをBよりも好むか)のbool値を関数に与えたときの出力が1ならA,0ならBとして定義される)
解法
答は、出力が1になるような2^(n-1)個のbitmaskのペア(重複を許す)に対し2^(一致している桁の個数)の総和を3倍した値。
計算において高速ゼータ変換の考え方を利用する。
dp[mask][i] = (上(n-i-1)bitがmaskに一致している値に対して、2^(下(i+1)bitでmaskと一致している桁の個数)の総和)
とすると、
dp[mask][i+1] = dp[mask][i]*2+dp[mask xor 2^i][i]
で求まる。
まともな実装で14行とか http://codeforces.com/contest/850/submission/30090122
2017-06-18
■ AOJ-ICPC埋め (2nd)
面白かったのをピックアップします。
鎖中経路 (550pts)
中心&交点を列挙してdijkstraする。辺を貼れる条件の言いかえが結構難しい。
ぼくのかんがえたさいきょうのおふとん (550pts)
dp[mask] = (maskに含まれる布団のぬくもりの和をSとするとき、maskに含まれる布団のあり得る順番すべてに対して需要がS以下の日に対する不快度の和の最小値)とすると通る。
Dictionary (550pts)
色々な意味で難しい。dp[L][R][K] = (L~Rの辞書をK文字目以降で辞書順に並べ替える方法の数)とする。
選挙活動 (600pts)
考えるべき点は(人-多角形の頂点)の直線同士の交点のみ。あとはライブラリを貼ってなんとかする。
ICPC Teams (600pts)
これはかなり難しい、あと良問。余事象を考えて包除原理すると制約がsameだけになるのでできる。
Polygon Guards (700pts)
凹多角形と点の包含関係は偏角の和で判定できるらしい。あとは解の上界を見積もって枝狩り探索。
Towns along a Highway (800pts)
探索木の大きさをO(2^N)にしようと考えると解ける。左右から1つずつ決めていくだけ。
回転と書換 (800pts)
区間DPである区間を文字chに変換できるかを求めたあと、2つの区間を持つDPで徐々につなげていって最大値を求める。
2017-06-14
■ AOJ-ICPC埋め (1st)
競プロ再開します。(今回はマジです。) 最近やった問題のまとめ的なことをします。
Rabbit Party (500pts)
クリークを全て調べて終わりです。(575)
引っ越し (550pts)
http://joisc2011.contest.atcoder.jp/tasks/joisc2011_bookshelf をします。
つながれた風船 (550pts)
高さで二分探索することを考えると、結局N個の円があった時すべての円が含む点が存在するか否かを判定すれば良くなる。
2円の交点と各円の中心を考えれば十分。
夕食 (550pts)
良問。そのままDiv1Medに使えそう。解法は食堂に使うべき順番(Ci+i*pの大きい順)が決まるので、食堂を0個、1個、2個...使う場合の幸福度を順に計算してmaxをとればOK.
Reverse Sort (600pts)
解の上限は9なので、8以下にできるかを考える。区間を選び反転する操作は可逆なことに気づけば半分全列挙のノリですり合わせるだけ。(カンニングしました。)
ほぼ周期文字列 (600pts)
sa+lcpを貼って、Tだけずらした文字列同士に対してグチャグチャやると通る。ハッシュを使った解法の方が綺麗に書けます。
最強の呪文 (700pts)
良問。解法は後ろから見て(dp[v] = (vからゴールに至る辞書順最小の文字列)とする)ベルマンフォードをする。存在しない場合を弾くのが難しくて結局良く分からないまま通してしまった(反省)。
800pts以上はなかなか手がつかなさそうですが国内予選まで頑張りたい。
2016-12-31
■ 2016年を振り返る
競プロと少し疎遠になったのもあり目標を立ててその結果発表をするだけのブログになりつつありますが、今年も振り返ります。
(目標: http://topcoder.g.hatena.ne.jp/Hiro180/20160103/1451813037 )
JMO: 1/20 春合宿止まりでした。
JOI: 1/10 レベルが高い。
運動会: 0/20 大事なのは優勝することじゃないです。(じゃなんでこんな目標にしたんですかね....)
(ちなみにそれぞれ2回戦 / 5位 / 4位 でした)
iPad模試: 0/5 不可能。
東大模試: 4/9 秋OPで339取った。3位とかどうして取れると思ったのか。あとA判阻止した本レは許さん (白目)
実テと定期考査: 4/4 実テで2回1位だった。定期考査も年間9.8だったし良いのでは。
卒業条件: 4/4 遅刻28とかしたけどセーフ。
音ゲー: 4/4 結構スッパリ辞めました。(模範的受験生なので最近ハエレ鳥乗せてしまったのは内緒) (ゲーセンは殆ど行かなかった)
生活リズム: 1/4 卒業は出来たので情けの1点。() 来年の課題です。
パソコン甲子園: 3/4 健闘できたので3位だったけど高評価。Isは良いコンビだったと思います。
数学甲子園: 4/4 結果は4位ですが満足だし楽しかったから満点。良いチームだった。
数学甲子園の審査員には京大の特色入試レベルの問題も評価して貰えなかったしIMOの3番級の問題でも作れば良いんじゃないんですか。知らんけど。
適当なイベント: 4/4 化グラ金。参加するとすら思ってなかったけど楽しかった。
コミュ力: 2/4 微増。
人生を楽しむ: 3/4 まあ概ね楽しんだ。
総計: 35/100 (落第)
まとめ: 目標を得点制にするのやめます (震え声)
追記: そういえば目標に無かったので忘却してましたが、申し訳程度の競プロ要素としてSRM 694のwriterをしました。後でそれについて記事を書きます。(たぶん)
最近解いた問題
たまには競技プログラミングのブログも書こうと思います。
面白かったのとか教育的なのとかをまとめる。
■ Yandex 2016 round2 D
<問題概要>
Ax+By = Cを満たす非負整数x,y全てに対して C(x+y,x)の総和を求めよ (A,B<=100 C<=10^18)
<解法>
要するに「総和がCになるようにA,Bを並べ替える方法は何通りあるか」を求めればよい。行列累乗するだけ。
■ csacademy beta round 7 Array Coloring
<問題概要>
N個の無色のセルをM回異なる色で区間を塗った結果が与えられる。考えられる色の順番すべてに対して、「色を塗られた回数」の最大値が最大になるとき、その回数を求めよ (N,M<=100000)
<解法>
色ごとに(左端、右端)を求め、ある色と色に対し、「片方の(左端、右端)を含む最小の(左端、右端)がもう片方の(左端、右端)」であるとき、対応する頂点間に有向辺を結ぶことを考えると、森になる。ダミーの根を作り木にして、木DPをする。
「間に根の色を挟まないような子の集合に対し、1つはdpの値を、その他は1を加えた値」の最大値が今考えてる部分木に対するDP値。
■ SRM691 Div1 Med
<問題概要>
仕事がN個あり、経験値と係数が決められている。得られる収入は(これまでの経験値の総和)*(その仕事の係数)である。
ただし、Nは偶数で、N/2個仕事をした時点で研修に参加し経験値がX増えるものとする。
収入を最大化せよ。 (N<=50,経験値,X<=100000,係数<=10)
<解法>
X=0の場合を考える。
(経験値、係数) = (ex1,co1),(ex2,co2)の2つの仕事を考える。これまでの経験値をexpとすると、収入は
・前者->後者: (exp+ex1)*co1 + (exp+ex1+ex2)*co2
・後者->前者: (exp+ex2)*co2 + (exp+ex1+ex2)*co1
となるので、(前後はどちらも同じ。)
実質ex1*co2とex2*co1の比較であり、それはつまりex1/co1 と ex2/co2の比較である。
以上より、(exp/coef)が大きい方からやるのが良いと分かった。 (こういう問題、150問に1問くらいのペースで見るイメージがある)
X>0の時にはこれではうまくいかない。しかし、Xの前後ではそれぞれこの順番で並べるのが良いので、
順に振り分けていくDPを考える。
ここで、収入の計算方法を
(exp1+exp2+.....+expE) * coEを毎回加えるのではなく、(coE+co(E+1)....+coN) * expEを毎回加えるという発想をすると、
研修の前にやった仕事に対する係数の総和を決め打ちすると(tmpCoとする)
前に振り分けたときは(sum(co)-sum(振り分け済みの前のco)) * exp
後ろに振り分けたときは(sum(co)-tmpCo-sum(振り分け済みの後ろのco)) * exp
を毎回加えればOK。
計算量は50 * 25 * 250のDPを25*10回くらいするのでまぁ通る。 良問。
■ SRM692 Div1 Med
<問題概要>
長さSの文字列が与えられる。(length(S)<=100)
以下の条件を満たす文字列は何通りあるか.
・non-intersectなSの個数の最大値はK個 (K<=10^9)
・長さはK*length(S)以上K*length(S)+N以下 (N<=1000)
・文字はすべて英小文字
<解法>
貪欲に取っていったときの出現箇所を考える。
1つ目の出現箇所までに無駄な部分がi文字になるような場合の数は、愚直なDPで計算できる。
一つ前の出現箇所から無駄な部分がi文字になるような場合の数も、愚直なDPで計算できる。
ここで、dp[i][j] = 2^i個文字列が出現するときに無駄な部分がj文字になるような場合の数
とすると、O(N*N*log K)くらいで計算できる。
最後の出現箇所から無駄な部分がi文字あるような場合の数も、愚直なDPで計算できる。
以上で求めた値を掛け合わせて足せば答が出る。
■ SRM692 Div1 Hard
<問題概要>
根付き木が与えられる (頂点数<=300000)
全ての部分木に対し、(ある頂点からすべての頂点へのパスの重みの総和)の最小値のXORを求めよ。
<解法>
重心が最小化する頂点なのはまあそれはそうっていう感じで
部分木に対し、重心が求まればパスの重みは求まるので、重心を求めることを考える。(地味に256MB制限が厳しいのでsegtreeに逃げることはできません)
ところで、ある部分木(根をVとする)に対し
すべての部分木サイズがもとの部分木サイズの半分以下ならVが重心になり、そうでないときは
部分木サイズが最大の子(V2とする)の重心の祖先のどれかが重心になることが示せる。
(前者は自明、後者はV2の祖先以外が重心になるとすると、その頂点の部分木サイズは明らかに小さすぎるから矛盾)
よって、(自分から子へのパス重みの総和、重心)を返しつつDFSをすればOK.コスト計算はDoublingでできる。
(重心を求めるフェーズがやばくならないのは、「系列」が変わらない限りO(N)で済むことと、「系列」が変わるときには部分木サイズが倍以上になるからまとめてO(N log N)的な感じだと思います)
