0521 Change
釣銭枚数を計算する問題。
解法
書くだけです。
#include<stdio.h>
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
n=1000-n;
printf("%d\n",n/500+(n%500)/100+(n%100)/50+(n%50)/10+(n%10)/5+(n%5));
}
}
0522 JOI and IOI
解法
文字列を前から見てカウントするだけです。
この問題では単語が短いので手抜きします。
#include <stdio.h>
int main(){
char text[10001];
while(scanf("%s",text)!=EOF){
int ioi=0,joi=0;
for(int i=0;text[i+2]!='\0';i++){
if(text[i+1]=='O' && text[i+2]=='I'){
if(text[i]=='J')joi++;
if(text[i]=='I')ioi++;
}
}
printf("%d\n%d\n",joi,ioi);
}
}
0523 Card Game
解法
計算量が低いうえおそらくNP困難問題なので愚直に実装します。
もしNが大きくなった場合どうするか、少し考えつきません。
#include <stdio.h>
#include <string.h>
void calc(int n){
int nowCard;
bool cards[2][201];
memset(cards[0],false,201);
memset(cards[1],true,201);
for(int i=0;i<n;i++){
scanf("%d",&nowCard);
cards[0][nowCard]=true;
cards[1][nowCard]=false;
}
int p,pturn=0,ans[2];
ans[0]=ans[1]=n;
while(1){
p=1;
while(p<=2*n){
if(cards[pturn][p]){
cards[pturn][p]=false;
p++;
ans[pturn]--;
if(ans[pturn]==0)break;
pturn=(pturn+1)%2;
}else{
p++;
}
}
if(ans[pturn]==0)break;
pturn=(pturn+1)%2;
}
printf("%d\n%d\n",ans[1],ans[0]);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
0524 Searching Constellation
解法
一つずつ平行移動して重なるかチェックします。
星のポイントが整数であることを利用し、星の座標をsetに入れておくことで計算量をmlog(m)に下げます。
#include<stdio.h>
#include<set>
struct point{
int x,y;
bool operator<(const point p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
};
void search(int m){
point p;
int xs[201],ys[201];
for(int i=0;i<m;i++){
scanf("%d %d",&xs[i],&ys[i]);
}
int n;
scanf("%d",&n);
std::set<point> allPs;
std::set<point>::iterator it;
for(int i=0;i<n;i++){
scanf("%d %d",&p.x,&p.y);
allPs.insert(p);
}
it=allPs.begin();
bool allOK;
int sx,sy;
while(it!=allPs.end()){
sx=(*it).x-xs[0];
sy=(*it).y-ys[0];
allOK=true;
for(int i=0;i<m;i++){
p.x=sx+xs[i];
p.y=sy+ys[i];
if(allPs.find(p)==allPs.end()){
allOK=false;
break;
}
}
if(allOK==true){
printf("%d %d\n",sx,sy);
return;
}
it++;
}
}
int main(){
int m;
while(1){
scanf("%d",&m);
if(m==0) break;
search(m);
}
}
0525 Osenbei
解法
横列の裏返しは2^10通りしかなく、一度横列の裏表が決まれば最大化する方法は一通りしかないことを利用して解きます。
高速化する方法があるようですが私には思いつきませんでした。
#include<stdio.h>
#include<string.h>
int map[11][10001];
int remap[11][10001];
int ans;
int c,r;
void saiki(int deep){
if(deep==r){
int count=0,temp;
for(int x=0;x<c;x++){
temp=0;
for(int y=0;y<r;y++){
temp+=remap[y][x];
}
temp=temp>r-temp?temp:r-temp;
count+=temp;
}
ans=ans>count?ans:count;
}else{
memcpy(remap[deep],map[deep],4*10001);
saiki(deep+1);
for(int x=0;x<c;x++)remap[deep][x]=(map[deep][x]+1)%2;
saiki(deep+1);
}
}
void calc(){
ans=0;
for(int y=0;y<r;y++){
for(int x=0;x<c;x++){
scanf("%d",&map[y][x]);
}
}
saiki(0);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d %d",&r,&c);
if(c==0 && r==0) break;
calc();
}
}
0526 Boat Travel
#include<stdio.h>
const int size=101;
const int max=100000000;
int cost[size][size];
int n,k;
void costUpData(int c,int d,int e){
if(cost[c][d]<=e)return;
int sum,sum2;
cost[c][d]=cost[d][c]=e;
for(int s=1;s<=n;s++){
for(int g=1;g<=n;g++){
sum=cost[s][c]+e+cost[d][g];
if(sum<cost[s][g]) cost[s][g]=cost[g][s]=sum;
sum=cost[s][d]+e+cost[c][g];
if(sum<cost[s][g]) cost[s][g]=cost[g][s]=sum;
}
}
}
void calc(){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
cost[i][j]=max;
if(i==j)cost[i][j]=0;
}
}
int a,b,type,c,d,e;
for(int i=0;i<k;i++){
scanf("%d",&type);
if(type==0){
scanf("%d %d",&a,&b);
printf("%d\n",cost[a][b]==max?-1:cost[a][b]);
}else{
scanf("%d %d %d",&c,&d,&e);
costUpData(c,d,e);
}
}
}
int main(){
while(1){
scanf("%d %d",&n,&k);
if(n==0 &&k==0) break;
calc();
}
}
0527 Setting Go Stones
碁石の置き換え問題。
解法
連続して同色の碁石が並んでいる部分を塊で扱います。
#include<stdio.h>
#include<vector>
struct stone{
int count,color;
};
void calc(int n){
std::vector<stone> stones;
stone s;
int color,last;
for(int i=1;i<=n;i++){
scanf("%d",&s.color);
s.count=1;
last=stones.size()-1;
if(i%2==1){
if(stones.empty()){
stones.push_back(s);
}else if(stones[last].color==s.color){
stones[last].count++;
}else{
stones.push_back(s);
}
}else{
color=stones[last].color;
if(color==s.color){
stones[last].count++;
}else{
s=stones[last];
stones.pop_back();
if(stones.empty()){
s.color=(s.color+1)%2;
s.count++;
stones.push_back(s);
}else{
stones[last-1].count+=s.count+1;
}
}
}
}
int ans=0;
for(int i=0;i<stones.size();i++){
if(stones[i].color==0)ans+=stones[i].count;
}
printf("%d\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
calc(n);
}
}
0528 Common Sub-String
#include<stdio.h>
#include<string.h>
int main(){
char text[4001],text2[4001];
int memo[2][4003],now,old,ans;
while(scanf("%s",text)!=EOF){
memset(memo,0,sizeof(memo));
scanf("%s",text2);
ans=0;
for(int i=0;text2[i]!='\0';i++){
now=i%2;
old=(i+1)%2;
memset(memo[now],0,4003*4);
for(int j=0;text[j]!='\0';j++){
if(text2[i]==text[j]){
memo[now][j+1]=memo[old][j]+1;
ans=ans>memo[now][j+1]?ans:memo[now][j+1];
}
}
}
printf("%d\n",ans);
}
}
0529 Darts
解法
きれいなコードを用意できませんでした。
1本投げた場合を求め、次に2本投げた場合の全組み合わせを求め、Vectorに保存しておきます。
後は3本の組を1本のセットと2本のセットからバイナリサーチで最高点を求め、4本は2本+2本をバイナリサーチで求めます。
#include <stdio.h>
#include <vector>
#include <algorithm>
int solve(int n,int m);
int main()
{
int n,m,ans;
scanf("%d %d",&n,&m);
while(n!=0 && m!=0){
ans=solve(n,m);
printf("%d\n",ans);
scanf("%d %d",&n,&m);
}
}
int bsearch(std::vector<int> &v,int target){
int l=0,r=v.size(),size=v.size()-1;
if(v[0]>target) return 0;
if(v[size]<=target) return v[size];
int index;
while(1){
index=(l+r)/2;
if(v[index]==target) return target;
if(index<size && v[index]<target && v[index+1]>target) return v[index];
if(v[index]>target){
r=index;
continue;
}
if(v[index]<target){
l=index+1;
continue;
}
}
return -1;
}
int solve(int n,int m)
{
std::vector<int> wPoints;
std::vector<int>::iterator it;
int t;
int datas[1001];
int p=0;
int ans=0;
//一本だけ使う場合
for(int i=0;i<n;i++)
{
scanf("%d",&t);
if(t==m){
return m;
}else if(t<m){
datas[p]=t;
p++;
ans=std::max(ans,t);
}
}
//2本使う場合
for(int i=0;i<p;i++){
for(int j=0;j<=i;j++){
t=datas[i]+datas[j];
if(t==m){
return m;
}else if(t<m){
wPoints.push_back(t);
ans=std::max(ans,t);
}
}
}
std::sort(wPoints.begin(),wPoints.end());
//3本使う場合
for(int i=0;i<p;i++){
t=m-datas[i];
t=datas[i]+bsearch(wPoints,t);
ans=std::max(ans,t);
if(ans==m) return m;
}
//4本使う場合
it=wPoints.begin();
while(it!=wPoints.end())
{
t=m-(*it);
//if(t<(*it)) return ans;
t=(*it)+bsearch(wPoints,t);
ans=std::max(ans,t);
if(ans==m) return m;
it++;
}
return ans;
}
0530 Pyon-Pyon River Crossing
#include<stdio.h>
#include<vector>
#include <stdlib.h>
int n,m;
struct Stone{
int x,d;//x座標と滑りやすさ
};
void calc(){
int memo[77][154][11];//動的計画法である石に到達したとき滑りやすさの合計が最小となる経路を残す
std::vector<Stone> stones[154];
Stone stone;
int k;//滑りやすさ
int max=1000000000;
for(int z=0;z<=(n+1)/2;z++){
for(int y=0;y<n;y++){
for(int x=0;x<11;x++){
if (y==1 && z==1) memo[1][y][x]=0;
else if (y==0 && z==0) memo[0][y][x]=0;
else memo[z][y][x]=max;
}
}
}
for(int y=0;y<n;y++){
scanf("%d",&k);
for(int j=0;j<k;j++){
scanf("%d %d",&stone.x,&stone.d);
stones[y].push_back(stone);
}
}
int jump,slip;
for(int y=0;y<n-1;y++){
jump=(y+1)/2>m?m:(y+1)/2;
for(int z=0;z<=jump;z++){
for(unsigned int x=0;x<stones[y].size();x++){
//一段ジャンプ
for(unsigned int x2=0;x2<stones[y+1].size();x2++){
slip=memo[z][y][x]+abs(stones[y][x].x-stones[y+1][x2].x)*(stones[y][x].d+stones[y+1][x2].d);
if(memo[z][y+1][x2]>slip){
memo[z][y+1][x2]=slip;
}
}
//2段ジャンプ
for(unsigned int x2=0;x2<stones[y+2].size();x2++){
slip=memo[z][y][x]+abs(stones[y][x].x-stones[y+2][x2].x)*(stones[y][x].d+stones[y+2][x2].d);
if(memo[z+1][y+2][x2]>slip){
memo[z+1][y+2][x2]=slip;
}
}
}
}
}
int ans=max;
for(int z=0;z<=m;z++){
for(int x=0;x<11;x++){
ans=memo[z][n-1][x]<ans?memo[z][n-1][x]:ans;
if(z==m) continue;
ans=memo[z][n-2][x]<ans?memo[z][n-2][x]:ans;
}
}
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d %d",&n,&m);
if(n==0 && m==0) break;
calc();
}
}
最終更新:2011年10月30日 17:08