読者です 読者をやめる 読者になる 読者になる

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:どうしたら本番中にこれに気づけるのだろう

AGC007 ひとこと解法

コンテストページ

AtCoder Grand Contest 007 - AtCoder Grand Contest 007 | AtCoder

解法

A:Shik and Stone

移動方向を右と下にしてbfs。通った'#'をメモしておいて最後に全て通ったかチェック。

B:Construct Sequences

aをa_0 < a_1.. bをb_0 > b_1... としておいてa_piにi足す。a,bは幅を大きめにとる(20000とか)

C以降

まだ

ARC063 ひとこと解法

コンテストページ

arc063.contest.atcoder.jp

解法

C: 一次元リバーシ / 1D Reversi

色が変わった回数をカウント

D: 高橋君と見えざる手 / An Invisible Hand

大利益額とそのパターン数を数える

Chokudai Contest002 解法

問題概要

109以下の整数を100個出力しろ。出力した数の約数の集合(重複は除く)の数が多いほど良い。

コメント

本番では高度合成数を適当にいくつか出力するくらいしか分からなかった。

のでTLに流れてた回答を見て解いた。解法1を本番中に思いつきたかった...

コンテストページ

Chokudai Contest 002 - Chokudai Contest 002 | AtCoder

解法

解法1:高度合成数×素数

約数が多い高度合成数に異なる素数をかけて結果が109を超えないものを出力。

すると250-1000個程度の約数をもつ高度合成数が選ばれるので35000-40000くらいの点数が出る

提出コード:Submission #965609 - Chokudai Contest 002 | AtCoder

解法2:約数が多い数を10000個ほど挙げて焼きなまし

色々調べながらやってみた
コード:https://gist.github.com/SoichiSumi/34fb428b9b07a2f6d8df209f35087d36

initial post

競プロメモ、制作物紹介、技術メモなど,技術的な事を書いていきます。

大体以下のようになると思います。

竸プロ..一言解法とコード

制作物紹介..開発過程や作っていて面白かったところ

技術メモ..手順書

 

質問、コメント等大歓迎です。