youseiの技術メモ

競プロで書いたコードや制作物の紹介など,技術的な事を書いていきます

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

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の問題文もう少し説明してくれても良かったんじゃないかな・・・

*1:3勝vs1勝が出来たら、3勝側の勝ちが決定するとかかなあ

*2:どうしたら本番中にこれに気づけるのだろう