Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-18

[][] TopCoder Single Round Match 504.5 Div1 02:08 はてなブックマーク -  TopCoder Single Round Match 504.5 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:07:45.740Passed System Test233.07
5000:41:00.454Challenge Succeeded0.00
10000:25:54.023Opened0.00
Challenge..0.00

部屋(Room 37) 10位,全体 370位

Rating : 1420 → 1490 (+70)

 ノーコンテストとなった回の代替試合.Mediumが荒れた回でした.

自分の結果に関しては,Easyを解いた速さは比較的満足しています.Mediumは前回のSRMと同じく検証をさぼったのが原因です.950を解く時間の確保を優先したのが戦略ミスでした.

 同じ部屋だったuwiさんが部屋1位でレッドコーダーに昇格しました.おめでとうございます.

250 TheNumbersWithLuckyLastDigit

要約

 下1桁が4か7の数をLucky Numberと呼ぶ.与えられた数 n がLucky Numberのいくつかの和で書けるかを判定し,書ける場合は足すべきLucky Numberの数の最小値を答えよ.n は1以上10^{12}以下.

方針

 ある数が末尾が4 or 7で書けたとする.もし,末尾7が2つ以上あったら,2つをまとめて末尾4の数が作る事でLucky Numberの個数を減らせる.同様に,末尾4が6つ以上あったら,6つをまとめて末尾4を作れる.従って,末尾7が1以下,末尾4が6つ以下で書けるかを調べれば十分である.

 

コード例

 下のコードでは,調べるべき4, 7の個数に上限がある事がわかった段階で書き始めているので,上の個数の条件よりもっと緩い条件でチェックをしています.

#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class TheNumbersWithLuckyLastDigit {
public:
  int find(int n) {
    for(int i = 1; i < 10; i++){
      for(int j = 0; j <= i; j++){
	int k = i - j;
	if( ( j * 4 + k * 7 ) <= n && ( n - ( j * 4 + k * 7 ) ) % 10 == 0 ){
	  return i;
	}
      }
    }
    return -1;    		
  }
};

500 TheJackpotDivOne

要約

 賞金(問題の設定ではジャックポットで得た賞金)を何人かに分配する事を考える.それぞれの人物が予めいくらか持っている状態から初めて,次のアルゴリズムで分配する.

  • 所持金額が最も少ない人と,全員の平均持ち金を調べる.最も所持金が少ない人が複数いる場合は一人をランダムに選ぶ
  • 選んだ人がその平均より真に所持金が多くなるような金額のうち,最低の金額を与える.もし今残っている賞金全部を与えても平均を超えない場合は残っている賞金全てを与える
  • 最初に戻る

 それぞれの人物の最初の所持金と賞金額が与えられているので,分配後のそれぞれの持ち金を少ない順に答えよ.

 人物は1以上47以下,それぞれの最初の所持金は1以上10^{18}以下,分配すべき賞金は1以上10^{18}以下.

方針

 おそらく多くの人がはまったのは10^{18} * 47 がC言語での long long型の最大値を超えてしまう所で,JavaのBigIntegerなどの多倍長整数を用いるか,賞金を合計しないで平均を求める工夫が必要となる(自分もそこではまりました.Easy, HardはC++ だけどMediumはJavaで解いた人も少なくないようです).

 愚直に上のアルゴリズムを実装すると例えば最初の所持金が「1, 1, 1, ..., 1」で,賞金が10^{18}の時全員に1ずつ配るので,時間がかかりすぎてしまう.実験してみると,「賞金を分配されてもその時点での最高所持金額を超える事は滅多になく,唯一の例外は全員が同じ所持金の時」だと気づく,そこで,全員が等しい金額になった時点で愚直なシミュレーションは終了させ,残り賞金を全員に等しく分配する.

コード例
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>

using namespace std;

typedef long long ll;

void add(long long& a, long long& div, long long& res, int n){
  div += a / n;
  res += a % n;
  if(res >= n){
    div ++;
    res -= n;
  }
}


class TheJackpotDivOne {
public:
  vector<long long> find(vector<long long> money, long long jackpot) {
    sort(money.begin(), money.end());
    int n = money.size();

    long long div = 0;
    long long res = 0;
    for(int i = 0; i < n; i++){
      add(money[i], div, res, n);
    }

    while(true){
      sort(money.begin(), money.end());
      if(money[0] == money[n-1])
	break;
      long long toadd = div - money[0] + 1;
      if(toadd < jackpot){
	money[0] += toadd;
	add(toadd, div, res, n);
	jackpot -= toadd;
      }else{
	money[0] += jackpot;
	add(jackpot, div, res, n);
	jackpot = 0;
	break;
      }
    }

    if(jackpot > 0LL){
      for(int i = 0; i < n; i++){
	money[i] += jackpot / n;
      }
      for(int i = 0; i < jackpot % n; i++){
	money[i]++;
      }
    }
    sort(money.begin(), money.end());

    return money;
  }
};

分析

 さらに,実験してみると「所持金の平均を超えている場合,0ドルを分配することを認めるならば,最初の所持金でソートした順番に賞金を分配すれば良い.」ではないかと思えます.例えば3人で次の状況を分配を考えます.

 1 10 100 合計:111 平均:37 残り:1000

実際に分配をシミュレーションすると次のようになります."↓"で分配の対象者を表します.

+36
 ↓
 1 10 100 合計:111 平均:37 残り:889
  +40
   ↓
37 10 100 合計:147 平均:49 残り:853
      +0
      ↓
37 50 100 合計:187 平均:62.3 残り:813
+26     
↓
37 50 100 合計:213 平均:62.3 残り:787
   +30     
   ↓
63 50 100 合計:239 平均:79.7 残り:761
      +0     
      ↓
63 80 100 合計:269 平均:89.7 残り:731

 0ドルの分配を認めると分配する順序は固定でき,ソートは最初と最後の1回だけで済みます.しかしこれは正しくありません.例えばSystemTestの32番目のケースでWAが返ります.このケースではそれぞれの最初の所持金は下表で与えられています.

0 253920995999951
1 261383280458054
2 261545796441447
3 397444942952159
4 465814620334968
5 587311923572791
6 702036475565943
7 717992419066752
8 841420261437928
9 1614524952743456
10 1792721361613253
11 1910098303151592
12 2033401256024203
13 2381930372824776
14 2570801733635568
15 2636621002405360
16 2769284722688042
17 3061319632203626
18 3510300900946779
19 3785566194359680
20 3959115359315863
21 4095236657946954
22 4186161583065095
23 4447594013543674
24 4552237338111802
25 4752335916103198
26 5054951605072076
27 5343906371941975
28 6003645665166311
29 6162160424226647
30 6522998483383946
31 6618583125545910
32 6875217911724384
33 7020268774332648
34 7127085084630247
35 7279578350263002
36 7528796737878623
37 7614318298451338
38 7976532560692712
39 8670405223633845
40 8692060070929655
41 8701760179526288
42 9189183095957703
43 9390074325157675
44 9404232225801752
45 9499193164241496
46 9640179505824800

一巡目,最初の25人に分配をすると

0 4656664961721191
1 4750340365247175
2 4845850090455454
3 4943388479689794
4 5040110682599106
5 5137436130732385
6 5234247284076207
7 5330677301278553
8 5428819532814974
9 5526423772631507
10 5609655662416359
11 5690867030518553
12 5771308918334871
13 5850838868596800
14 5924645432336630
15 5996003808904738
16 6067480038830257
17 6137654407258815
18 6203108338642967
19 6260402113913099
20 6313058197307853
21 6363142087477895
22 6411395394489192
23 6458740794732258
24 6501531151778823 <- ここまで分配した
25 4752335916103198
26 5054951605072076
27 5343906371941975
28 6003645665166311
29 6162160424226647
30 6522998483383946
31 6618583125545910
32 6875217911724384
33 7020268774332648
34 7127085084630247
35 7279578350263002
36 7528796737878623
37 7614318298451338
38 7976532560692712
39 8670405223633845
40 8692060070929655
41 8701760179526288
42 9189183095957703
43 9390074325157675
44 9404232225801752
45 9499193164241496
46 9640179505824800

すると,0人目(4656664961721191)と25人目(4752335916103198)では1人目の方が所持金が少ないので,0人目が分配の対象となります.