「AOJ再挑戦問25～30」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦問25～30」(2014/01/11 (土) 11:25:09) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問25 Hit and Blow
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0025
2人ゲーム Hit&Blowの判定をする問題。
解法
同じ数字がないので4*4検証して同じ数ならHitかBlowしかありません。
同じ場所でないならBlowです、同じ場所ならHitです。
同じ数字が許容されるとこの問題判定が少し難しくなりますね。
#include<stdio.h>
int main(){
int as[4],bs[4];
while(scanf("%d %d %d %d",&as[0],&as[1],&as[2],&as[3])!=EOF){
scanf("%d %d %d %d",&bs[0],&bs[1],&bs[2],&bs[3]);
int hit=0;
int blow=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(i!=j){
blow+=(as[i]==bs[j]);
}else{
hit+=(as[i]==bs[j]);
}
}
}
printf("%d %d\n",hit,blow);
}
}
*問26 Dropping Ink
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0026
ペーパーにインクを落とした後の結果をこたえる問題。
解法
そのままシミュレートします。
ペーパー上下左右をそれぞれ２マスを大きくして実際に垂らしたポイントをx+2,y+2とし、２～11マス目までを集計する事で外側判定処理を省いています。
#include<stdio.h>
#include<string.h>
int paper[15][15];
const int slide=2;
void small(int x,int y){
paper[x+1][y]++;
paper[x][y+1]++;
paper[x-1][y]++;
paper[x][y-1]++;
paper[x][y]++;
}
void middle(int x,int y){
paper[x+1][y+1]++;
paper[x+1][y-1]++;
paper[x-1][y+1]++;
paper[x-1][y-1]++;
small(x,y);
}
void big(int x,int y){
paper[x+2][y]++;
paper[x][y+2]++;
paper[x-2][y]++;
paper[x][y-2]++;
middle(x,y);
}
int main(){
memset(paper,0,sizeof(paper));
int x,y,s;
while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
x+=slide;
y+=slide;
if(s==3)big(x,y);
if(s==2)middle(x,y);
if(s==1)small(x,y);
}
int ansA=0,ansB=0;
for(int x=0;x<10;x++){
int x1=x+slide;
for(int y=0;y<10;y++){
int y1=y+slide;
if(paper[x1][y1]>ansB)ansB=paper[x1][y1];
if(paper[x1][y1]==0)ansA++;
}
}
printf("%d\n%d\n",ansA,ansB);
}
*問27 What day is today?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0027
曜日判定をする問題。
解法
ツェラーの公式で一発です。
#include<stdio.h>
char weeks[7][10]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
int getWeekday(int nYear, int nMonth, int nDay)
{
//ツェラーの公式という有名な曜日判定プログラム
int nWeekday, nTmp;
if (nMonth == 1 || nMonth == 2) {
nYear--;
nMonth += 12;
}
nTmp = nYear/100;
nWeekday = (nYear + (nYear >> 2) - nTmp + (nTmp >> 2) + (13*nMonth + 8)/5 + nDay) % 7;
return nWeekday;
}
int main(){
while(1){
int m,d;
scanf("%d %d",&m,&d);
if(m==0&&d==0)break;
printf("%s\n",weeks[getWeekday(2004,m,d)]);
}
}
*問28 Mode Value
1～100までの数の書かれたデータをカウントして、最頻値を出力する問題。
解法
範囲が決まっているので配列でカウントして最頻値の出現回数を更新。
最頻値と同じ数だけ出た数を全て出力すれば答え。
#include<stdio.h>
int main(){
int memo[101]={0};
int n,max=0;
while(scanf("%d",&n)!=EOF){
memo[n]++;
if(max<memo[n])max=memo[n];
}
for(int i=1;i<=100;i++){
if(max==memo[i])printf("%d\n",i);
}
}
*問29 English Sentence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0029
単語の出現頻度を数えて最頻する単語と一番長い単語の二つをこたえる問題。
解法
出現範囲があやふやなのでstd::mapで集計しますが原理は問28と同じです。
カウントしてカウントが今までの記録を更新したらその単語と回数で記録を更新。
一番長い単語が出たら更新。
それだけ。
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
int main(){
std::map<std::string,int> memo;
std::string word,ansLongStr,ansCountStr;
int maxCount=0,maxLen=0;
while(std::cin.eof()==false){
std::cin>>word;
if(memo.find(word)==memo.end())memo[word]=0;
memo[word]++;
if(word.size()>maxLen){
maxLen=word.size();
ansLongStr=word;
}
if(memo[word]>maxCount){
maxCount=memo[word];
ansCountStr=word;
}
}
std::cout<<ansCountStr<<" "<<ansLongStr<<"\n";
}
*問30 Sum of Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030
0～9までの数字ｎ個を重複なく組み合わせて和をとるとき指定された数ｓを作る方法は何通りか？
足す順番が違うだけのものは同じとみなして計算せよ。
解法
動的計画法で解けば計算量は大雑把にって10*55*50=25000回程度です。
n sの組のうちｓが100までという構成できない値を聞いてくるのがこの問題のひっかけなのでそこだけ注意。
あとは何も考えない動的計画法で解けます。
i個めまで数字を使ったとき、i+1個めはi個めまでに使った数より大きなものをとるという条件で計算するだけです。
#include<stdio.h>
#include<string.h>
int main(){
int memo[11][10][101];//memo[数字の個数][数字の最高値][数字の合計値]
int ans[11][101];
memset(memo,0,sizeof(memo));
memset(ans,0,sizeof(ans));
memo[0][0][0]=1;
for(int i=1;i<=10;i++){
for(int j=0;j<=9;j++){
int t=j;
if(i==1&&j==0)t=-1;
for(int k=t+1;k<=9;k++){
for(int sum=45-k;sum>=0;sum--){
memo[i][k][sum+k]+=memo[i-1][j][sum];
}
}
}
for(int sum=0;sum<=45;sum++){
for(int j=0;j<=9;j++){
ans[i][sum]+=memo[i][j][sum];
}
}
}
int n,s;
while(scanf("%d %d",&n,&s)!=EOF){
if(n==0&&s==0)break;
printf("%d\n",ans[n][s]);
}
}
*問25 Hit and Blow
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0025
2人ゲーム Hit&Blowの判定をする問題。
解法
同じ数字がないので4*4検証して同じ数ならHitかBlowしかありません。
同じ場所でないならBlowです、同じ場所ならHitです。
同じ数字が許容されるとこの問題判定が少し難しくなりますね。
#include<stdio.h>
int main(){
int as[4],bs[4];
while(scanf("%d %d %d %d",&as[0],&as[1],&as[2],&as[3])!=EOF){
scanf("%d %d %d %d",&bs[0],&bs[1],&bs[2],&bs[3]);
int hit=0;
int blow=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(i!=j){
blow+=(as[i]==bs[j]);
}else{
hit+=(as[i]==bs[j]);
}
}
}
printf("%d %d\n",hit,blow);
}
}
*問26 Dropping Ink
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0026
ペーパーにインクを落とした後の結果をこたえる問題。
解法
そのままシミュレートします。
ペーパー上下左右をそれぞれ２マスを大きくして実際に垂らしたポイントをx+2,y+2とし、２～11マス目までを集計する事で外側判定処理を省いています。
#include<stdio.h>
#include<string.h>
int paper[15][15];
const int slide=2;
void small(int x,int y){
paper[x+1][y]++;
paper[x][y+1]++;
paper[x-1][y]++;
paper[x][y-1]++;
paper[x][y]++;
}
void middle(int x,int y){
paper[x+1][y+1]++;
paper[x+1][y-1]++;
paper[x-1][y+1]++;
paper[x-1][y-1]++;
small(x,y);
}
void big(int x,int y){
paper[x+2][y]++;
paper[x][y+2]++;
paper[x-2][y]++;
paper[x][y-2]++;
middle(x,y);
}
int main(){
memset(paper,0,sizeof(paper));
int x,y,s;
while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
x+=slide;
y+=slide;
if(s==3)big(x,y);
if(s==2)middle(x,y);
if(s==1)small(x,y);
}
int ansA=0,ansB=0;
for(int x=0;x<10;x++){
int x1=x+slide;
for(int y=0;y<10;y++){
int y1=y+slide;
if(paper[x1][y1]>ansB)ansB=paper[x1][y1];
if(paper[x1][y1]==0)ansA++;
}
}
printf("%d\n%d\n",ansA,ansB);
}
*問27 What day is today?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0027
曜日判定をする問題。
解法
ツェラーの公式で一発です。
#include<stdio.h>
char weeks[7][10]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
int getWeekday(int nYear, int nMonth, int nDay)
{
//ツェラーの公式という有名な曜日判定プログラム
int nWeekday, nTmp;
if (nMonth == 1 || nMonth == 2) {
nYear--;
nMonth += 12;
}
nTmp = nYear/100;
nWeekday = (nYear + (nYear >> 2) - nTmp + (nTmp >> 2) + (13*nMonth + 8)/5 + nDay) % 7;
return nWeekday;
}
int main(){
while(1){
int m,d;
scanf("%d %d",&m,&d);
if(m==0&&d==0)break;
printf("%s\n",weeks[getWeekday(2004,m,d)]);
}
}
*問28 Mode Value
1～100までの数の書かれたデータをカウントして、最頻値を出力する問題。
解法
範囲が決まっているので配列でカウントして最頻値の出現回数を更新。
最頻値と同じ数だけ出た数を全て出力すれば答え。
#include<stdio.h>
int main(){
int memo[101]={0};
int n,max=0;
while(scanf("%d",&n)!=EOF){
memo[n]++;
if(max<memo[n])max=memo[n];
}
for(int i=1;i<=100;i++){
if(max==memo[i])printf("%d\n",i);
}
}
*問29 English Sentence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0029
単語の出現頻度を数えて最頻する単語と一番長い単語の二つをこたえる問題。
解法
出現範囲があやふやなのでstd::mapで集計しますが原理は問28と同じです。
カウントしてカウントが今までの記録を更新したらその単語と回数で記録を更新。
一番長い単語が出たら更新。
それだけ。
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
int main(){
std::map<std::string,int> memo;
std::string word,ansLongStr,ansCountStr;
int maxCount=0,maxLen=0;
while(std::cin.eof()==false){
std::cin>>word;
if(memo.find(word)==memo.end())memo[word]=0;
memo[word]++;
if(word.size()>maxLen){
maxLen=word.size();
ansLongStr=word;
}
if(memo[word]>maxCount){
maxCount=memo[word];
ansCountStr=word;
}
}
std::cout<<ansCountStr<<" "<<ansLongStr<<"\n";
}
*問30 Sum of Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030
0～9までの数字ｎ個を重複なく組み合わせて和をとるとき指定された数ｓを作る方法は何通りか？
足す順番が違うだけのものは同じとみなして計算せよ。
解法
動的計画法で解けば計算量は大雑把にって10*(55*50+45*10)=30000回程度です。
n sの組のうちｓが100までという構成できない値を聞いてくるのがこの問題のひっかけなのでそこだけ注意。
あとは何も考えない動的計画法で解けます。
i個めまで数字を使ったとき、i+1個めはi個めまでに使った数より大きなものをとるという条件で計算するだけです。
#include<stdio.h>
#include<string.h>
int main(){
int memo[11][10][101];//memo[数字の個数][数字の最高値][数字の合計値]
int ans[11][101];
memset(memo,0,sizeof(memo));
memset(ans,0,sizeof(ans));
memo[0][0][0]=1;
for(int i=1;i<=10;i++){
for(int j=0;j<=9;j++){
int t=j;
if(i==1&&j==0)t=-1;
for(int k=t+1;k<=9;k++){
for(int sum=45-k;sum>=0;sum--){
memo[i][k][sum+k]+=memo[i-1][j][sum];
}
}
}
for(int sum=0;sum<=45;sum++){
for(int j=0;j<=9;j++){
ans[i][sum]+=memo[i][j][sum];
}
}
}
int n,s;
while(scanf("%d %d",&n,&s)!=EOF){
if(n==0&&s==0)break;
printf("%d\n",ans[n][s]);
}
}
