コード記述者 堀江伸一
世にあるプログラマ養成プロジェクトの一つとして北京大学主催のプログラマ向け練習問題サイトというものがあります。
3000問程度問題が掲載されており、国際的にみても登録者の多いサイトで国際的には有名なサイトでアルゴリズムを勉強するにはちょうどいいサイトです。
問題を解くコードを書いてサーバに送信するとテストデータを使って自動採点までしてくれるので独学にはお勧めのサイトです。
http://poj.org/problemlist
ただ問題が英語か中国語で掲載されているため日本人には敷居が高いかもしれません。
そこでリンク先サイトが役に立ちます。
問題を日本語訳しており挑戦しやすくなっております。
http://wikiwiki.jp/pku/?FrontPage
リンク先サイトでは翻訳者を募集しているのですが、私はこのサイトをいいサイトだと思い簡単な問題だけ選んで翻訳に参加しています。
翻訳した内容を誰かが読んでくれていたら幸いです。
翻訳の手助けをしてもらおうと問題の分かりにくい部分を掲示板などで質問すると冷たい返事しか返ってこない世の中はちょっとつらいです。
poj3126
4けたの素数が二つS,Gが与えられる。
Sのケタを一つだけ変化させて4桁の素数に変化させる操作を繰り返す。
最小の操作回数でSをGに変化させた場合何回の操作で終わるかを出力する問題。
とりあえず幅優先探索で力づくで求めたけど、もっと賢い方法がありそうな問題でもある。
最初に素数のグラフを作って、ワーシャルフロイド法で解けば速度出たかな？
#include<stdio.h>
#include<set>
#include<queue>
struct so{
int nums[4],turn;
bool operator<(const so& s)const{
for(int i=0;i<4;i++){
if(nums[i]!=s.nums[i])return nums[i]<s.nums[i];
}
return false;
}
void set(int num){
for(int i=3;i>=0;i--){
nums[i]=num%10;
num/=10;
}
turn=0;
}
};
void setSosuu(std::set<so>& memo){
bool sosuu[10000];
so s;
memset(sosuu,true,sizeof(sosuu));
for(int i=3;i<10000;i+=2){
if(sosuu[i]==false) continue;
if(i>999){
s.set(i);
memo.insert(s);
}
for(int j=i*3;j<10000;j+=i*2){
sosuu[j]=false;
}
}
}
int main(){
std::set<so> memo;
setSosuu(memo);
int n,num1,num2;
so s1,s2;
scanf("%d",&n);
while(n--){
scanf("%d %d",&num1,&num2);
s1.set(num1);
s2.set(num2);
std::queue<so> qu;
std::set<so> spents;
qu.push(s1);
spents.insert(s1);
int t;
while(!qu.empty()){
s1=qu.front();
qu.pop();
if(!(s1<s2)&&!(s2<s1)) break;
s1.turn++;
for(int i=0;i<4;i++){
for(int j=0;j<=9;j++){
t=s1.nums[i];
s1.nums[i]=j;
if(spents.find(s1)==spents.end() && memo.find(s1)!=memo.end()){
spents.insert(s1);
qu.push(s1);
}
s1.nums[i]=t;
}
}
}
printf("%d\n",s1.turn);
}
}
poj 3126
サンプルとして与えられた表から規則性を見出し、その規則性に沿った表を出力する問題。
うーんforが2回に分かれているの何とかなったかも？
#include<stdio.h>
#include<string.h>
int main(){
int n,s;
char map[21][21];
scanf("%d %d",&n,&s);
memset(map,'0',sizeof(map));
for(int c=0;c<n;c++){
for(int r=0;r<=c;r++){
map[r][c]=s+'0';
s=s%9+1;
}
}
for(int r=0;r<n;r++){
for(int c=0;c<n;c++){
printf("%s%c",c==0?"":" ",map[r][c]=='0'?' ':map[r][c]);
}
printf("\n");
}
}
poj3176
パスカルの三角形と同じ配置の数字を上からスタートして右下か左下か選びながら移動していったとき、通ったルート上の数字の合計が最大になるルートを探すという問題。
ほとんど同じ問題が別にあったので前の問題を参考にしながら動的計画法でアセプト。
#include<stdio.h>
#include<string.h>
#include <algorithm>
int main(){
int n,nowR,nextR,ans=0;
int memo[2][352];
int num;
scanf("%d",&n);
memset(memo,0,sizeof(memo));
for(int i=1;i<=n;i++){
nowR =i%2;
nextR=(i+1)%2;
for(int j=1;j<=i;j++){
scanf("%d",&num);
memo[nextR][j]=num+std::max(memo[nowR][j-1],memo[nowR][j]);
ans=std::max(ans,memo[nextR][j]);
}
}
printf("%d\n",ans);
}
poj3100
B=A^nのBとｎからAを求める問題、ただしA、B、Nは3つとも整数。
北京大の問題は中学生でもとける問題から大学生でも悩む問題までそろっていますが、これは高校生向けの問題のようです。
#include<stdio.h>
#include <stdlib.h>
#include <math.h>
bool setData(){
double a,n,b;
int sa=1000001,ans,d,t;
scanf("%lf %lf",&b,&n);
if(b==0&&n==0) return false;
a=pow(b,1/n);
d=(int)a;
if(d>1)d--;
for(int i=d;i<d+3;i++){
t=abs(b-(int)pow(i,n));
if(t<sa){
sa=t;
ans=i;
}
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData()){
}
}
poj3365
縦横サイズが決まっている板からまず円を切りぬき、次に四角形の縦横と平行に切断を入れて四角い板を切りだす。
このとき、板を丸く曲げて円と接合して上に穴のあいた円柱を作るとき、作ることのできる円柱の最大値を求めよという問題。
縦と横どちらを円中との接合部に使うかということに注意さえすれば高校生に出すとちょうどよさそうな問題ですね。
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<math.h>
#include <algorithm>
int main(){
double w,h,r,v,v2;
while(1){
scanf("%lf %lf",&w,&h);
if(w==0&&h==0)break;
r=h/(2.0*(1.0+M_PI));//高さを円との接合部に使う場合
if(2.0*r>w)r=w/2.0;
v=r*r*M_PI*w;
r=w/(2.0*M_PI);//横を円との接合部に使う場合
v2=r*r*M_PI*(h-2.0*r);
v=std::max(v,v2);
printf("%.3lf\n",v);
}
}
poj 3366
与えられた単語を複数形にする問題。
特別な場合のリストが最初に与えられ、それ以外は指定されたルールで複数形にチェンジする問題。
末尾をiesに変形する場合のif文のルールが一行だけわからなかったので、掲示板で変形ルールを質問して解いた。
#include<stdio.h>
#include<string>
#include<map>
#include<iostream>
void change(){
std::map<std::string,std::string> memos;
std::string text,cText,lastTwo;
char last,t;
int l,n;
scanf("%d %d",&l,&n);
while(l--){
std::cin>>text>>cText;
memos[text]=cText;
}
while(n--){
std::cin>>text;
last=text[text.size()-1];
if(text.size()>1)lastTwo=text.substr(text.size()-2);
else lastTwo=" ";
t=lastTwo[0];
if(memos.find(text)!=memos.end()){
text=memos[text];
}else if(!(t=='a'||t=='i'||t=='u'||t=='e'||t=='o')&&last=='y'){
text[text.size()-1]='i';
text+="es";
}else if(last=='x' || last=='s' || last=='o' || lastTwo=="ch" || lastTwo=="sh"){
text+="es";
}else{
text+="s";
}
std::cout<<text<<"\n";
}
}
int main(){
change();
}
poj1316
1949年だがに発見された単調増加数列の初項の集合を求める問題。
求める範囲が狭いので力づくで求めた。
#include<stdio.h>
#include<string.h>
bool hits[10002];
int main(){
int num,next;
memset(hits,false,sizeof(hits));
for(int i=1;i<10000;i++){
if(hits[i]==true)continue;
next=num=i;
while(next<10000){
while(num>0){
next+=num%10;
num/=10;
}
if(hits[next]==true)break;
hits[next]=true;
num=next;
}
}
for(int i=1;i<9994;i++){
if(hits[i]==true)continue;
printf("%d\n",i);
}
}
poj3331
自然数ｎが与えられる。
ｎ！の中に出てくる数字のうち0～9までのどれか指定された数字がN!の中に何個出てくるかを数えて返す問題。
#include<stdio.h>
#include<string.h>
const int last=1300;
char nums[367][last];
void calc(int i){
int up=0,t;
for(int p=last-1;p>2;p--){
t=nums[i-1][p]*i+up%10;
nums[i][p]=t%10;
up=up/10+t/10;
}
}
void count(int num,int b){
int sp,ans=0;
for(sp=0;sp<last;sp++)if(nums[num][sp]!=0)break;
for(int p=sp;p<last;p++){
if(nums[num][p]==b)ans++;
}
printf("%d\n",ans);
}
void setData(){
memset(nums,0,sizeof(nums));
nums[1][last-1]=1;
for(int i=2;i<367;i++){
calc(i);
}
}
int main(){
setData();
int t,d,n;
scanf("%d",&t);
while(t--){
scanf("%d %d",&d,&n);
count(d,n);
}
}
poj3390
文字列を改行で区切り各行が指定された文字数に近づくように配置する問題。
よりよい区切り方は、(指定された文字数-その行の文字数)^2の計算を各行についておこない、この合計が最小になる場合が最も良い状態。
最も良い状態のスコアを出力せよという問題。
動的計画法で挑戦。
今日はサーバのメンテなのか採点してくれないらしい？
#include<stdio.h>
#include<string.h>
void setData(){
const long long max=((long long int)10000)*10000*10000;
long long int memo[2][10003],ans=max,score;
bool oks[2][10003];
int textLens[10003];
int n,m;
scanf("%d %d",&m,&n);
for(int i=0;i<n;i++)scanf("%d",&textLens[i]);
memset(memo,0,sizeof(memo));
memset(oks,false,sizeof(oks));
oks[0][0]=true;
int nowLen,nowRow,nextRow,ep=1,tenpEP=0;
for(int row=0;row<n;row++){
nowRow=row%2;
nextRow=(row+1)%2;
memset(memo[nextRow],0, sizeof(memo[nextRow]));
memset( oks[nextRow],false,sizeof(oks[nextRow]));
int count=0;
for(int sp=row;sp<ep;sp++){
if(oks[nowRow][sp]==false) continue;
if(memo[nowRow][sp]>=ans) continue;
count++;
nowLen=-1;
for(int nowP=sp;nowP<n;nowP++){
nowLen+=textLens[nowP]+1;
if(nowLen>m)break;
score=memo[nowRow][sp]+(m-nowLen)*(m-nowLen);
if(memo[nextRow][nowP+1]==0){
memo[nextRow][nowP+1]=score;
}else if(memo[nextRow][nowP+1]>score){
memo[nextRow][nowP+1]=score;
}
oks[nextRow][nowP+1]=true;
tenpEP=tenpEP>nowP+2?tenpEP:nowP+2;
}
ep=ep>tenpEP?ep:tenpEP;
if(memo[nextRow][n]!=0&&ans>memo[nextRow][n])ans=memo[nextRow][n];
}
if(count==0) break;
}
printf("%d\n",ans==max?0:ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
setData();
}
}
poj3372
車座になった生徒に時計回りに1～ｎまで番号が付いている。
先生が時計回りに回りにまわりながら生徒にキャンデーを与えていくが、最初は1番の生徒に、次は2番の生徒に、次は一人飛ばして4番の生徒に、次は2人飛ばして7番の生徒にと飛ばす人数を一人ずつ増やしながら生徒にキャンディを与えていく。
生徒の人数ｎが決まった時、全ての生徒が最低一個以上キャンディーをもらえるかを求める問題。
数式をいくらいじりまわしても理屈が分からなかったのでｎが決まった時の数列の変化をEXCELで表にしてみるとどうやら2の倍数のときのみ全生徒がキャンディをもらえる規則性を発見。
理屈が不明なので合格できるかどうかは運次第だったが幸運にもアセプトとなりました。
理屈不明で解いたのでほとんどカンニングのような解き方かもしれない、、、
#include<stdio.h>
int main(){
int n;
while(scanf("%d",&n)!=EOF){
while(n%2==0){
n/=2;
}
printf("%s\n",n==1?"YES":"NO");
}
}
poj3302
文字列を前から見て、何文字か抜き出し、後ろから見て何文字か抜き出し、抜き出した結果が指定された文字列になるかを求める問題。
前と後ろから参照して文字列の添え字を二つ使うだけで解けます。
#include<stdio.h>
#include<string.h>
bool hit(char text[101],char search[101],bool revers){
int size=strlen(text);
int sizeS=strlen(search);
int p1,p2=0;
for(int i=0;i<size;i++){
p1=revers?size-1-i:i;
if(text[p1]==search[p2]){
p2++;
if(sizeS==p2)return true;
}
}
return false;
}
int main(){
int n;
char text[102],search[102];
bool ok;
scanf("%d",&n);
while(n--){
scanf("%s %s",text,search);
ok=hit(text,search,true)||hit(text,search,false);
printf("%s\n",ok?"YES":"NO");
}
}
