yoyoyousei technical notes

サーバ、インフラ周りについて書きます

AtCoder Regular Contest 083 解法

コンテストページ

arc083.contest.atcoder.jp

C - Sugar Water

問題

次の４種類の操作を行って砂糖水を作る。

  • 操作 1: ビーカーに水を 100A [g] 入れる。
  • 操作 2: ビーカーに水を 100B [g] 入れる。
  • 操作 3: ビーカーに砂糖を C [g] 入れる。
  • 操作 4: ビーカーに砂糖を D [g] 入れる。

できるだけ濃度が高く、砂糖が溶け残っておらず(砂糖は100[g]当たりE [g]溶ける)、重さがF以下の砂糖水を作って砂糖水の重量とそれに溶けている砂糖の質量を求めろ。答えが複数ある場合はどれを答えても良い。

 

制約

  • 1≦A<B≦30
  • 1≦C<D≦30
  • 1≦E≦100
  • 100A≦F≦3,000
  • A,B,C,D,E,F はすべて整数である。

解法

制約より、操作1~3を行った回数で全探索する。なるべく濃度の高い砂糖水を作りたいので、操作1~3を行った回数が分かれば最適な操作4の回数が決まる。操作4を行う回数は合計の重量がFを超えない、かつは砂糖が溶け残らない回数だけ行えばいい。0[g]の砂糖水はダメなので(コンテスト中のclarificationより)濃度0%の砂糖水をつくるの場合もそれを作るときの砂糖水と砂糖の量を出力することに気をつける。

計算量は O(F/ 100A * F/100B * F/C )で A, B, C が1でFが3000だとしても 2.7 * 106で十分間に合う。

提出コード： http://arc083.contest.atcoder.jp/submissions/1601536

D - Restoring Road Network

問題

頂点nの都市があり、いくつかの都市の組は道路で双方向に結ばれている。全ての都市と道をグラフと考えたときにグラフは連結無向グラフとなっている。 n x nの表Aが与えられる。全てのAu,vについて、Au,vが都市uから都市vまでの最短経路になるようなグラフが存在するか調べよ。もし存在するならそのようなグラフの中で道路の長さの和が最小になるようなものについてその和を求めよ。存在しないなら-1を出力しろ。

制約

  • 1≦N≦300
  • i≠j のとき、1≦Ai,j=Aj,i≦109
  • Ai,i=0

解法

まずワーシャルフロイドで全てのu, vについてAu,vの長さの辺を張ったときのグラフで各点の間の最短経路がAu,vと等しいかチェック。

等しいなら所望のグラフは存在する。ただ全ての辺についてAu,vの辺を張ったグラフは存在する道路の長さの和が最小とは限らないので、全ての辺Eu,vについて、Eu,v == Eu,x + Ex, vとなるxが存在するかチェックする。 存在するならEu, vはなくても最短経路は変わらないので取る。

等しくないなら所望のグラフは存在しないので-1。

計算量はO(N3)。

提出コード：

Submission #1602625 - AtCoder Regular Contest 083 | AtCoder

まとめ

今年から社会人なのですが、お仕事慣れて余裕ができたので参加。

やっぱり問題解けると楽しい

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以降

まだ

Chokudai Contest002 解法

問題概要

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

コメント

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

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

コンテストページ

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

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

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

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

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

技術メモ..手順書

 

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