Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2458-6c7888cd
この記事にトラックバックする(FC2ブログユーザー)

SRM564 DIV1 MEDIUM - AlternateColors2 (この記事を編集する[管理者用])

Source

TopCoder SRM564 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

N個 (100000以下) のボールがあって,それぞれ赤・緑・青のどれかの色をしている.
 赤いボールがあれば赤いボールを1個捨てる
 緑色のボールがあれば緑色のボールを1個捨てる
 青いボールがあれば青いボールを1個捨てる
 以下繰り返し
としたとき,K番目に捨てられたボールが赤であった.
赤・緑・青のボールの数の分布としてありうるのは何通りあるかを求める問題.

解法

今何個目のボールを捨てたか,残ってるボールの種類はどれかを状態としてDPする.
O(色の種類 * N),または,O(2^色の種類数 * N).

本番では,K番目のボールが捨てられた時,残っているボールの種類数が1種類,2種類,3種類で場合分けした.
1種類,2種類の場合は,なくなったボールの種類が使われた個数でループを回して数えた.O(N).
がすぐO(1)にすることもできる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll solve1(ll n, ll k){
  if(k%3!=1) return 0;
  n -= k;
  return (n+2)*(n+1) / 2;
}

ll solve2(ll n, ll k){
  ll i, j, b;
  ll nn, kk;
  ll res = 0;
  
  for(b=0;;b++){
    nn = n - b*3;
    kk = k - b*3;
    if(nn < 0 || kk < 0) break;

    if(kk==1) continue;
    if(kk%2!=1) continue;

    nn -= kk;
    res += nn+1;
  }
  res *= 2;
  
  return res;
}

ll solve3(ll n, ll k){
  ll i, j, b, h;
  ll nn, kk;
  ll res = 0;

  for(b=0;;b++){
    h = k - b - 2;

    if(b > h*2) break;

    if(b <= h) res += b+1;
    else       res += 2*h-b+1;
  }

  return res;
}

class AlternateColors2 {
public:
ll countWays(int n, int k) {
  ll res1, res2, res3;
  res1 = solve1(n, k);
  res2 = solve2(n, k);
  res3 = solve3(n, k);
  printf("%lld %lld %lld\n",res1,res2,res3);
  return res1 + res2 + res3;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2458-6c7888cd
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。