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辺を上手く選んで、根から全ての葉へのコストの最大値を最小化せよ。
以下、解説
続きを読む