2012-10-27

PKU3104 Drying

PKU

問題はこちら　3104 -- Drying．

k = 1 のときは自然乾燥と同じなので，a₀ 〜 a_n-1 の中で最大のものが答えになる．

k > 1 のときは，全部の服を乾かすのに必要な最小時間を二分探索で求める．

a_i を x 分で0にするのに必要な，乾燥機の使用時間を t_i とおく．
乾燥機によって減らされる水分量は k ・ t_i ．
自然乾燥で減る水分量は x - t_i ．
この2つの和が a_i 以上であれば良いので　k ・ t_i + x - t_i >= a_i ．
これより　t_i >= (a_i - x) / (k - 1)　が得られる．

次に，a₀ 〜 a_n-1 全部を x 分で乾かすための条件を考える．
乾燥機は1度に1つの服しか乾かせないので全部の服を x 分で乾かすための乾燥機の使用時間は，合計で t₀ + t₁ + … + t_n-1 分になる．
これが x 以下であれば全部の服を x 分で乾かすことができる．

具体例 a = { 6, 13, 17 } , k = 5 でみてみる．
x = 10 のとき
t₀ = 0
t₁ = 1
t₂ = 2

余裕で間に合う．

x = 5 のとき
t₀ = 1
t₁ = 2
t₂ = 3

それぞれを5分で乾かそうとすると，乾燥機を6分使うことになるから無理．

#include <cstdio>
#include <algorithm>
using namespace std;
int a[100010],n,k;
bool ok(int x)
{
    long long sum=0;
    for (int i=0;i<n;++i) if (a[i]>=x) {
        int t=(a[i]-x+k-2)/(k-1);
        sum+=t;
    }
    return sum<=x;
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;++i) scanf("%d",a+i);
    scanf("%d",&k);

    if (k==1) { printf("%d\n",*max_element(a,a+n)); return 0; }

    int L=0,R=1000000000;
    while (L<=R) {
        int M=(L+R)/2;
        if (ok(M)) R=M-1;
        else L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

2012-10-19

SRM558 DIV1 275 Stamp

SRM

スタンプの長さ（L = 1 〜 desiredColor.size()）と、最初に何色で塗るか（3通り）を全通り試す。

int n=desiredColor.size();
int res=inf;
for(int L=1;L<=n;++L) {
    for(int c=1;c<=3;++c) { // R=1, G=2, B=3
        res=min(res, L*stampCost + (長さL、最初にcで塗ったときの最小push回数)*pushCost);
    }
}

最小push回数を求める部分は、
・重ね塗りできるのは同じ色だけ
・まだ塗っていないところは何色でもいい
・ボードからスタンプがはみ出してはいけない
というルールに気をつけて左から右に塗っていく感じでメモ化全探索。

#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;

int a[51],n;
ll memo[4][51];
const ll inf=(1LL<<40);
class Stamp {
    // 長さLのスタンプでk〜k+L-1番目のセルを色cで塗った場合、
    // k番目以降をdesiredColorに合わせるための最小push回数
    ll func(int L, int c, int k)
    {
        // はみ出しちゃダメ
        if (k+L>n) return inf;
        // desiredColorじゃない色で塗っちゃダメ
        rep(i,L) if (a[k+i] && a[k+i]!=c) return inf;
        // 最後まで塗れたらOK
        if (k+L==n) return 1;

        ll& res=memo[c][k];
        if (res) return res;
        res=inf;
        // [k+1,k+L)の範囲はcと同じ色でしか塗れない
        REP(i,1,L) res=min(res,func(L,c,k+i)+1);
        // まだ塗っていないセルは何色で塗ってもいい
        REP(i,1,4) res=min(res,func(L,i,k+L)+1);
        return res;
    }
    public:
    int getMinimumCost(string desiredColor, int stampCost, int pushCost)
    {
        ll res=inf;
        n=desiredColor.size();
        rep(i,n)switch(desiredColor[i]){
            case 'R': a[i]=1; break;
            case 'G': a[i]=2; break;
            case 'B': a[i]=3; break;
            default: a[i]=0;
        }
        // スタンプの長さ、最初に何色で塗るかを全探索
        REP(L,1,n+1) REP(c,1,4) {
            memset(memo,0,sizeof(memo));
            res=min(res,L*stampCost+func(L,c,0)*pushCost);
        }
        return int(res);
    }
};

2012-10-16

CodeChef October Challenge 2012 "Need More Diamonds"

CodeChef

問題はこちら　Contest Page | CodeChef

最初にやったこと（愚直DP解　TLE）

与えられた配列 $V$ の、 $[\ell,r)$ の範囲が残った状態で先手の番が来たとき、
それ以降の先手が獲得するスコアの期待値を $f(\ell, r)$ とおく。

（１）先手が左端（ $V_\ell$ ）を取る場合
　　後手は $V_{\ell+1}$ か $V_{r-1}$ のどちらかを取るので、
　　次に先手の番が来るときの $V$ の状態は以下の2通りになる。
　　　・ $V_{\ell+2}\:, \;\; \dots, \;\; V_{r-2}\:, \;V_{r-1}$ 　（後手が $V_{\ell+1}$ をとった場合　 $[\ell+2,\:r)$ が残った状態で先手の番になる）
　　　・ $V_{\ell+1}\:, \;V_{\ell+2}\;,\;\; \dots, \;\; V_{r-2}$ 　（後手が $V_{r-1}$ をとった場合　 $[\ell,\:r-1)$ が残った状態で先手の番になる）
　　このどちらかが1/2の確率で起こるので、これ以降の期待値は
　　　　 $V_{\ell}\;+\;\frac{1}{2}\:(f(\ell+2,\:r)\;+\;f(\ell+1,\;r-1)\:) \mbox{ (eq. 1)}$
　　と書ける。

（２）先手が右端（ $V_{r-1}$ ）を取る場合
　　（１）と同様に
　　　　 $V_{r-1}\;+\;\frac{1}{2}\:(f(\ell,\:r-2)\;+\;f(\ell+1,\;r-1)\:) \mbox{ (eq. 2)}$
　　となる。

（１）、（２）はそれぞれ1/2の確率で起こるので、
　　　　 $f(\ell,\:r)\;=\;\frac{1}{2}\:(\mbox{ (eq. 1)}\;+\mbox{ (eq. 2)}\:)$
　　　　 $\quad\quad\quad=\;\frac{1}{2}\:(V_\ell\:+\:V_{r-1}\:+\:f(\ell+1,\:r-1)\:+\:\frac{1}{2}\:(\:f(\ell+2,\:r)\:+\:f(\ell,\:r-2)\:)\:)$
となる。

#include <cstdio>
double memo[2010][2010];
int v[2010];
double func(int l, int r)
{
    if (r-l<=0) return 0;    // 1つも残っていない
    if (r-l==1) return v[l]; // v[l] (==v[r-1]) だけが残っている
    double& res=memo[l][r];
    if (res>-0.5) return res;
    return res=0.5*(v[l]+v[r-1]+func(l+1,r-1)+0.5*(func(l+2,r)+func(l,r-2)));
}
int main()
{
    int T; scanf("%d",&T);
    while (T--) {
        int n; scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",v+i);
        for(int i=0;i<=n+1;++i) for(int j=0;j<=n+1;++j) memo[i][j]=-1;
        printf("%.3f\n",func(1,n+1));
    }
    return 0;
}

計算量はたぶんO(T*N*N)。
1<=T<=500 , 1<=N<=2000 なので最大で 500 * 2000 * 2000 = 2 * 10^9 。
これじゃさすがにCodeChefじゃなくても余裕でTLEっぽいのでボツ。

次にやったこと（数列観察ゲー　Accepted）
少々ややこしいので具体例で説明。
例えばN=4のとき、ゲームの進み方は以下の8通りがある。

この中で先手が取るもの（図で色がついている部分）の、1〜4それぞれの出現回数を並べると
　　5, 3, 3, 5　（1が5個、2が3個、3が3個、4が5個）
という数列が得られる。

で、これを使って
　　 $(V_1\,\times\,5\:+\:V_2\,\times\,3\:+\:V_3\,\times\,3\:+\:V_4\,\times\,5)\:/\:(5+3+3+5)$
とでもすれば答えになるんじゃね？と思ってN=1〜3についても同様に数列を作ってサンプルを計算してみた。
100.000　(正解 100.000）
21.000　（正解 21.000）
4.250　（正解 9.500）
5.000　（正解 10.000）
…合わない。N=3とN=4のときは2倍しないと合わない。

この2ってなんだ？
1ゲームあたりの先手の手数（上の図でいうと色のついている列数）っぽいな。
よし、そういうことにしよう。

ということで
・与えられた数列 $V$ の要素数を $n$
・上述の手順で得られる数列を $\{A_n\}$
・ $\{A_n\}$ の $i$ 番目の要素を $A_{n,\,i}$
・数列 $\{A_n\}$ の総和を $S_n$
・1ゲームあたりの先手の手数を $H_n$
とおくと、

　　　 $\sum_{i=1}^{n}\,V_i\,\times\,A_{n,\,i}\,/\,S_n\,\times\,H_n \mbox{ (eq. 3)}$

が求めるべき答えになりそう（なんかしらんけど）。
（実際これが正解だった。なんかしらんけど。）

$H_n$ は (n+1)/2 で計算できるので、あとは $\{A_n\}$ が求められればOK。
とりあえず 1<=n<=10 のときを列挙してみる。

// {An}を求める
#include <vector>
#include <set>
#include <cstdio>
#include <cstdlib>
using namespace std;
void func(set<vector<int> >& s, vector<int> v, int l, int r)
{
    if (r-l<1) return;
    if (r-l==1) { v.push_back(l+1); s.insert(v); return ;}
    v.push_back(l+1);
    func(s, v, l+1, r);
    v[v.size()-1]=r;
    func(s, v, l, r-1);
}
int main(int argc, char** argv)
{
    int N=atoi(argv[1]);
    for(int n=1;n<=N;++n) {
        set<vector<int> > s;
        vector<int> v;
        func(s,v,0,n);
        vector<int> c(n+1);
        for(typeof(s.begin())i=s.begin();i!=s.end();++i){
            vector<int> t=*i;
            for(int j=0;j<t.size();++j) if(j%2==0) c[t[j]]++;
        }
        printf("%2d:\t",n);
        for(int i=1;i<=n;++i)printf("%4d ",c[i]);
        puts("");
    }
    return 0;
}

これからパスカルの三角形っぽく計算出来ないものかと規則性をさがす。

みつからない。一日中眺めててもなにも見つからない。

ということで先手だけじゃなくて後手についても $\{A_n\}$ と同様の数列（ $\{B_n\}$ とする）を作って並べてみる。

サクッと発見。こんなかんじ。

　　　 $\large\left\{\begin{array}{ccll}A_{1,1}&=&1&\\ B_{1,1}&=&0&\\ A_{n,1}&=&A_{n,n}=A_{n-1,1}\:+\:2B_{n-1,1}&\quad(n\,>\,1)\\B_{n,1}&=&B_{n,n}=A_{n-1,1}&\quad(n\,>\,1)\mbox{ (eq. 4)}\\A_{n,j}&=&B_{n,j-1}\:+\:B_{n,j}&\quad(n\,>\,1\:,\:j\,>\,1)\\B_{n,j}&=&A_{n,j-1}\:+\:A_{n,j}&\quad(n\,>\,1\:,\:j\,>\,1)\end{array}$

    int A[2010][2010],B[2010][2010];
    A[1][1]=1;
    B[1][1]=0;
    for(int i=2;i<=2000;++i) {
        A[i][1]=A[i][i]=A[i-1][1]+2*B[i-1][1];
        B[i][1]=B[i][i]=A[i-1][1];
        for(int j=2;j<i;++j) {
            A[i][j]=B[i-1][j-1]+B[i-1][j];
            B[i][j]=A[i-1][j-1]+A[i-1][j];
        }
    }

これで解ける・・・わけない。こんなもんあっさりオーバーフローするわ。
ここでちょっと $S_n$ をよく見てみたら
　　　　 $S_n\;=\;2^{n-1}\:\times\;H_n\mbox{ (eq. 5)}$
になってるのを発見（なんかしらんけど）。これを使うと (eq. 3) は

　　　　 $\sum_{i=1}^{n}\,V_i\,\times\,A_{n,\,i}\,/\,2^{n-1} \mbox{ (eq. 6)}$

とすっきりした形になる。
$P_{n,\,i}\:=\:A_{n,\,i}\:/\:2^{n-1}\quad,\quad Q_{n,\,i}\:=\:B_{n,\,i}\:/\:2^{n-1}$ とおくと、(eq. 4) をまるごと $2^{n-1}$ で割って

　　　　 $\large\left\{\begin{array}{ccll}P_{1,1}&=&1&\\ Q_{1,1}&=&0&\\ P_{n,1}&=&P_{n,n}=\frac{1}{2}P_{n-1,1}\:+\:Q_{n-1,1}&\quad(n\,>\,1)\\Q_{n,1}&=&Q_{n,n}=\frac{1}{2}P_{n-1,1}&\quad(n\,>\,1)\mbox{ (eq. 7)}\\P_{n,j}&=&\frac{1}{2}$Q_{n,j-1}\:+\:Q_{n,j}$&\quad(n\,>\,1\:,\:j\,>\,1)\\Q_{n,j}&=&\frac{1}{2}$P_{n,j-1}\:+\:P_{n,j}$&\quad(n\,>\,1\:,\:j\,>\,1)\end{array}$

が得られる。また、 (eq. 6) は

　　　　 $\sum_{i=1}^{n}\,V_i\,\times\,P_{n,\,i}$

となる。これでオーバーフローせずに答えが求められる。めでたしめでたし。

// 計算量は O(N*N + T*N) かな
#include <cstdio>
#include <cstdlib>
#include <cstring>
double P[2010][2010],Q[2010][2010];
int main()
{
	P[1][0]=1;
	Q[1][0]=0;
	for(int i=2;i<=2000;++i) {
		P[i][0]=P[i][i-1]=0.5*P[i-1][0]+Q[i-1][0];
		Q[i][0]=Q[i][i-1]=0.5*P[i-1][0];
		for(int j=1;j<i-1;++j) {
			P[i][j]=0.5*(Q[i-1][j-1]+Q[i-1][j]);
			Q[i][j]=0.5*(P[i-1][j-1]+P[i-1][j]);
		}
	}
	int T; scanf("%d",&T);
	while (T--) {
		int n; scanf("%d",&n);
		double res=0;
		for(int i=0;i<n;++i){
			int v; scanf("%d",&v);
			res+=v*P[n][i];
		}
		printf("%.6f\n",res);
	}
	return 0;
}

2012-10-10

SRM557 DIV1 250 FoxAndMountainEasy

SRM

nからhistory.size()を引いた残りでどう動けばいいかを決める。
重要なのは、U,Dの個数さえ決まってしまえば順番がどうであろうと結果は一緒ということ。
ただしh[i]が負の数になってはいけない。
h[i]が負にならないためにはUをh[0]側に寄せればいい。

m = n - history.size() とすると、長さmのsequenceで移動できるのは

m, -m+2, -m+4, ... , m-2, m 。

（例えば m = 4 のとき
　DDDD：-4
　UDDD：-2
　UUDD： 0
　UUUD：+2
　UUUU：+4
）

この範囲で全探索をして条件をみたすものがあればYES、なければNOを返す。

#include <string>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, n)
using namespace std;

class FoxAndMountainEasy {
    public:
    string possible(int N, int h0, int hn, string history)
    {
        int n=history.size();
        int dh=0;
        rep(i,n) dh+=history[i]=='U'?1:-1;
        int m=N-n;
        for(int i=-m,d=m,u=0;i<=m;i+=2,d--,u++) if(h0+i+dh==hn) {
            for(int j=0;j+n<=N;j++) {
                bool ok=true;
                int h=h0+min(u,j);
                if (h<0) ok=false;
                for(int k=0;k<n;++k) { 
                    h+=history[k]=='U'?1:-1;
                    if (h<0) ok=false;
                }
                if (ok) return "YES";
            }
        }
        return "NO";
    }
};

2012-10-08

Codeforces Round #143 A. Team

Codeforces

問題文に書いてあるとおりにコードを書けばOK。
「1」が2個以上ある行数を返す。

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

using namespace std;

int main()
{
	int n;
	while (cin>>n) {
		int res=0;
		rep(i,n) {
			int a,b,c;
			cin>>a>>b>>c;
			if (a+b+c>=2) res++;
		}
		cout<<res<<endl;
	}
	return 0;
}

2012-10-08

Codeforces Round #143 B. Magic, Wizardry and Wonders

Codeforces

なかなか解法が思いつかなかったのでとりあえず要素数5の場合を紙の上でシミュレーションしてみた。

与えられた数列を a0, a1, a2, a3, a4　とすると
　1手目　a0, a1, a2, (a3-a4)
　2手目　a0, a1, (a2-(a3-a4))
　3手目　a0, (a1-(a2-(a3-a4)))
　4手目　(a0-(a1-(a2-(a3-a4))))
最終的にこんなかんじになる。カッコとはずすと

　a0 - a1 + a2 - a3 + a4　=　(a0 + a2 + a4) - (a1 + a3)

と書ける。これから

　（奇数番目の項の和）-（偶数番目の項の和）= d

となればいいとわかる。
奇数項の和を x , 偶数項の和を y とおくと、
　x - y = d
とかける。また元の配列の各要素は1以上l以下なので、奇数項の個数をp、偶数項の個数をqとおくと、
　p <= x <= l*p
　q <= y <= l*q →　q <= (x-d) <= l*q
となる。この２つの式を満たすようなxを全探索で求める。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,d,l;
    cin>>n>>d>>l;
    int p=(n+1)/2;
    int q=n-p;
    vector<int> odd(p), even(q);
    for(int x=p; x<=l*p; ++x) {
        int y=x-d;
        if(q<=y && y<=l*q) {
            // 奇数番目の項の和がx, 偶数番目の項の和がyになるような配列を作る
            int i=0;
            while(x>0) { odd[i%p]++; i++; x--; }
            i=0;
            while(y>0) { even[i%q]++; i++; y--; }
            break;
        }
    }
    if (odd[0]==0) { cout<<-1<<endl; return 0; }
    for(int i=0;i<n;++i) {
        if(i%2==0) cout<<odd[i/2]<<' ';
        else cout<<even[i/2]<<' ';
    }
    cout<<endl;
    return 0;
}

2012-10-03

SRM428 DIV2 250 ThePalindrome

SRM

sの先頭からi文字をひっくり返したものをtとする。
sの末尾にtをつけたものが回文になってるかどうかを試していく。

例えば、s="abcccc" の場合
i=0：
　t="" （空文字列）
　s+t="abccc" ←回文じゃない
i=1:
　t="a"
　s+t="abccca"　←回文じゃない
i=2:
　t="ba"
　s+t="abcccba"　←回文！これの長さを返す

#include <string>
#include <algorithm>
using namespace std;

class ThePalindrome {
	bool ok(const string& s)
	{
		int n=s.size();
		for(int i=0;i<n/2;++i) if (s[i]!=s[n-i-1]) return false;
		return true;
	}
	public:
	int find(string s)
	{
		for(int i=0;i<s.size();++i) {
			string t=s.substr(0,i); 　　// 先頭からi文字を取り出して
			reverse(t.begin(),t.end()); // ひっくり返して
			t=s+t;                      // sの末尾にくっつける
			if (ok(t)) return t.size();
		}
		return 0;
	}
};