問題はこちら
No.586 ダブルブッキング - yukicoder
各部屋について最初の1人で部屋を予約することにする。
2人目以降は振替により(P1+P2)円の損失が発生する。
a[1000],p1,p2,n,x,s; main(){ scanf("%d%d%d",&p1,&p2,&n); for(int i=0;i<n;i++){ scanf("%d",&x); if(a[x]==0){//まだ予約されてない部屋なら a[x]++;//確保する }else{//既に予約されている部屋なら s+=p1+p2;//損失が発生 } } printf("%d",s); }
ぎゅっとする。人数だけ数えて最後に掛け算をした方が短い
a[9999],k,s,x; main(i){ for(;~scanf("%d",&x);)i--<0?k+=i+2&&a[x]++:(s+=x); printf("%d",s*k); }
90B
問題はこちら
No.581 XOR - yukicoder
XORを表す演算子を^とする。XORの基本的な性質を確認する
・順序に依らない（可換かつ結合的）
・任意のXについてX^X=0
C=A^Bの両辺にAをXORすることでA^C=A^A^B=Bが得られる
long a,b;main(){scanf("%ld%ld",&a,&b);printf("%ld",a^b);}
57B
問題はこちら
No.555 世界史のレポート - yukicoder
DP解法との賢い数学解法がある
・DP解
N文字以上を作る最小コスト=min{ちょうどK文字を作る最小コスト|K≧N}
K文字を作る際には、その過程で必ずK/2文字以上の状態を経由するので、Kの上限は2Nとしてよい。
・もらうDP
ちょうどi文字を作るための最小コストをd[i]とする。d[1]=1。
ちょうどi文字を作るためには、最後にコピーを行う際の文字数kはiの約数でなければならない。
このときペーストはi/k-1回行われるので、コストはd[k]+C+(i/k-1)*Vとなる
約数列挙にO(√i)かかるので全体で、Σ√i=O(N√N)
・配るDP
上の解法を配るDPに書き換えるだけ
j≧2に対して、d[i*j]=min(d[i*j],d[i]+C+(j-1)*V)とすればよい
ΣN/i=O(NlogN)
n,c,v; dp[100010]; ans=1e9; main(){ scanf("%d%d%d",&n,&c,&v); for(int i=0;i<2*n+5;i++)dp[i]=1e9; dp[1]=0; for(int i=1;i<n;i++)for(int j=2;i*j<2*n;j++)dp[i*j]=fmin(dp[i*j],dp[i]+c+(j-1)*v); for(int i=n;i<2*n;i++)ans=fmin(ans,dp[i]); printf("%d",ans); }
・O(logN)の賢い解法
操作は「コピー、(ペースト)×a1、全体をコピー、(ペースト)×a2、全体をコピー、……」となる。
このときペーストの回数を順にaiとすれば、最終的な文字数はとなる。
各kに対して最小コストを考える。
の条件下で
を最小化する問題を考える。
kは固定しているので、これは結局
を最小化することと同じ。
以下1+aiをaiと改めて書く。
さて、相加相乗平均の関係から、Σaiの最小値はaiたちが等しい値をとるとき（∀i,j.|ai-aj|≦1)に達成される。
よって、aiたちはfloor(N^(1/k))及びそれ+1の値を、Πai≧Nとなるように取ればよいことがわかり、最小値はO(1)で求められる。
またai≧2よりΠai≧2^kなのでkはlog2(N)+1まで調べればよく、全体ではO(logN)で求める事ができる。
n,c,v; a,b,t; ans=1e9; main(){ scanf("%d%d%d",&n,&c,&v); for(int k=1;k<log2(n)+1;k++){ a=pow(n,1.0/k);//aiたちの小さい方の値 b=(log(n)-k*log(a))/(log(a+1)-log(a))+1-1e-9;//大きい方の個数 //+1-1e-9は切り上げのため t=(c-v)*k+v*(a*k+b); ans=fmin(ans,t); } printf("%d",ans); }
・発想の転換
実はdfsでも解ける
f(現在の文字数,クリップボードの文字数)=必要な残りコスト
という関数を考えると
n,c,v;
f(a,b){
if(a>=n)return 0;
return fmin(f(a+b,b)+v,f(a+a,a)+c+v);
}
main(){
scanf("%d%d%d",&n,&c,&v);
printf("%d",f(1,1)+c);
}
と書くことができる
最大ケースのN=50000でもfは168685291回≒1.6×10^8回しか呼び出されないらしく間に合う。
これをギュッとする
n,c,v;
f(a,b){
return a<n?fmin(f(a+b,b),f(a+a,a)+c)+v:c;
}
main(){
scanf("%d%d%d",&n,&c,&v);
printf("%d",f(1,1));
}
return文を省略
x,n,c,v;
f(a,b){
x=a<n?fmin(f(a+b,b),f(a+a,a)+c)+v:c;
}
main(){
scanf("%d%d%d",&n,&c,&v);
printf("%d",f(1,1));
}
105B
問題はこちら
No.566 だいたい完全二分木 - yukicoder
○激ヤバ解法
シャッフルすれば高確率で通る
○まじめな解法
普通に完全二分木をつくると高さはK-1になる。そこで適当にいじって高さをKにする
・方針1
完全二分木を作る過程で、2と3を入れ替える。
そうすると
2
／＼
1 3
の部分が
3
／
1
＼
2
または
3
／
2
／
1
となり高さが1増える。ほかの部分には影響がないのでこれにより全体の高さがKになる
・方針2
完全二分木を作る過程で、最大値2^K-1の代わりに0を入れる
そうすると
2
／＼
1 3
の部分が
2
／＼
1 3
／
0
となり高さが1増える。
登場する数が0～2^K-2になっているので、全体に1を加えることで1～2^K-1にする
○実装について
・DFSっぽいの
自分が最初に思いついたのはこれだった。
方針1を再帰で実装する
f(n,c){
printf("%d ",n!=2&&n!=3?n:5-n);
if(c>=0){
f(n-(1<<c),c-1);//左側
f(n+(1<<c),c-1);//右側
}
}
main(){
int k;
scanf("%d",&k);
f(1<<(k-1),k-2);
}
・BFSっぽいの
完全二分木を、根に近いほうから順に配っていく
例えばK=4なら、頂点が8、その次が4,12、次が2,6,10,14、…となる
初項が2^i、公差が2^(i+1)の等差数列をなしている
方針2を実装する
main(){
int k;
scanf("%d",&k);
for(int i=1<<(k-1);i;i/=2)for(int j=i;j<(1<<k);j+=i*2)printf("%d ",j);
}
・方針3
次の比較関数でソートする
c(int*a,int*b){ int ta=*a,tb=*b; while(ta%2==0)ta/=2; while(tb%2==0)tb/=2; return ta-tb; } a[5000]; main(){ int k; scanf("%d",&k); for(int i=0;i<(1<<k)-1;i++)a[i]=i+1; qsort(a,(1<<k)-1,4,c); for(int i=0;i<(1<<k)-1;i++)printf("%d ",a[i]); }
この解法はtailsさんの提出をC言語に書きなおしたものである
（なおこの提出はシャッフル解でないもののなかで最短）
少しわかりにくいが、このソートにより高さ2K-1の木が得られることがKに関する帰納法で示せる。
このソートにより出力は、1,2,4,…、3,6,12,…、5,10,20,…、…となる。
初項2*i-1、公比2の等比数列からなる群数列なので、単なる二重ループで書ける。
main(){
int k;
scanf("%d",&k);
for(int i=1;i<(1<<k);i+=2)for(int j=i;j<(1<<k);j*=2)printf("%d ",j);
}
これをちゃちゃっと縮める
j,k;main(i){for(k=1<<atoi(gets(&k));i<k;i+=2)for(j=i;j<k;j*=2)printf("%d ",j);}
79B
まだ縮む余地はありそう
問題はこちら
No.567 コンプリート - yukicoder
包除原理やるだけ（説明は後述）
main(n){
scanf("%d",&n);
printf("%.9f",
1
- 6*pow(5/6.,n)
+15*pow(4/6.,n)
-20*pow(3/6.,n)
+15*pow(2/6.,n)
- 6*pow(1/6.,n)
);
}
事象A1,…,A6を、
A1：1が出ない
…
A6：6が出ない
とおく。このとき、6種類が揃う確率は、余事象を考えて 1-P(A1∪A2∪A3∪A4∪A5∪A6)となる。
ところで明らかに
P(Ai)=(5/6)^n
P(Ai∩Aj)=(4/6)^n （i≠j）
……
であるから、包除原理より冒頭のプログラムの式が得られる
単に式を書き換えるよりも、for文で1つにまとめてしまった方が短くなった。
powの前についている係数は二項係数なので順次計算できることに注意して次のように書ける
double A; n,i; main(s){ for(scanf("%d",&n);++i<7;A+=pow(i/6.,n)*s)s=s*(i-7)/i; printf("%.9f",A); }
93B
