北京大学ではプログラマ向け練習問題を多数掲載しています。
そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。
このサイトの問題を解いた記録を掲載しています。
プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。
とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。
POJ1562
油田の地図データから油田の数を数える問題。
簡単な問題なのでちょちょいと書いた。
#include<stdio.h>
#include<string.h>
char map[104][103];
int dxs[8]={1,1,0,-1,-1,-1,0,1};
int dys[8]={0,1,1,1,0,-1,-1,-1};
void saiki(int x,int y){
int nx,ny;
for(int i=0;i<8;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(map[ny][nx]=='@'){
map[ny][nx]='*';
saiki(nx,ny);
}
}
}
void setData(int h,int w){
memset(map,'*',sizeof(map));
for(int i=1;i<=h;i++){
scanf("%s",&map[i][1]);
map[i][w+1]='*';
}
int ans=0;
for(int y=1;y<=h;y++){
for(int x=1;x<=w;x++){
if(map[y][x]=='@'){
saiki(x,y);
ans++;
}
}
}
printf("%d\n",ans);
}
int main(){
int w,h;
while(1){
scanf("%d %d",&h,&w);
if(h+w==0)break;
setData(h,w);
}
}
poj1051
モールス信号を一定のルールで符号化してさらにそれを復号化する問題。
符号化の表を作るのがめんどいだけでアルゴリズムとしては単純。
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
#include <algorithm>
std::map<char,std::string> alphaToCode;
std::map<std::string,char> codeToAlpha;
void setData(){
std::string codes[30]={".-","-...","-.-.","-..",".","..-.","--.",
"....","..",".---","-.-",".-..","--","-.",
"---",".--.","--.-",".-.","...","-","..-",
"...-",".--","-..-","-.--","--..",
"..--","---.",".-.-","----"};
char alpha[30];
for(char i='A';i<='Z';i++)alpha[i-'A']=i;
alpha[26]='_';
alpha[27]='.';
alpha[28]=',';
alpha[29]='?';
for(int i=0;i<30;i++){
alphaToCode[alpha[i]]=codes[i];
codeToAlpha[codes[i]]=alpha[i];
}
}
void codeChange(int no){
std::string codes,nums,text,code,ans;
std::cin>>text;
char num;
for(int p=0;p<text.size();p++){
code=alphaToCode[text[p]];
codes+=code;
num=(char)code.size()+'0';
nums+=num;
}
for(int i=0;i<nums.size()/2;i++)std::swap(nums[i],nums[nums.size()-i-1]);
int nowP=0;
for(int i=0;i<nums.size();i++){
code=codes.substr(nowP,nums[i]-'0');
ans+=codeToAlpha[code];
nowP+=nums[i]-'0';
}
std::cout<<no<<": "<<ans<<"\n";
}
int main(){
setData();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
codeChange(i);
}
}
POJ1177
AOJに掲載のSheetという問題の亜種なのでそれを思い出しながら解く。
考え方さえわかっていればそんなに難しい問題ではない。
問題は速度が出なかったこと。
AOJでは最速クラスのコードを叩き出した私ですが世界では遅かった。
AOJは日本国内限定、熱心な参加者も少ないしどうしても限定されたランクになる、熱心なのは300人ほど。
それに対しPOJは参加者が圧倒的に多い、むむむこれが世間の標準レベル、このレベルでコード実行速度を競うことでようやく世間の平均値に辿りつけるのかと感心。
AOJでは結構実行速度の速いコードを書いてるほうの私ですがPOJという世間一般レベルでの評価では遅い方。
まだまだ精進だなあと感じた次第。
今回のコードは最後のWhileとForの3重ループが悪かったのかも？
ループは重ねると遅くなるという実感はあるのだが、ループは楽だからなあつい使っちゃうんだよな。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
struct point{
int xLeft,y,inOut,xRight;
bool operator<(const point& p)const{
if(y!=p.y)return y>p.y;
return inOut<p.inOut;//inが先に来るようにする
}
};
int main(){
int n;
std::priority_queue<point> points;
scanf("%d",&n);
point p1,p2;
p1.inOut=1;
p2.inOut=-1;
int inOutCounts[20003];
std::vector<int> inYPosMemo[20003];
memset(inOutCounts,0,sizeof(inOutCounts));
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&p1.xLeft,&p1.y,&p2.xRight,&p2.y);
p2.xLeft=p1.xLeft;
p1.xRight=p2.xRight;
points.push(p1);
points.push(p2);
}
const int shift=10001;
while(!points.empty()){
p1=points.top();
points.pop();
p1.xLeft+=shift;
p1.xRight+=shift;
for(int x=p1.xLeft;x<p1.xRight;x++){
inOutCounts[x]+=p1.inOut;
if(inOutCounts[x]==0){
inYPosMemo[x].push_back(p1.y);
}else if(inOutCounts[x]==1 && p1.inOut==1){
inYPosMemo[x].push_back(p1.y);
}
}
}
int ans=0,y1,y2,y3,y4,pLeft;
for(int x=1;x<20002;x++){
ans+=inYPosMemo[x].size();//上下両端を足しこむ
pLeft=0;
for(int pNow=0;pNow<inYPosMemo[x].size();pNow+=2){
y3=inYPosMemo[x][pNow+1];
y4=inYPosMemo[x][pNow];
ans+=2*(y3-y4);
while(pLeft<inYPosMemo[x-1].size()){
y1=inYPosMemo[x-1][pLeft+1];
y2=inYPosMemo[x-1][pLeft];
if(y4>=y1){
}else if(y2>=y3){
break;
}else if(y3>=y1&&y1>=y4 && y4>=y2){
ans-=2*(y1-y4);
}else if(y1>=y3&&y3>=y2&&y4>=y2){
ans-=2*(y3-y4);
break;
}else if(y1>=y3&&y3>=y2&&y2>=y4){
ans-=2*(y3-y2);
break;
}else if(y3>=y1&&y1>=y4&&y2>=y4){
ans-=2*(y1-y2);
}
pLeft+=2;
}
}
}
printf("%d\n",ans);
}
poj1406
四角い燃料と三角錐の燃料を補給する問題。
簡単な問題なので中学生でもとけそう。
#include<set>
#include<stdio.h>
std::set<int> cube,pyramid;
void setData(){
for(int i=0;i*i*i<=151200;i++){
cube.insert(i*i*i);
}
for(int i=0;(i*(i+1)*(i+2))/6<=151200;i++){
pyramid.insert((i*(i+1)*(i+2))/6);
}
}
int main(){
setData();
int n,ans;
std::set<int>::iterator it,it2;
while(1){
scanf("%d",&n);
if(n==0)break;
ans=0;
for(it=cube.begin();(*it)<=n&&it!=cube.end();it++){
it2=pyramid.upper_bound(n-(*it));
if(it2!=pyramid.begin())it2--;
ans=(*it)+(*it2)>ans?(*it)+(*it2):ans;
}
printf("%d\n",ans);
}
}
poj1047
#include<stdio.h>
#include<string>
#include<iostream>
#include<set>
void add(std::string& num1,const std::string num2,int size){
int up=0;
for(int i=size-1;i>=0;i--){
num1[i]+=num2[i]+up;
up=num1[i]/10;
num1[i]%=10;
}
//return up==1?false:true;
}
bool calcData(std::string num){
char t;
int size=num.size();
std::set<std::string> nums;
std::string fNum=num;
for(int i=0;i<size;i++){
num[i]-='0';
fNum[i]-='0';
}
for(int i=0;i<size;i++){
t=num[0];
for(int p=0;p<size-1;p++)num[p]=num[p+1];
num[size-1]=t;
nums.insert(num);
}
for(int i=0;i<size-1;i++){
add(num,fNum,size);
if(nums.find(num)==nums.end())return false;
if(num==fNum)break;
}
return true;
}
int main(){
std::string num;
while(1){
std::cin>>num;
if(std::cin.eof())break;
if(calcData(num)){
printf("%s is cyclic\n",num.c_str());
}else{
printf("%s is not cyclic\n",num.c_str());
}
}
}
poj1157
簡単な問題なので正答率を稼げるおいしい問題と思って挑戦する。
しょうもないポカミスに気づかず論理的に正しいのに何故正解にならないのかと不思議だった問題。
最初は読解ミスとはいえ読解後のWA３連続はダメージ大きいです。
動的計画法の計算部分のy<=hとx<=wを間違えてy<hとx<wにしていたというポカ、はい馬鹿発見ですね。
#include<stdio.h>
#include <algorithm>
const int sizeMax=103;
void setData(){
int memo[sizeMax][sizeMax];
int score[sizeMax][sizeMax];
int h,w;
scanf("%d %d",&h,&w);
for(int y=0;y<=h;y++){
for(int x=0;x<=w;x++){
memo[y][x]=-10000000;
if(y!=h&&x!=w)scanf("%d",&score[y][x]);
}
}
memo[0][0]=0;
for(int y=0;y<h;y++){
for(int x=y;x<w;x++){
memo[y][x+1 ]=std::max(memo[y][x],memo[y][x+1]);
memo[y+1][x+1]=std::max(memo[y][x]+score[y][x],memo[y+1][x+1]);
}
}
printf("%d\n",memo[h][w]);
}
int main(){
setData();
}
poj1218
酔っ払った看守がドアを開放したり閉じたりしていく問題。
#include<stdio.h>
#include<string.h>
const int roomMax=102;
bool lock[roomMax];
int ans[roomMax];
void setData(){
memset(lock,true,sizeof(lock));
for(int i=2;i<roomMax;i++){
for(int j=i;j<roomMax;j+=i){
lock[j]=!lock[j];
}
}
int count=0;
for(int i=1;i<roomMax;i++){
count+=lock[i]?1:0;
ans[i]=count;
}
}
int main(){
int t,n;
setData();
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
}
poj1080
#include<stdio.h>
#include<iostream>
#include<string>
#include <algorithm>
int dnaScore[5][5]={ {5,-1,-2,-1,-3},
{-1,5,-3,-2,-4},
{-2,-3,5,-2,-2},
{-1,-2,-2,5,-1},
{-3,-4,-2,-1,0}};
int dnaToNo(char t){
if(t=='A'){
return 0;
}else if(t=='C'){
return 1;
}else if(t=='G'){
return 2;
}else if(t=='T'){
return 3;
}else{
return 4;
}
}
void setData(){
int len1,len2,score;
int memo[102][102];//memo[1つめのDNAをM文字目まで読んで][２つ目のDNAをN文字目]まで読んだ場合の最大値
for(int x=0;x<102;x++){
for(int y=0;y<102;y++)memo[x][y]=-1000000;//一列ずつの動的計画法
}
std::string dna1,dna2;
std::cin>>len1>>dna1;
std::cin>>len2>>dna2;
if(len1<len2){
//dna1を長くしてコードを簡単にする
std::swap(len1,len2);
std::swap(dna1,dna2);
}
memo[0][0]=0;
for(int x=0;x<len1;x++){
for(int y=0;y<len2;y++){
score=memo[x][y]+dnaScore[dnaToNo(dna1[x])][dnaToNo(dna2[y])];
memo[x+1][y+1]=std::max(memo[x+1][y+1],score);
score=memo[x][y]+dnaScore[dnaToNo(dna1[x])][4];//-にして読み飛ばす
memo[x+1][y]=std::max(memo[x+1][y],score);
score=memo[x][y]+dnaScore[4][dnaToNo(dna2[y])];
memo[x][y+1]=std::max(memo[x][y+1],score);
}
}
printf("%d\n",memo[len1][len2]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
setData();
}
}
poj1163
#include<stdio.h>
#include<string.h>
#include <algorithm>
int main(){
int n,l,t,ans=0;
int memo[102][102];
scanf("%d",&n);
memset(memo,0,sizeof(memo));
for(int y=1;y<=n;y++){
for(int x=1;x<=y;x++){
scanf("%d",&t);
memo[y][x]=std::max(memo[y-1][x-1]+t,memo[y-1][x]+t);
ans=std::max(ans,memo[y][x]);
}
}
printf("%d\n",ans);
}
poj3748
Bit演算をする問題。
Bit演算は苦手なので少しコードが冗長。
#include<stdio.h>
int main(){
int r,x,y;
int bit;
scanf("%x,%d,%d",&r,&x,&y);
bit=~(1<<(x));
r&=bit;
bit=~(7<<(y-2));
r&=bit;
bit=6<<(y-2);
r|=bit;
printf("%x\n",r);
}
poj1019
#include<stdio.h>
#include<set>
#include <sstream>
#include <iostream>
#include <string>
std::set<int> datas;
std::string nums;
int saiki(int num,int num9,int deep,int sum){
if(num<=num9)return num*deep+sum;
return saiki(num-num9,num9*10,deep+1,sum+num9*deep);
}
std::string IntToString(int num){
std::stringstream ss;
ss<<num;
return ss.str();
}
void setData(){
datas.clear();
unsigned int sum=1;
int i=1;
datas.insert(0);
while(sum<=2147483647){
datas.insert(sum);
nums.append(IntToString(i));
i++;
sum+=saiki(i,9,1,0);
}
}
int main(){
int t,no,top;
std::set<int>::iterator it;
setData();
scanf("%d",&t);
while(t--){
scanf("%d",&no);
it=datas.lower_bound(no);
if(it!=datas.begin())it--;
std::cout<<nums[no-(*it)-1]<<"\n";
}
}
poj2665
#include<stdio.h>
bool setData(){
int l,m;
scanf("%d %d",&l,&m);
if(l==0&&m==0)return false;
int x1,x2;
l++;
while(m--){
scanf("%d %d",&x1,&x2);
l-=(x2-x1+1);
}
printf("%d\n",l);
return true;
}
int main(){
while(setData()){
}
}
