読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 3/4/5

GWのうちに問題数を稼ぐ

- 3 ビットすごろく

  • 問題概要

10進数kを2進数に変換したとき,ビットが1になっている部分の個数をbit(k)とする。
頂点kからはk-bit(k),k+bit(k)に移動することができる。
1からNに移動するときの最短距離を求めてくださいという問題です。
ちなみに1未満N+1以上の頂点には移動することができない。

  • 解説

グラフの辺の張り方は問題制約そのままでいいです。
移動コストが1なので幅優先探索で解が求められます。
既訪問チェックリストとなる配列に最短距離を書き込んでいくのが定石でしょうか。

またもや直打ちコードです。

#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
int bit[10001];
int dist[100001];
inline int countbit(int n){
int cnt=0;
while(n){
if(n&1)cnt++;
n>>=1;
}
return cnt;
}


int main(void){
int N;
cin>>N;
for(int i=0;i<=N;i++){bit[i]=countbit(i);dist[i]=-1;}
queue<int> que;
dist[1]=1;
que.push(1);
while(que.empty()==false){
int v=que.front();que.pop();
if(v-bit[v]>0&&dist[v-bit[v]]==-1){
dist[v-bit[v]]=dist[v]+1;
que.push(v-bit[v]);
}
if(v+bit[v]<=N&&dist[v+bit[v]]==-1){
dist[v+bit[v]]=dist[v]+1;
que.push(v+bit[v]);
}

}
cout<<dist[N]<<endl;
return 0;
}

- 4 おもりと天秤

  • 問題概要

与えられたN個のおもりを全部使って天秤を水平にできるかどうか判定する問題です。

  • 解説

まず水平にするためには全てのおもりの合計が偶数にならなくてはいけません。
合計が偶数のときちょうど合計がその半分になるようなおもりの組み合わせの選び方が存在すれば水平にできます。
したがっておもりの合計の半分の重さを作れるかどうかのナップサック問題に帰着できます。

これも直打ちコードです

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


bool dp[10000];
int main(void){
int N,w[100];

int sum=0;
cin>>N;
for(int i=0;i<N;i++){
cin>>w[i];
sum+=w[i];
}
if(sum&1){
cout<<"impossible"<<endl;
return 0;
}
int m=sum/2;
dp[0]=true;
for(int i=0;i<N;i++)
for(int j=m;j>=w[i];j--)
dp[j]|=dp[j-w[i]];

if(dp[m])cout<<"possible"<<endl;
else cout<<"impossible"<<endl;
return 0;
}

- 5 数字のブロック

  • 問題概要

縦1,横Wの箱がある。
N個の縦1、横[tex;w_i]のブロックがある。
箱の中に最大何個のブロックが入るか答える問題です。

  • 解説

小さい箱から詰めていくのが最大です。
したがってブロックをソートして貪欲法で詰めていくだけ。

直うち三連発です。
#include
#include
using namespace std;
int main(void){
int N,L;
int w[10000];
cin>>L>>N;
for(int i=0;i>w[i];
sort(w,w+N);
int sum=0;
int cnt=0;
for(int i=0;i