ARC F 未AC問題

2019/3/29現在でのARC Fの未AC問題リスト

・900点

問題:https://atcoder.jp/contests/arc060/tasks/arc060_d

2019/3/30 自力×

全て同じ文字のときはN個に分割するしかなく、元々良い文字列の場合は分割しなくていいので自明。それ以外のときは、(w[0..N-2],w[N-1])と分割すると上手くいくので分割数の最小値は2になり、分割を全て試せばいい(全ての接頭辞、接尾辞について良い文字列かどうか判定する問題だけでも文字列系アルゴリズムを知らなければ難しい)。

 

問題:https://atcoder.jp/contests/arc065/tasks/arc065_d

2019/3/30 自力〇

まず、i<jならばr[i]<r[j]と仮定していい(そうでない場合、l[i]≦l[j]<r[j]≦r[i]より区間jは区間iに完全に入っているので区間jを無視できる)。あとは「dp[i][j]:=区間iと区間i+1が重なっている区間に1がj個あるようにi番目までのシャッフルをしたとき、区間i+1の手前までの列は何通りあり得るか」というDPをすればいい。

 

問題:https://atcoder.jp/contests/arc072/tasks/arc072_d

2019/3/30 自力×

後から入れた水ほど温度が高いのであれば、先に入れた水から捨てていくのが最適。新しく入れる水の温度が最後に入れた水の温度以下である場合、これらの水が混ざったものが同時に入ってくると考えればよいので、「後から入れた水ほど温度が高い」という制約は成り立っているとしていい。

 

問題:https://atcoder.jp/contests/arc073/tasks/arc073_d

2019/4/4 自力×

「dp[i][j]:=i番目までのクエリを処理してコマがx[i]とjにあるときのコストの最小値」というDPを高速化することを考える。漸化式は

dp[i+1][j]=dp[i][j]+|x[i+1]-x[i]| (j≠x[i])

dp[i+1][x[i]]=min{dp[i][j]+|x[i+1]-j|}

となるが、上については全体に定数を足すだけなので簡単。下の式については0≦j≦x[i+1]のときとx[i+1]≦j<nのときで場合分けすれば、min{dp[i][j]-j}+定数とmin{dp[i][j]+j}+定数になるのでセグメント木でdp[i][j],dp[i][j]-j,dp[i][j]+jを管理すればいい。

 

問題:https://atcoder.jp/contests/arc078/tasks/arc078_d

2019/4/5 自力×

「頂点1から頂点Nへの単純パスがちょうど1通り」⇔「頂点1から頂点Nへの単純パスが存在し、パスに含まれるどの辺も橋」

そこで「dp[S][x]:=頂点集合Sに含まれる頂点だけに注目したとき、頂点1から頂点xへの単純パスがちょうど1通りとなるようにするための最小コスト」というDPをすることが出来る。遷移としては「頂点xからSに含まれない頂点yへの橋を追加する(頂点yとx以外のSに含まれる頂点との間の辺を消す分のコストがかかる)」と「Sとdisjointな頂点集合Tについて、Tをx以外とつながらないようにする(Tに含まれる頂点とx以外のSに含まれる頂点の間の辺を消すコストがかかる)」という2つを考えればいい。

 

問題:https://atcoder.jp/contests/arc088/tasks/arc088_d

2019/4/8 自力×

色々書いているけど、要するに木をdisjointなパスで被覆するときのパスの本数の最小値と、そのときのパスの長さの最大値の最小値を求める問題。本数の方は(奇数次数の頂点数)/2という有名事実がある。あとは「最大値の最小値」なので「長さK以下のパスだけで被覆できるか」という判定問題に言いかえてにぶたんといういつもの奴。次数1の頂点を根とした根つき木にして次のような木DPをすれば判定できる。「dp[v]:=vを根とする部分木を長さK以下のパスで被覆するときの、端点をvとするパスの長さの最小値」。

 

問題:https://atcoder.jp/contests/arc090/tasks/arc090_d

2019/4/9 自力△(考察は出来たがデバッグが上手くいかずkmjpさんのブログを参考にした)

場合分けをする。

(i) l<10^8のとき

しゃくとり法の要領で(l,r)を全て試すことが出来る。

(ii) l≧10^8のとき

f(r)-f(l)≦1であることがわかる。

f(l)=k,f(r)=k+1となる(l,r)を数えることは、k*x+(k+1)*y=Sとなる(k,x,y)の組を数えることに対応するが、実はx+yを固定すると(k,x,y)は一意に定まることがわかる(k*x+(k+1)*y=k*(x+y)+y=Sより、kはSをx+yで割った商、yは余りになるため)。

x+yがSの約数である場合y=0となるが、これはf(l)=f(r)のケースに対応する。結局、区間の長さを全て試せばいい。

 

問題:https://atcoder.jp/contests/arc091/tasks/arc091_d

2019/4/10 自力×

実験して法則を見つける系。Kを適当に決めてgrundy数を書き出してみると、NがKで割りきれるときはgrundy(N,K)=N/K、割りきれないときはgrundy(N,K)=grundy(N-floor(N/K)-1,K)となることがわかる。このままだと遅いがfloor(N/K)が一定のところをまとめて計算すると高速化できる。

floor(N/K)=dとおくと、N%K=N-K*dと表せる。Nは1回の操作でd+1ずつ減るのでN-k*d≧x*(d+1)となる最大のxをmとしたとき、m回操作する間はfloor(N/K)はdのまま。あとはgrundy(N-(m+1)*d,K)を再帰的に計算する。

 

問題:https://atcoder.jp/contests/arc095/tasks/arc095_d

2019/4/11 自力〇

今[1..N-1]の順列Pに対応する木があるとする。ここにNを挿入するとその位置によらず、Pの右端の数が書かれた頂点とNが書かれた頂点の間に辺が張られる。右端にある数だけが重要なので本質的にNの挿入位置は右端かそうでないかだけになる。これを元にどんな木が出来るかを調べると、スターグラフをいくつかつなげた形しかできないことがわかる。あとは適当に判定して順列を構成してやる。

N頂点のスターグラフが出来る順列のうち辞書順最小のものは1 3 4 ... N-1 2 Nである。

 

・1000点

問題:https://atcoder.jp/contests/arc064/tasks/arc064_d

2019/4/12 自力×

長さNの回文Sをシフトして得られる文字列が何種類かを考える。これはSの最小周期をdとしたときd種類であることがわかる(任意のiについてS[i]==S[(i+d)%N]を満たすとき文字列Sは周期dを持つといい、Sの周期のうち最小のものを最小周期と呼ぶ)。何故かというと、最小周期がdであることからSを0~d-1回シフトした結果は全て異なるから(もし1≦t≦d-1回シフトして元に戻るなら定義より周期tを持ち、dが最小周期であることに矛盾)。

 

問題:https://atcoder.jp/contests/arc067/tasks/arc067_d

2019/4/12 自力×

l番目の店からスタートしてr番目の店まで歩くことにする(l≦r)。「F(i,l,r):=l番目からr番目までの店で、i番目のチケットと引き換えに食べられる肉の美味しさの最大値」とすると、幸福度の最大値はΣF(i,l,r)-(l番目の店とr番目の店の距離)になる。これを全ての(l,r)のペアについて計算すればいいが普通にやると間に合わない。

iを固定する。F(i,t,t)=F(i,0,N-1)を満たすtがあって、l≦t≦rである(l,r)についてはF(i,t,t)=F(i,l,r)である(全体の最大値を取る点を含む区間の最大値は当然全体の最大値)。そうするとのこりはl≦r<tの場合とt<l≦rの場合になるが再帰的に同じことをしていけば下の図のようにいくつかの同じ値をとる長方形領域に分割できる。imos法を用いて前計算すれば全ての(l,r)についてΣF(i,l,r)をO(1)で求められる。

f:id:Div9851P:20190413132000p:plain

 

問題:https://atcoder.jp/contests/arc084/tasks/arc084_d

2019/4/14 自力×

整数とF2上の多項式を対応づけることにすると、2倍する操作はxをかける操作に、2つの整数のxorをとる操作は多項式の足し算になる。これらの操作で、多項式PとQからP%Qを作ることが出来るのでユークリッドの互除法が出来る。よって与えられたN個の多項式のgcdをgとすると、ある多項式Pがgの多項式倍で表されるとき、またそのときに限りPが作れることがわかる。

 

問題:https://atcoder.jp/contests/arc085/tasks/arc085_d

2019/4/15 自力×

左から順番に要素を見ていく。l≦iであるような区間(l,r)からどの区間を選ぶか決めると、このあとi番目までの要素が更新されることはないので、ここまでのスコアは決まる。よって「dp[i][j]:=l≦iであるような区間(l,r)からどの区間を選ぶか決めていて、j番目(j≧i)まで1になっているときのi番目までのスコア」というDPをすればいい。このままだとO(N^2)だが、インラインDPをするとO((N+Q)logN)になる。

 

問題:https://atcoder.jp/contests/arc098/tasks/arc098_d

2019/4/16 自力×

何かが通れなくなっていったり、何かを分割していったりする場合、後ろから見ると楽になるというのが1つのポイント。後ろから見てゲームを言い換えると最適戦略がわかりやすいゲームに帰着される。

 

・1100点

問題:https://atcoder.jp/contests/arc061/tasks/arc061_d

2019/4/18 自力×

 

問題:https://atcoder.jp/contests/arc077/tasks/arc077_d

2019/4/19 自力〇

 

問題:https://atcoder.jp/contests/arc092/tasks/arc092_d

2019/4/20 自力×

 

問題:https://atcoder.jp/contests/arc093/tasks/arc093_d

2019/4/20 自力×

結局、2~Nを1個 2個 4個 ... 2^(N-1)個のグループにわけて、どのグループの最小値もAの要素でないようにする方法は何通りあるかという問題になる。小さい方からグループに振り分けていくことを考えると、各A[i]は空でないグループに振り分ける必要があることがわかる(空のグループに入れるとこれが最小値となってしまう)。そこで「dp[i][mask]:=2~A[i]をグループに振り分けて、空でないグループがmaskであるような分け方が何通りか」というDPをすればいい。更新するときは、ゼータ変換してからA[i]+1~A[i+1]-1を振り分け、メビウス変換(ゼータ変換の逆変換)をしてA[i+1]を振り分けるという方法でやる。

 

問題:https://atcoder.jp/contests/arc100/tasks/arc100_d

2019/4/24 自力×

解説→https://div9851-tech.hatenablog.jp/entry/2019/04/24/131228

 

・1200点

問題:https://atcoder.jp/contests/arc068/tasks/arc068_d

2019/4/25 自力×

わかりやすいブログ→https://hama-du-competitive.hatenablog.com/entry/2017/02/26/125205

 

https://atcoder.jp/contests/arc069/tasks/arc069_d

2019/4/26 自力×

にぶたん。2SATに帰着されるが、普通にやると節がO(N^2)個になってしまう。セグ木の要領で区間に対応する変数を導入すると節がO(NlogN)個に減らせる。

 

https://atcoder.jp/contests/arc080/tasks/arc080_d

2019/5/2 自力×

差分に注目して区間フリップを端点フリップに言いかえる。すると、「いくつかのマスに駒が置いてあって、好きな駒を1回で奇素数マスだけ進めることができ、同じマスに2つの駒がいるときは両方消すことができる。最短何手で全ての駒を消せる?」という問題になる。i番目のマスにいる駒とj番目のマスにいる駒をペアにして消すためには|i-j|が奇素数のときは1回、|i-j|が偶数のときは2回、|i-j|が素数でない奇数のときは3回の操作が必要なので、そのように辺を張ってマッチングをすればいいことになる。ここで、1回で消せるペアは消した方が得なので、|i-j|が奇素数のペアだけに辺を張って二部グラフの最大マッチングを計算する。残りはパリティが同じもの同士でペアにしていって余ったらそれらをペアにすればいいので解けた。

 

https://atcoder.jp/contests/arc083/tasks/arc083_d

2019/5/4 自力×

2N個のロボットを(0,1)→0,(0,2)→1,...,(0,N)→N-1,(1,0)→N,(2,0)→N+1,...,(N,0)→2N-1というように2N個の頂点に対応させる。そして各ボールについてそのボールを回収できる2つのロボットに対応する頂点の間に辺を張ってグラフを作る。まず、このグラフの連結成分に、頂点数と辺の数が異なるものがあったら答えは0。そうでない場合、各連結成分についてロボットを動かす順番を独立に決められるので、以下では全体が連結とする(グラフの作り方から、異なる連結成分に属するロボットが干渉し合うことはない)。さて、頂点数と辺の数が等しいグラフはループに木を生やした形になる。ループに含まれないロボットたちについてはどのボールを取るか一意に決まり、ループに含まれるロボットたちについては時計回りに取っていくか反時計回りに取っていくかの2通りがある。それはどちらも試すことにして、あるロボットがどのボールを取るか決めたら、あとはそれを実現する動かし方が何通りあるか数えればいい。頂点iに隣接する頂点u[0]<u[1]<...<u[k-1]があって、ロボットiはi→u[x]に対応するボールを取るとする。この場合、ロボットu[0],u[1],...,u[x-1]はロボットiより早く動かさないといけないという制約が生まれる。xをyより早く動かさないといけないときx←yという辺を張ると有向森になって、有向森のトポロジカルソートが何通りあるかは数えられるので、二項係数をかけて頑張ると答えが計算できる。

 

https://atcoder.jp/contests/arc086/tasks/arc086_d

https://atcoder.jp/contests/arc099/tasks/arc099_d

https://atcoder.jp/contests/arc102/tasks/arc102_d

・1300点

https://atcoder.jp/contests/arc062/tasks/arc062_d

https://atcoder.jp/contests/arc070/tasks/arc070_d

・1400点

https://atcoder.jp/contests/arc066/tasks/arc066_d

・1500点

https://atcoder.jp/contests/arc058/tasks/arc058_d

・1600点

https://atcoder.jp/contests/arc063/tasks/arc063_d