Codeforces Round #382 (Div. 2) 解法
2完。Cの題意を読み取れず終了。文は読めていたが出題者の気持ちが分かっていなかった..
コンテストページ
Dashboard - Codeforces Round #382 (Div. 2) - Codeforces
A. Ostap and Grasshopper
問題
長さnの一本道にGrasshopperとInsectが置かれる。Grasshopperはkマス飛ぶ事ができる(間のマスには移動できない。例えばk=2なら前後のマスには行けない)。また、道には障害物があり、障害物のあるマスには移動できない。Grasspopperはinsectのところまで移動できるか。
制約:(2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1)
解法
nが小さいのでそのままシミュレート。Grashopperが左にくるようにGrasshopperとInsectの位置をswapしておくと両方向調べなくて良くなる
提出コード:
Submission #22532553 - Codeforces
B. Urbanization
問題
n人の人がおり、それぞれaiの資産を持っています。町を2つ作る予定です。各町にはn1、n2人住むことができます。町に住む人の資産の平均Avg1、Avg2の和を最大化してください
制約:(1 ≤ n, n1, n2 ≤ 100000, n1 + n2 ≤ n), (1 ≤ ai ≤ 100000)
解法
資産をソートして大きいほうからn1+n2個を取得する。その中で小さいものから順に、住める人数n1、n2の大きいほうに住ませる。残りは小さいほうに住ませて、それぞれの平均の和を出力。
提出コード:
Submission #22540036 - Codeforces
C. Tennis Championship
問題
選手がn人の勝ち残り式のトーナメント表を作る。ただし、選手はその勝利数の差が1より大きい相手と戦ってはいけない。優勝者が戦うことができる最大の試合数を求めよ。
制約:(2 ≤ n ≤ 10 ^18)
考察
勝利数の差が1より大きい相手と戦ってはいけない制約から、明らかにnが2-7のときの優勝者の最大試合数は1,2,2,3,3,3となる。n=8のとき、下図より最大試合数は4となる。もし(6,8)で戦って6が負け、(1,8)で戦うことになった場合、3勝vs1勝となってしまうが、最大の試合数を求めるので大丈夫みたいです。*1
@esplo77 こういうトーナメントでしょうか? pic.twitter.com/wTV1SaqKkJ
— ようせい (@yousei_coding) November 28, 2016
n=8まで書き出してみると、n=2,3,5,8で最大試合数が増えているのがわかる(最大試合数2のトーナメントと3のトーナメントを組み合わせて最大試合数4のトーナメントが作れる)。この事からnがフィボナッチ数のときに最大試合数が増加する。
解法
フィボナッチ数列を作ってほい
提出コード:
Submission #22560527 - Codeforces
D. Taxes
問題
今年の収入がnあります。収入には税金がかかり、nにかかる税金は、nでない、nの最大の約数です。Funtさんは収入を1以上の任意の数に分割することで払う税金を最小化したいです。分割とは、例えばn=n1+n2+n3...とすることです。払わなければいけない最小の税金を求めてください。
制約:(2 ≤ n ≤ 2·10 ^9)
考察
分割された数niが素数ならniにかかる税金は1.nをなるべく少ない素数の和に表したくなる。
解法
まず、nが素数なら答えは1。4以上の偶数なら、ゴールドバッハの予想より2つの素数の和で表せるので2。そうでないなら、ゴールドバッハの予想より3。但しこれだけでは漏れがあり、n-2が素数の時はn-2、2と分割することにより税金2で済ませる事ができる。*2
提出コード:
Submission #22583417 - Codeforces
E. Ostap and Tree
解いてません
まとめ
Cの問題文もう少し説明してくれても良かったんじゃないかな・・・