AGC024 B Backfront

問題文

https://beta.atcoder.jp/contests/agc024/tasks/agc024_b

 

選ばない要素は公差1の等差数列になっていないといけない.

そうなっていれば,適当な順で先頭と末尾にうごかすことでソートできる.

例えば3 2 5 1 4 6の場合,3 4を固定して2を先頭に,1を先頭に,5を末尾に,6を末尾にうごかすことで4回で出来る.

という訳で一番長い等差数列を見つければよい.

続きを読む

ARC101 E Ribbons on Tree

問題文

https://beta.atcoder.jp/contests/arc101/tasks/arc101_c

 

どの辺にも少なくとも1本のリボンが張られるようなペアの分け方を直接数えるのは難しい.「f(S)=Sに含まれる辺には1本もリボンが張られないようなペアの分け方」とすると包除原理より答えはΣ(-1)^|S|f(S)で求まるので,これを使って上手く求めたい.

Sに含まれる辺に1本もリボンが張られないペアの分け方はどんなものだろうか.これは,木からSに含まれる辺を取りのぞいて|S|+1個の連結成分に分割し,各連結成分内でペアを作るような分け方である.

ではx個のものがあって,それらをペアに分けるとき,異なる分け方は何通りあるだろうか.

これはxが奇数のとき0通り,xが偶数のときは(x-1)・(x-3)・...・1通りである.

これで計算量を無視すればとけたのだが,今回の場合,Sを全て試すことは当然できないので工夫が必要(本番ではここから進めなかった).

包除原理の高速化には色々なパターンがあるが,今回の場合は|S|の偶奇で分けて,|S|が偶数であるとき,|S|が奇数であるときそれぞれについてΣf(S)を求めればいい.

これで重要なのがSの偶奇と根が含まれる連結成分の大きさ(その連結成分をペアに分ける方法が何通りか計算するため)だけになったので,「dp[v][s][p]=頂点vが含まれる連結成分の大きさがsで,頂点vのサブツリー内で取りのぞいた辺の数の偶奇がpであるときのペアの分け方(ただし頂点vが含まれる連結成分はまだペアに分けない)」として木DPをすれば|S|が偶数であるとき,奇数であるときそれぞれについてΣf(S)が求まる.

続きを読む

ARC087 F Namori Grundy

問題文

https://arc079.contest.atcoder.jp/tasks/arc079_d

 

どの頂点も入次数が1であることから,グラフの形は以下のような「なもりグラフ」になる.

f:id:Div9851P:20180822165818j:plain

入次数が1であるから,どの頂点についても「親」を定義することが出来る(同様に「子」も定義する).

まず簡単な場合としてグラフが有向木(根つき木の無向辺を親→子の向きに向き付けして有向グラフにしたもの)であるときをかんがえると,子に割り当てられた整数が全てわかっていれば親に割り当てる整数も決まるので再帰的に計算すれば全ての頂点に割り当てる値が一意に定まる(常に割り当てられる).

元の問題に戻ると,輪の周りに生えている木のところについては上の方法で割り当てる値を計算しておいて,あとは輪の上にある適当な頂点を選んでその頂点に割り当てる値を全て試せばよい(1つ決めればさっきと同様にして輪の上にある頂点に割り当てる値は全て決まる).

ちなみに輪を見つけるには「適当な頂点からスタートして親をたどっていくと,どこかで同じ頂点が現れる.二回現れた頂点の間に出てきたのが輪」というアルゴリズムを用いればいい(どこかで見たことがあった).

続きを読む

ARC075 F Mirrored

問題文

https://arc075.contest.atcoder.jp/tasks/arc075_d

 

ケタ数を固定することにし,kケタの整数で,rev(N)=N+DとなるNを数えることにする.

10^iのケタの数字をa[i]とすると,N=Σa[i]*10^iでrev(N)=Σa[k-i-1]*10^iとなるから,

rev(N)-N=Σ(a[k-i-1]-a[i])*10^i=Dとなるようaを決める方法が何通りかを数えることになる.

ここでa[k-1]-a[0]≡D(mod 10)であることがわかる.例えばD=63ならa[k-1]-a[0]=3 or -7の二択である.

このうちどちらかに固定してやると,同様にしてa[k-2]-a[1]の値も二択になる.こうしていくと,結局2^(k/2)通り試してやればこのようなNを全て数えることが出来る.

あとは固定するkをどこまで試せばいいかだが,これは1から18まで試せばよい.

※Dのケタ数の2倍まで試せば良いことをちゃんと示せてない

続きを読む

ARC063 E 木と整数

問題文

https://arc063.contest.atcoder.jp/tasks/arc063_c

 

はじめから値の書かれている頂点を一つ選び,それを根とした根つき木と見ることにする.

各頂点に書ける整数の範囲を調べたい.

葉ノードの場合,書ける整数の範囲は,はじめから整数vが書いてあれば[v,v],整数が書かれていなければ[-INF,INF]になる.

そうでない場合,書ける整数の範囲は,i番目の子に書ける整数の範囲を[l[i],r[i]]としたとき,[l[i]-1,r[i]+1]の共通部分になる.ただしi番目の子にはじめから整数vが書いてある場合,さらに[v,v]との共通部分をとる.共通部分が空になってしまった頂点があれば,Noを出力する.

そのような頂点がないときは,親に書かれた整数に+1または-1して求めた範囲に入る方を書いていけばちゃんと書ききることが出来る.

(根からの距離で偶奇が決まるのだが,+1したときと-1したときを両方調べ,どちらも範囲に入っていなければ偶奇が間違っていることを検出できて,このときもNo)

続きを読む

ARC059 F バイナリハック

問題文

https://arc059.contest.atcoder.jp/tasks/arc059_d

 

sがどういう列なのかはどうでもよくて,sの長さだけが本質ということに気づけば終わり.というのも,例えば最終的に00,01,10,11が表示されるようなキーの押し方というのは全て等しい(偏りはない)はずだから.

よって dp[i][j]=i回キーを押して長さjの文字列が表示されるようなキーの押し方が何通りか というDPでdp[N][|s|]を求めて,2^|s|で割ればいい.

続きを読む

ARC078 E Awkward Response

問題文

https://beta.atcoder.jp/contests/arc078/tasks/arc078_c

 

Nを答えとする.「? n」と質問すると,Nとnを文字列として比較したときの大小と数値として比較したときの大小が同じならばYes,そうでなければNoが返ってくる.

Nのケタ数を決定する方法をかんがえてみる.例えば「? 10000」と質問すると,Nが10のべき乗でなければ,Nが5ケタ以上の整数ならばYes,そうでなければNoが返ってくるのでこれを利用してにぶたんが出来そう.

「? 1000000000」と質問すると,Nが10のべき乗のときYes,そうでないときNoが返ってくるので,これを用いてあらかじめNが10のべき乗の場合は弾いておく.

もしNが10のべき乗であることがわかったらあとは簡単なので略(コーナーケースに注意).

以下,Nは10のべき乗でないとする.

先にのべた方法でケタ数dを決定し,上のケタから順番に数字を決定していこう.

「? (これまでにわかっているケタ)M(全体がd+1ケタになるまで0を並べた列)」と質問すると,Yesが返ってきたらこのケタの数字はM未満,Noが返ってきたらこのケタの数字はM以上であることがわかり,これを利用してにぶたんが出来る.

ただし,例えばN=1230の3ケタ目を決定しようとして「? 12300」と質問すると,Yesが返ってきて3ケタ目は3未満ということになってしまう.そこで,Yesが返ってきたときは「? (これまでにわかっているケタ)M-1(全体がd+1ケタになるまで9を並べた列)」という質問もする.このときYesが返ってきたらNは(これまでにわかっているケタ)M(全体がdケタになるまで0を並べた列)という形になっていることがわかり,Noが返ってきたら本当にこのケタがM未満であることがわかる.

候補が10個あるときにぶたんに必要な質問は高々3回で,この全てがYesだとすると必要な質問は6回.これを9ケタでやると6×9=54回で,10のべき乗かどうか判定する質問と,ケタ数を決定するのに必要な質問を含めても60回程度で済むことがわかり,とけた.

続きを読む