「AOJ2031～2040」の編集履歴（バックアップ）一覧に戻る
AOJ2031～2040 - (2013/04/22 (月) 12:09:21) のソース
*2031 Hyper Rock-Scissors-Paper
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2031
最大１０００人で15種類の手のあるじゃんけんを行う。
各人の出した手が与えられるので勝利した手を答えよ。
アイコの場合Drawと答えよ。
解法
全員同じ手の場合アイコになることに気づきさえすれば簡単な問題です。
ある手が勝っているとは、その手に勝ってる手が一つもないということでそれを検証するだけです。
勝ってる手がいなければアイコとなります。
#include<stdio.h>
#include<string>
#include<map>
#include<set>
#include<iostream>
std::string text[15]={"Rock","Fire","Scissors","Snake","Human","Tree","Wolf","Sponge","Paper","Air","Water","Dragon","Devil","Lightning","Gun"};
std::map<std::string,int> toNum;
void check(int n){
int hit[15]={0};
std::string str;
for(int i=0;i<n;i++){
std::cin>>str;
hit[toNum[str]]=1;
}
int sum=0;
for(int i=0;i<15;i++){
sum+=hit[i];
}
if(sum==1){
printf("Draw\n");
return ;
}
for(int i=0;i<15;i++){
if(hit[i]==0)continue;
bool ok=true;
for(int j=1;j<=7;j++){
if(hit[(i+15-j)%15]==1){
ok=false;
}
}
if(ok==true){
std::cout<<text[i]<<"\n";
return ;
}
}
printf("Draw\n");
}
int main(){
for(int i=0;i<15;i++){
toNum[text[i]]=i;
}
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
check(n);
}
}
*2035 It Prefokery Pio
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2035
2000文字までの単語が与えられるのでこの中から文字の並び順を変えずに文字を抜き出して最長の回文を作るときできる回文を答えよという問題。
可能な答えのうちどれを答えてもよい。
解法
文字列の添え字を左を固定して右端から左へ向かって調べていきます。
Ａ 最初に１文字目と右の文字２文字か一文字が決まりこの文字の長さと文字列をメモします。
左を一つ動かして右端から調べるとＡでメモった文字列に文字を足す場合だけを上手く選別できるのでこれを更新していくだけです。
紙と鉛筆があればまだ説明できるのですが、直感的に解いてしまったためにうまく他人に説明できない状態です。
他人に伝えるという国語力の大事さを実感します。
速度より実装の簡便さを重視してstd::stringを使ったためコード実行速度はそこそこ18/52位でした。
#include<stdio.h>
#include<string>
#include<string.h>
void calc(char text[2001],int len){
std::string memo[2001],nowText;
int lenMemo[2001]={0},nowLen,ansLen=0;
bool addOK;
for(int pL=0;pL<len;pL++){
nowText="";
nowLen=0;
addOK=true;
for(int pR=len-1;pR>=pL;pR--){
if(addOK==true){
if(pR==pL){
nowText+=text[pL];
nowLen+=1;
}else if(text[pL]==text[pR]){
nowText+=text[pL];
nowLen+=2;
}
addOK=false;
}
if(nowLen<=lenMemo[pR]){
nowText=memo[pR];
nowLen=lenMemo[pR];
addOK=true;
}else{
memo[pR]=nowText;
lenMemo[pR]=nowLen;
}
}
}
int ansNo=0;
for(int i=0;i<len;i++){
if(ansLen<lenMemo[i]){
ansLen=lenMemo[i];
ansNo=i;
}
}
printf("%s",memo[ansNo].c_str());
for(int i=memo[ansNo].size()-1-ansLen%2;i>=0;i--){
printf("%c",memo[ansNo][i]);
}
printf("\n");
}
int main(){
char text[2001];
while(scanf("%s",text)!=EOF){
calc(text,strlen(text));
}
}
*2039 Space Coconut Crab II
三角形の周長Ｌが整数で与えられるので周長Ｌかつ三辺が全部素数になる三角形の数を答えよという問題。
周長は30000までとする。
解法
賢い方法を思いつきません。
素数表を求め全探索してみました。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
const int up=30010;
std::vector<int> sosuu;
bool so[up+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
int table[up]={0};
int main(){
setSo();
std::vector<int>::iterator itA,itB,itC,itU;
for(itA=sosuu.begin();itA!=sosuu.end();itA++){
int a=(*itA);
for(itB=itA;itB!=sosuu.end();itB++){
int b=(*itB);
itU=std::lower_bound(sosuu.begin(),sosuu.end(),b+a);
for(itC=itB;itC!=itU;itC++){
int c=(*itC);
if(a+b+c>=up||a+b<=c)break;
table[a+b+c]++;
}
}
}
int t;
while(1){
scanf("%d",&t);
if(t==0)break;
printf("%d\n",table[t]);
}
}
