https://www.codechef.com/APRIL17?order=desc&sortBy=successful_submissions
Similar Dishes
T組の料理がある。
各料理は4つの材料で構成されている。
T組の料理が似ているならば"similar"、似てないならば"dissimilar"をそれぞれ答えよ。
※似ている : 材料のうち半分以上が同じ
Dish Of Life
N個の島とK種類の材料がある。
i番目の島ではP[i]種類の材料が集まる。
- 全ての島を回っても材料が全て集まらないなら"sad"
- 全ての島を回らないと材料が全て集まらないなら"all"
- 全ての島を回らなくても材料が全て集まるなら"some"
を出力せよ
Bear and Row 01
1と0から成る文字列Nが与えられる。
行える操作は「ある1に対して端っこに行くか隣に1がある状態まで動かす」操作である。
この操作は移動距離+1のコストがかかる。
全ての1を左に移すために必要なコストの総和の最大値は？
Bear and Clique Distances
N頂点ある。
この頂点のうち、1～K番目の頂点は完全グラフであり、辺のコストはXである。
これとは別にM本の辺があり、A[i]とB[i]をコストC[i]で繋いでいる。
頂点Sから他の頂点への最短距離を求めよ。
Chef and Divisor Tree
Divisor Treeは以下のルールで作られた根付き木である。
- 根はある数
- ある親の子はノードに書かれた数の約数(書かれた数は除く)
- 数が1となると葉
- ノードにはコストがあり、そのコストはノードの次数と等しい
(問題文のテストケースに図があるのでそれをみると分かりやすい)
A<=n<=Bをみたす全てのnに対して、Divisor Treeを作り、根からある葉へのパスのコストの総和の最大値を計算し、その総和を答えよ。
Stable market
N個の数列Aがある。
その数列に対してQ個のクエリについて答える。
各クエリでは、[L[i],R[i]]の範囲でのK[i]連続区域は何個あるかを答える。
K連続区域とは同じ数がK個以上連続しているまとまりのこと。
Bear and Random Grid
命令文Sと、N*Nの盤面がある。
盤面は'.'なら通れて、'#'だと通れない。
全てのセルについて、そこを初期地点として、命令文で動ける最大命令数を求める。
'.'のセルで最大命令数を求めたとき、そのxor和を答えよ。
盤面に'#'が出る生成規則がある(割愛)。
Chef and Digits
A[0]～A[9]が与えられる。
ある数について、現れる文字をカウントした時に、ある数iの個数が丁度A[i]となったとき、その数は嫌いとされる。
L<=n<=Rを満たす全てのnに対して、嫌いでない数は何個あるか。
Serejs and Billiards
マラソン問題
ビリヤードをする。
(0,0)から(N,N)の盤面がある。
ボールがM個あり、4*M回まで操作ができる。
操作のルールは
1. 加速度としてdx,dyを-1,0,+1で指定し、E回分だけ動かす。
2. 端に当たると跳ね返る
3. (-1,-1),(-1,N+1),(N+1,-1),(N+1,N+1)のいずれかに入ると得点
Heavy-Light Decomposition
与えられた根付き木をHL分解する。
- Light辺を通るときは長さLでコストL
- Heavy辺を通るときは長さLでコスト(ceiling[log_2L] + 1)
かかる。Heavy辺を上手く選んで、根から全ての葉へのコストの最大値を最小化せよ。
以下、解説
Similar Dishes
Dish Of Life
https://www.codechef.com/viewsolution/13278966
セグメント木(最小値)を上手く使う。
st[i] := 種類iが取れる島の個数
としてカウントし、st[0,K-1]==0なら全ての島へ行っても集まらないので"sad"
あとは全ての島について、訪れなくても大丈夫かを判定する。
取れる種類をstから引いてst[0,K-1]!=0ならば、無くても大丈夫なので"some"
次の島を確認する前に引いた分は戻しておく。
全てチェックして該当するものが無ければ"all"
Bear and Row 01
https://www.codechef.com/viewsolution/13279183
貪欲法。
移動距離は全ての1について同じなので、命令する回数が多くなるように貪欲をする。
その為、頭から順に左へ移動できそうなものを順番に移動させていく。
10000100010001 00001100010001 00000001110001 00000000001111
このように上から1の塊を作っていく感じで貪欲していく。
Bear and Clique Distances
https://www.codechef.com/viewsolution/13279489
ダイクストラ法で最短経路を求める。
普通の辺の方は普通にやれば良いが、頂点1～Kのうちのどれかを初めて処理するときだけ、その頂点iから頂点1～Kへの辺を考えてやる。
すると解ける。
Chef and Divisor Tree
部分点解法(～Subtask#3)
https://www.codechef.com/viewsolution/13285034
メモ化再帰と素因数分解で解く。
ll rec(ll x) := 根がxの時のコストの総和の最大値
としてこれをメモ化と素因数分解を使いながら解いていく。
あとは、A<=x<=Bに対してrec(x)-1を足していくと答えとなる
満点解法
https://www.codechef.com/viewsolution/13337031
満点解法の制限だと、A<=x<=Bのxを素因数分解するだけで時間オーバーする。
蟻本を眺めていると「区間篩」というのがある。
ある区間に対して素数判定をするというものだが、これを工夫することである区間に対して高速に素因数分解できる。
https://yukicoder.me/wiki/algorithm_summary
yukicoderの区間篩の欄を見ると、「R<=10^12, R-L<=10^6という制約がヒント」とあって、まさにそう。
部分展開法でそれぞれ素因数分解していた所を区間篩を使って素因数分解に変更する。
しかし、それでもまだ間に合わない。
メモ化をもう少し頑張る必要がある。
素因数分解した時の素因数の数は実は問題ではない。
2*3^3の組合せの個数と3*5^3の組合せの個数は等しくなる。
なので、素因数分解した後に、素因数を2,3,5,...で正規化する。
素因数分解したときの形は似たような感じになりがりなので、これでかなり状態数を削減できる。
ここまでしてやっと通る。
Stable market
https://www.codechef.com/viewsolution/13287401
満点解法のためには平方分割が必要。
hamayanhamayan.hatenablog.jp
部分点解法
本当に愚直に連続している個数を数えていくだけ。
満点解法
平方分割をする。
方針立ては難しく無いが、実装が難しい。
事前に分割された領域に対して左右の連続領域と左右の連続領域以外の連続領域の個数の累積和をとっておく(pre関数)
あとは、普通のカウント(query関数)と分割された領域に対するカウント(query2関数)を併用しながら、高速に処理していく。
Bear and Random Grid
部分点解法https://www.codechef.com/viewsolution/13329681
部分点解法1(subtask13関数)
'.'のセルから初めて愚直にシミュレーションする。
C++だと早いからか、subtask3も何故か通る。
部分点解法2(subtask2関数)
'#'が無いので、衝突判定の必要は無くて、領域で考えていけば良い。
事前にi回行動を行った時の相対距離を求めておく(pre関数)
あとはこれを使って二分探索で、そのセルから初めてN*Nのグリッドをはみ出さないように動かせる最大を探していく。
それを纏めると答え。
満点解法
部分点を見ると、P<0.1の場合のみ何とかすれば良い。
'#'が疎であるため、壁から逆算して各マスに対して最長がどれだけか測れば良いとEditorialに書いてあったけど、分からない。
Chef and Digits
Subtask1のみhttps://www.codechef.com/viewsolution/13297376
Subtask1
本当に愚直に書くだけ。
[L,R]の数に対して題意を満たすかチェックして数え上げる。
Serejs and Billiards
63.017解https://www.codechef.com/viewsolution/13337441
最短で全てのやつを集めるみたいに、全部右側に寄せて、それを全部下に寄せて、カップインさせたら、結構点数出た。
