スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #115

2012/04/14
Codeforces Round #115

Tags : プログラミング Codeforces 未解決

問題

問題セットの原文はここを参照。

A. Robot Bicorn Attack

三つの数字が連結された文字列が与えられる。
三つの数字それぞれは leading zero を含まない 0 以上 10^6 以下の整数であることがわかっている。
ありうる三つの数字の和の最大値を求めよ。
復元不可能なら -1。

B. Plane of Tanks: Pro

n 人の人とそれぞれが取った得点が与えられる。
それぞれの人に対して、その人が全体の何% ( 得点の高い順 ) の位置に属しているかを判定し、その結果によって noob, random, average, hardcore, pro を割り当てよ。

同じ人が複数入力されることがありえて、その場合は最高得点のみに注目すること。

C. Geometry Horse

n 種類の的がある。
的を壊すことで点数が得られる。
種類 i の的は k[i] 個あり、パラメータ c[i] が割り当てられている。

点数計算には factor という値がからんでいて、最初は factor = 1 である。
factor は一定個数の的を壊すたびに 1 ずつ増えていく。最大 t+1 まで増える。
factor == i のとき、累計 p[i] 個の的を壊せば factor の値が 1 増える。

的 i を 1 つ壊すと factor × c[i] 点が得られる。
最適な順で的を壊すことで、合計得点を最大化せよ。

1 ≦ n, t ≦ 100
1 ≦ k[i] ≦ 10^9
0 ≦ c[i] ≦ 10^3
1 ≦ p[1] < p[2] < ... < p[t] ≦ 10^12

解答

A.
全部の切り方を試す。
http://www.codeforces.com/contest/175/submission/1532294

B.
問題文どおりに割り当てればいい。
http://www.codeforces.com/contest/175/submission/1533391

C.
c[i] の低い的から優先的に壊すのがいい。
というのも、後になるほど factor が大きくなって、それに比例して的一つ当たりの点数も上がるから。
けっこうスマートに書けた。
http://www.codeforces.com/contest/175/submission/1534279

D.
状態がループする DP。
普通にやると収束するまで時間がかかりすぎるから、行列べき乗とかでやりたくて、遷移行列の matrix power series が求められればできそう、とか思って泥沼なコードを書いていた。 ( そもそも正しいかどうかすらあやしい )
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。