「PKJ適当」の編集履歴（バックアップ）一覧に戻る
PKJ適当 - (2011/12/09 (金) 17:36:51) のソース
北京大学ではプログラマ向け練習問題を多数掲載しています。
そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。
このサイトの問題を解いた記録を掲載しています。
プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。
とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。
*poj2887
100万文字の文字列にさらに別の文字列を2000回以下insertし2000回以下ｎ文字目の文字を返す問題
文字の枝にどんどん文字列の枝を接続していくイメージで攻略。
考え方としては子供のころ遊んだブロック遊びと大差ないなあ。
賢ければ中学生でも解けるレベルか。
一度目は何も考えずstd::strinの基本機能だけで解決しようとして惨敗。
2度目で正答できた。
ｎ文字目に文字列の枝をくっつけていく木構造で解決。
listを使えればもう少しコード実行速度もメモリ使用量も低減来たんだけどな。
木構造を表す構造体nodeのvectorをlistに変更したらコンパイラにnodeの中でlistを使用できないと怒られた。
nodeの中でlist<node>をするのはだめらしい。
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include <iostream>
bool ansHit;
struct node{
//文字列に文字をどんどんつけ足していく木構造
std::string text;
int addPoint;
std::vector<node> nodes;
std::vector<int> nodeNo;
};
void saiki(node& nowNode,int& p,const int searchP,const bool add,const std::string& addText){
//searchPはｎ文字目をサーチする-1して代入される
//ｐは今サーチしている文字
int oldP=0;
int nextP;
unsigned int nowNodeNo;
int nowAddPoint;
std::vector<int>::iterator it=nowNode.nodeNo.begin();
for(nowNodeNo=0;nowNodeNo<nowNode.nodes.size();nowNodeNo++){
nowAddPoint=nowNode.nodes[nowNode.nodeNo[nowNodeNo]].addPoint;
nextP=p+nowAddPoint-oldP;
if(searchP<nextP){
break;
}
p=nextP;
oldP=nowAddPoint;
saiki(nowNode.nodes[nowNode.nodeNo[nowNodeNo]],p,searchP,add,addText);
if(ansHit==true) return;
it++;
}
if (nowNode.nodes.empty())nextP=p+nowNode.text.size();
else if(searchP>=nextP)nextP=p+nowNode.text.size()-oldP;
if(searchP<nextP){
ansHit=true;
if(add==false){
printf("%c\n",nowNode.text[searchP-p+oldP]);
}else{
node addNode;
addNode.text=addText;
addNode.addPoint=searchP-p+oldP;
nowNode.nodes.push_back(addNode);
nowNode.nodeNo.insert(it,nowNode.nodeNo.size());
}
return ;
}
p=nextP;
}
int main(){
node top;
int n,p,searchP;
std::string com,addText;
std::cin>>(top.text)>>n;
while(n--){
std::cin>>com;
ansHit=false;
p=0;
if(com=="Q"){
std::cin>>searchP;
searchP--;
saiki(top,p,searchP,false,addText);
}else{
std::cin>>addText>>searchP;
searchP--;
saiki(top,p,searchP,true,addText);
if(ansHit==false){
node addNode;
addNode.text=addText;
addNode.addPoint=top.text.size();
top.nodes.push_back(addNode);
top.nodeNo.push_back(top.nodeNo.size());
}
}
}
}
*poj3363
使い勝手の悪いペイントツールで指定された操作を繰り返して指定された画像を作れるか、その時の最小回数を求める問題。
この問題はBit演算で解くのが賢いが私はBit演算で解くのが苦手なので配列を使って説いた。
多く見積もっても多分１０００万回程度の計算量なので何とか通った。
#include<stdio.h>
#include<string.h>
void change(char perm[102][102],int x,int y,int c,int r){
for(int px=x;px<x+c;px++){
for(int py=y;py<y+r;py++){
perm[py][px]=perm[py][px]=='0'?'1':'0';
}
}
}
bool setData(){
int h,w,r,c;
scanf("%d %d %d %d",&h,&w,&r,&c);
if(h+w+r+c==0)return false;
char map[102][102],perm[102][102];
for(int y=0;y<h;y++){
scanf("%s",&map[y]);
}
memset(perm,'0',sizeof(perm));
int ans=0;
for(int y=0;y<h-r+1;y++){
for(int x=0;x<w-c+1;x++){
if(perm[y][x]!=map[y][x]){
ans++;
change(perm,x,y,c,r);
}
}
}
bool ok=true;
for(int y=0;y<h;y++){
for(int x=0;x<w;x++)if(map[y][x]!=perm[y][x])ok=false;
}
printf("%d\n",ok?ans:-1);
return true;
}
int main(){
while(setData()){
}
}
*poj3338
長方形のケーキを複数回四角くカットしていき最後にケーキが何個に分かれたかを計算する問題。
あるカット領域を別のカット領域と区別するのに四角形の重なりを利用して解いた。
考え方としては簡単だけどもっと賢い方法があるような気がする。
#include<stdio.h>
#include<string.h>
#include <algorithm>
const int dxs[]={1,0,-1,0};
const int dys[]={0,1,0,-1};
void saiki(long long int map[22][22],const int x,const int y,const long long int nowNo,const int w,const int h){
if(x<0 || x>=w || y<0 || y>=h || map[x][y]!=nowNo) return;
map[x][y]=-1;
for(int i=0;i<4;i++){
saiki(map,x+dxs[i],y+dys[i],nowNo,w,h);
}
}
bool setData(){
long long int map[22][22],one=1,flag;
int w,h,n,x1,y1,x2,y2,ans=0;
memset(map,0,sizeof(map));
scanf("%d %d",&h,&w);
if(w+h==0)return false;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
if(x1>x2)std::swap(x1,x2);
if(y1>y2)std::swap(y1,y2);
flag=one<<i;
for(int nowX=x1;nowX<x2;nowX++){
for(int nowY=y1;nowY<y2;nowY++){
map[nowX][nowY]|=flag;
}
}
}
for(int nowX=0;nowX<w;nowX++){
for(int nowY=0;nowY<h;nowY++){
if(map[nowX][nowY]!=-1){
ans++;
saiki(map,nowX,nowY,map[nowX][nowY],w,h);
}
}
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData()){
}
}
*poj3364
白黒模様のチェスボードが40000*40000のサイズで広がっている。
指定された範囲(8,8)、（n,m）の範囲にある白か黒0か1で表されるの数を求める問題。
サクッと計算式を建てるだけの問題です。
丁寧に解説すれば中学生でもとける問題ですね。
#include<stdio.h>
int main(){
int n,m,c,col1,col2,ans;
while(1){
scanf("%d %d %d",&n,&m,&c);
if(n+m+c==0) break;
if(c==1){
col1=(n-8)/2+1;
col2=col1-(n+1)%2;
}else{
col1=(n+1-8)/2;
col2=col1+(n+1)%2;
}
ans= col1*((m-8)/2+1);
ans+=col2*((m-8+1)/2);
printf("%d\n",ans);
}
}
*poj3325
競技で各審査員のつけた得点から得点の最高値と最低値を2つだけ無視して小数点以下切り捨てで平均を出す問題。
簡単すぎて掲載する意味があるのかすら不明な問題。
#include<stdio.h>
bool setData(){
int max,min,sum=0,n,num;
scanf("%d",&n);
if(n==0) return false;
scanf("%d",&sum);
max=min=sum;
for(int i=1;i<n;i++){
scanf("%d",&num);
sum+=num;
max=max>num?max:num;
min=min<num?min:num;
}
printf("%d\n",(sum-max-min)/(n-2));
return true;
}
int main(){
while(setData()){
}
}
*poj3444
ウェーブレット変換を施す問題。
ウェーブレット変換が何をする操作なのかはよく分からなかったし英文も読解できなかったので、サンプルインプットの数字だけを頼りに直感だけでこういう変換ではないかとコードを記述したら一発で通った。
うーん運任せ。
#include<stdio.h>
#include<string.h>
bool setData(){
int nums[257],len,nexts[257];
scanf("%d",&len);
if(len==0)return false;
for(int i=0;i<len;i++)scanf("%d",&nums[i]);
memcpy(nexts,nums,sizeof(nums));
for(int i=1;i<len;i*=2){
for(int j=0;j<i;j++){
nexts[j*2 ]=(nums[j]+nums[j+i])/2;
nexts[j*2+1]=(nums[j]-nums[j+i])/2;
}
memcpy(nums,nexts,sizeof(nexts));
}
for(int i=0;i<len;i++)printf("%s%d",i?" ":"",nums[i]);
printf("\n");
return true;
}
int main(){
while(setData()){
}
}
*poj 2853
ある数aが与えられたときそれを連続した整数の和として表す時何通りの表し方があるかを調べて数える問題。
a=a1+(a1+1)=a2+(a2+1)+(a2+2)=a3+(a3+1)+(a3+2)+(a3+3)
a=2a1+1=3a2+3=4a3+6=,,,となるので後は
(a-1)/2=a1
(a-3)/3=a2
(a-6)/4=a3
,,,の形に変形すれば割り切れるならaiは連続した和としての資格がある数となる。
高校1年生でも融ける問題。
#include<stdio.h>
int main(){
unsigned int no,num,n,max,sum,ans;
scanf("%d",&n);
max=2147483648;
while(n--){
scanf("%d %d",&no,&num);
ans=sum=0;
for(int i=1;sum<=max;i++){
sum+=i;
if(num<=sum) break;
if((num-sum)%(i+1)==0){
ans++;
}
}
printf("%d %d\n",no,ans);
}
}
*Poj2840
POJで一番簡単な問題だろうか？
11時間分だけずれた回数鐘を鳴らす時計塔が何回鐘を打つかを答える問題。
#include<stdio.h>
int main(){
int n,h,m;
scanf("%d",&n);
while(n--){
scanf("%d:%d",&h,&m);
printf("%d\n",m==0?((h+11)%24+1):0);
}
}
*poj2837
ある数ｎを連続した素数の和として表したとき何通りの表し方があるか答える問題。
計算量が小さいので極端に手抜きしてみた。
#include<stdio.h>
#include<set>
#include<string.h>
const int maxNum=20001;
bool so[maxNum];
int ans[maxNum];
std::set<int> sosuu;
void setData(){
memset(so,true,sizeof(so));
memset(ans,0,sizeof(ans));
sosuu.insert(2);
for(int i=3;i<maxNum;i+=2){
if(so[i]==false) continue;
sosuu.insert(i);
for(int j=i*2;j<maxNum;j+=i)so[j]=false;
}
std::set<int>::iterator it1,it2;
int sum;
for(it1=sosuu.begin();it1!=sosuu.end();it1++){
sum=0;
for(it2=it1;it2!=sosuu.end();it2++){
sum+=(*it2);
if(sum>=maxNum)break;
ans[sum]++;
}
}
}
int main(){
setData();
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
printf("%d\n",ans[n]);
}
}
*poj2845
2進数の足し算を計算する問題。
賢い方法がわからなかったので反転右揃え左は適当0づめにして計算し最後に計算結果を反転して出力。
計算量も小さくWAが怖かったので少し余分に配列を確保して計算した。
#include<stdio.h>
#include<string.h>
#include <algorithm>
const int maxLen=85;
void add(const char num1[maxLen],const char num2[maxLen],int ansNo){
int up=0,nowSum;
char ans[maxLen];
for(int i=0;i<maxLen-1;i++){
nowSum=(num1[i]-'0')+(num2[i]-'0')+up;
up=nowSum>1?1:0;
ans[i]=nowSum%2+'0';
}
printf("%d ",ansNo);
int p;
for(p=maxLen-2;p>0;p--)if(ans[p]=='1')break;
for(int i=p;i>=0;i--)printf("%c",ans[i]);
printf("\n");
}
void revers(char num[maxLen]){
int n=strlen(num);
for(int i=0;i<n/2;i++){
std::swap(num[n-1-i],num[i]);
}
for(int i=n;i<maxLen-1;i++)num[i]='0';
num[maxLen-1]='\0';
}
int main(){
char num1[maxLen],num2[maxLen];
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s %s",num1,num2);
revers(num1);
revers(num2);
add(num1,num2,i);
}
}
*poj2657
障害物のある周回コースをｋマス飛ばしで周回しながらゴールにたどり着くときｋの最小値を答える問題。
簡単な問題な上計算量も小さいので超手抜き。
#include<stdio.h>
#include<string.h>
#include<vector>
struct point{
int no,k;
};
int main(){
std::vector<point> points;
point p,ans;
int n,z,m,t;
bool moveOKs[1001];
memset(moveOKs,true,sizeof(moveOKs));
scanf("%d %d %d",&n,&z,&m);
z--;//スタート地点を0升目として計算を簡素化する
for(int i=0;i<m;i++){
scanf("%d",&t);
moveOKs[t-1]=false;
}
for(int k=1;k<n;k++){
p.no=p.k=k;
points.push_back(p);
}
for(int i=0;i<n+1;i++){
//たった100万回の計算なので極限まで手抜き
for(unsigned int j=0;j<points.size();j++){
if(points[j].k==0)break;
if(moveOKs[points[j].no]==false)continue;
if(points[j].no==z){
ans=points[j];
points[j].k=0;
break;
}else{
points[j].no=(points[j].no+points[j].k)%n;
}
}
}
printf("%d\n",ans.k);
}
*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
http://poj.org/problem?id=1047
142857*1～6までは12487を循環シフトしたものになっている。
あるｎ文字の数字が与えられるのでその数字に1～ｎ-1までをかけたものがその数字が循環シフトになっているかを求める問題。
簡単なので中学生でも解けそうです。
#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
http://poj.org/problem?id=1080
２つのDNAデータからDNAの類似度をスコアーとして算出する問題。
典型的な動的計画法の問題で楽々です。
#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
http://poj.org/problem?id=1163
三角形に配置された数字を上から下へ移動しながら合計値が最大となるルートを見つけその数を返す問題。
#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
http://poj.org/problem?id=1019
数列を繋げて文字列を作った時、i文字目にどんな数字が入ってるかを答える問題。
何個目の数列かを計算して、めんどくさかったので後は力づくで答えた。
#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
http://poj.org/submit?problem_id=2665
道路から木を撤去していく問題。
簡単な問題なので書くだけ。
#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()){
}
}
