北京大学ではプログラマ向け練習問題を多数掲載しています。
そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。
このサイトの問題を解いた記録を掲載しています。
プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。
とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。
poj2887
100万文字のテキストにさらに長いテキストを2000回以下insertし2000回以下ｎ文字目の文字を返す問題
只今攻略中。
文字の枝にどんどん文字を接続していくイメージで攻略予定。
1度目は何も考えずstd::stringの機能を使って惨敗。
こんどは大丈夫なはずだけどこの考え方で速度が出るのかは不明。
考え方としては子供のころ遊んだブロック遊びと大差ないなあ。
賢ければ中学生でも解けるレベルか。
#include<stdio.h>
#include<string>
#include<vector>
struct node{
//文字列に文字をどんどんつけ足していく木構造
std::string text;
std::vector<node> nodes;
std::vector<int> addPoints;
};
void saiki(node& nowNode,int& p){
for(int i=0;i<nowNode.nodes.size();i++){
}
}
int main(){
node top;
}
poj2823
100万個の数列を範囲Kでシフトしながらその範囲の最大値と最小値を求める問題。
簡単な問題だけど範囲をずらしながら新しく範囲に入った数字と範囲外に入った数字をmapを使って範囲内の数字の出現回数をカウントしてみたり、setを使って一番大きい数字と小さい数字の範囲を優先的に埋めていったり結構間抜けな攻略法で挑戦して惨敗した問題。
結局優先順位付きキューを使ったシンプルで簡単な方法で解いた。
計算量との戦いだった問題でこれがいわゆるラージサイズの問題の計算量かと感心した次第。
AOJではミドルサイズの問題は出てもラージサイズの問題はほとんど出なかったからなあ、これからはラージサイズの問題を前提にしたコードを考えないとなあ。
#include<stdio.h>
#include <algorithm>
#include <queue>
struct Num{
int num,p;
};
class maxSorter
{
public:
bool operator() (const Num& l, const Num&r) const
{
return l.num<r.num;
}
};
class minSorter
{
public:
bool operator() (const Num& l, const Num&r) const
{
return l.num>r.num;
}
};
const int size=1000001;
int mins[size],maxs[size];
int main(){
Num num,nowMax,nowMin;
int n,k;
std::priority_queue<Num,std::vector<Num>,maxSorter> maxMemo;
std::priority_queue<Num,std::vector<Num>,minSorter> minMemo;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&num.num);
num.p=i;
if(i==0)nowMax=nowMin=num;
if(nowMax.num<=num.num)nowMax=num;
else maxMemo.push(num);
if(nowMin.num>=num.num)nowMin=num;
else minMemo.push(num);
while(nowMin.p+k <= i){
nowMin=minMemo.top();
minMemo.pop();
}
while(nowMax.p+k<=i){
nowMax=maxMemo.top();
maxMemo.pop();
}
if(i+1>=k){
mins[i-k+1]=nowMin.num;
maxs[i-k+1]=nowMax.num;
}
}
printf("%d",mins[0]);
for(int i=1;i<n-k+1;i++)printf(" %d",mins[i]);
printf("\n");
printf("%d",maxs[0]);
for(int i=1;i<n-k+1;i++)printf(" %d",maxs[i]);
printf("\n");
}
POJ2121
アルファベット表記の数字を文字に戻す問題。
こんなめんどくさい表記法誰がするのだろうか？
#include<stdio.h>
#include<string>
#include<map>
#include<vector>
std::map<std::string,int> words;
void setData(){
words["zero"]=0;
words["one"]=1;
words["two"]=2;
words["three"]=3;
words["four"]=4;
words["five"]=5;
words["six"]=6;
words["seven"]=7;
words["eight"]=8;
words["nine"]=9;
words["ten"]=10;
words["eleven"]=11;
words["twelve"]=12;
words["thirteen"]=13;
words["fourteen"]=14;
words["fifteen"]=15;
words["sixteen"]=16;
words["seventeen"]=17;
words["eighteen"]=18;
words["nineteen"]=19;
words["twenty"]=20;
words["thirty"]=30;
words["forty"]=40;
words["fifty"]=50;
words["sixty"]=60;
words["seventy"]=70;
words["eighty"]=80;
words["ninety"]=90;
words["hundred"]=100;
words["thousand"]=1000;
words["million"]=1000000;
}
int main(){
setData();
char sp[3];
char word[10];
std::string num;
while(1){
int ans=0,neg=1,nowNum;
std::vector<int> v,ansV;
sp[0]=sp[1]='\0';
while(scanf("%s%[\n]",word,sp)!=EOF){
num=word;
if(num=="negative"){
neg=-1;
}else{
nowNum=words[num];
v.push_back(nowNum);
ansV.push_back(nowNum);
for(int i=v.size()-2;i>=0;i--){
if(v[i]<nowNum){
ansV[i]*=nowNum;
ansV[v.size()-1]=0;
}else{
break;
}
}
}
if(sp[0]=='\n')break;
}
for(int i=0;i<v.size();i++)ans+=ansV[i];
printf("%d\n",ans*neg);
if(sp[1]=='\n')break;
}
}
POJ2105
IPアドレスを表す32個の01の数字からIPアドレスの数字を算出する問題。
うーん実務でこんなコードを書いたら怒られるだろうな。
#include<stdio.h>
int codeToNo(char* text){
int b=128,ans=0;
for(int i=0;i<8;i++){
ans+=text[i]=='0'?0:b;
b/=2;
}
return ans;
}
int main(){
int n;
char bits[33];
scanf("%d",&n);
while(n--){
scanf("%s",bits);
printf("%d.%d.%d.%d\n",codeToNo(&bits[0]),codeToNo(&bits[8]),codeToNo(&bits[16]),codeToNo(&bits[24]));
}
}
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()){
}
}
