「PKJ適当」の編集履歴(バックアップ)一覧はこちら
PKJ適当 - (2011/12/05 (月) 14:09:52) の1つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
北京大学ではプログラマ向け練習問題を多数掲載しています。
そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。
このサイトの問題を解いた記録を掲載しています。
プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。
とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。
*poj2887
100万文字の文字列にさらに別の文字列を2000回以下insertし2000回以下n文字目の文字を返す問題
只今攻略中。
文字の枝にどんどん文字列の枝を接続していくイメージで攻略予定。
1度目は何も考えずstd::stringの機能を使って惨敗。
こんどは大丈夫なはずだけどこの考え方で速度が出るのかは不明。
考え方としては子供のころ遊んだブロック遊びと大差ないなあ。
賢ければ中学生でも解けるレベルか。
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include <algorithm>
bool ansHit;
struct node{
//文字列に文字をどんどんつけ足していく木構造
std::string text;
std::vector<node> nodes;
int addPoint;
bool operator<(const node& n)const{
return addPoint<n.addPoint;
}
};
void saiki(node& nowNode,int& p,const int searchP,const bool add,const& std::string addText){
//searchPはn文字目をサーチする-1して代入される
//pは今サーチしている文字
int oldP=0;
int nextP;
for(int i=0;i<nowNode.nodes.size();i++){
nextP=p+nowNode.nodes[i].addPoint-oldP;
if(searchP<nextP){
break;
}
p=nextP;
oldP=nowNode.nodes[i].addPoint;
saiki(nowNode.nodes[i],p,searchP,add);
if(ansHit==true) return;
}
if(nowNode.nodes.empty())nextP=p+nowNode.text.size();
if(searchP<nextP){
ansHit=true;
if(add==false){
printf("%c\n",nowNode.text[searchP-p]);
}else{
node addNode;
addNode.text=addText;
addNode.addPoint=searchP-p;
nowNode.nodes.push_back(addNode);
nowNode.addPoints.push_back(searchP-p);
std::sort(nowNode.nodes.begin(),nowNode.nodes.end());
}
return ;
}
if(nowNode.nodes.empty()==false)nextP=p+nowNode.text.size()-oldP;
p=nextP;
}
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
http://poj.org/problem?id=1047
142857*1~6までは12487を循環シフトしたものになっている。
あるn文字の数字が与えられるのでその数字に1~n-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
簡単な問題なので正答率を稼げるおいしい問題と思って挑戦する。
しょうもないポカミスに気づかず論理的に正しいのに何故正解にならないのかと不思議だった問題。
最初は読解ミスとはいえ読解後のWA3連続はダメージ大きいです。
動的計画法の計算部分の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
2つの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文字目まで読んで][2つ目の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()){
}
}
北京大学ではプログラマ向け練習問題を多数掲載しています。
そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。
このサイトの問題を解いた記録を掲載しています。
プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。
とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。
*poj2887
100万文字の文字列にさらに別の文字列を2000回以下insertし2000回以下n文字目の文字を返す問題
只今攻略中。
文字の枝にどんどん文字列の枝を接続していくイメージで攻略予定。
1度目は何も考えずstd::stringの機能を使って惨敗。
こんどは大丈夫なはずだけどこの考え方で速度が出るのかは不明。
考え方としては子供のころ遊んだブロック遊びと大差ないなあ。
賢ければ中学生でも解けるレベルか。
n文字目に文字列の枝を組み込んでいく木構造で解決。
listを使えればもう少しコード実行速度もメモリ使用量も低減来たんだけどな。
#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はn文字目をサーチする-1して代入される
//pは今サーチしている文字
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());
}
}
}
}
*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を循環シフトしたものになっている。
あるn文字の数字が与えられるのでその数字に1~n-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
簡単な問題なので正答率を稼げるおいしい問題と思って挑戦する。
しょうもないポカミスに気づかず論理的に正しいのに何故正解にならないのかと不思議だった問題。
最初は読解ミスとはいえ読解後のWA3連続はダメージ大きいです。
動的計画法の計算部分の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
2つの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文字目まで読んで][2つ目の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()){
}
}