「AOJ0111～120」の編集履歴（バックアップ）一覧に戻る
AOJ0111～120 - (2013/03/09 (土) 05:22:12) のソース
*0111 Doctor's Memorable Codes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0111
文字列をコード表に対応して変換せよという問題。
解法
丁寧に変換表を記述してみました。
変換表に規則性があるらしくコードを短くする方法もあるようですが私にはわかりませんでした。
#include<iostream>
#include<map>
#include<string>
using namespace std;
map<char,string> e;
map<string,char> d;
std::string noToCode(int no){
std::string ans="01234";
for(int i=0;i<5;i++){
ans[4-i]=no%2+'0';
no=no/2;
}
return ans;
}
void setMap(){
for(int i=0;i<26;i++){
e['A'+i]=noToCode(i);
}
e[' '] = "11010";
e['.'] = "11011";
e[','] = "11100";
e['-'] = "11101";
e['\'']= "11110";
e['?'] = "11111";
d["101"] = ' ';
d["000000"] = '\'';
d["000011"] = ',';
d["10010001"] = '-';
d["010001"] = '.';
d["000001"] = '?';
d["100101"] = 'A';
d["10011010"] = 'B';
d["0101"] = 'C';
d["0001"] = 'D';
d["110"] = 'E';
d["01001"] = 'F';
d["10011011"] = 'G';
d["010000"] = 'H';
d["0111"] = 'I';
d["10011000"] = 'J';
d["0110"] = 'K';
d["00100"] = 'L';
d["10011001"] = 'M';
d["10011110"] = 'N';
d["00101"] = 'O';
d["111"] = 'P';
d["10011111"] = 'Q';
d["1000"] = 'R';
d["00110"] = 'S';
d["00111"] = 'T';
d["10011100"] = 'U';
d["10011101"] = 'V';
d["000010"] = 'W';
d["10010010"] = 'X';
d["10010011"] = 'Y';
d["10010000"] = 'Z';
}
int main(){
setMap();
string line,put1,ans;
int p,k,size;
while(getline(cin,line)){
put1="";
for(int i=0;i<line.size();i++){
put1.append(e[line[i]]);
}
ans="";
p=0;
size=put1.size();
while(p<size){
for(int k=3;k<9;k++){
if(p+k>size){
p=size;
break;
}
line=put1.substr(p,k);
if(d.find(line)!=d.end()){
ans+=d[line];
p=p+k-1;
break;
}
}
p++;
}
cout<<ans<<"\n";
}
}
----
*0112 A Milk Shop
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0112
ミルク販売店の前に列ができています。
お客さんごとの接客時間が与えられます。
全てのお客さんの待ち時間の総計が最小になるように客に並んでもらった時、その最小値を表示せよという問題。
解法
long long intを使わないとintだとあふれるということにさえ注意すれば中学生でも解ける問題です。
気楽に解きましょう。
#include <algorithm>
#include <iostream>
long long int t[10001];
void calc(int n){
long long int ans=0;
for(int i=0;i<n;i++){
std::cin>>t[i];
}
std::sort(t,t+n);
for(int i=0;i<n;i++){
ans+=t[i]*(n-i-1);
}
std::cout<<ans<<"\n";
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
----
*0113 Period
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113
2 つの正の整数 p, q を入力し、 p / q を小数として正確に表現する問題です。
解法
循環小数の場合一行下に循環する部分を表示する必要があります。
小学生の筆算と同じ手法で解きます。
#include<stdio.h>
#include<map>
void calc(int p,int q){
std::map<int,int> memo;
int t,i=0;
memo[p]=-1;
while(1){
p*=10;
t=(p/q)%10;
p=p%q;
if(p==0){
printf("%d\n",t);
return;
}else if(memo.find(p)==memo.end()){
printf("%d",t);
memo[p]=i;
}else{
printf("%d\n",t);
break;
}
i++;
}
for(q=0;q<=i;q++){
printf("%c",q<=memo[p]?' ':'^');
}
printf("\n");
}
int main(){
int p,q;
while(scanf("%d %d",&p,&q)!=EOF){
calc(p,q);
}
}
----
*0114 Electro-Fly
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114
x= a1x mod m1
y= a2y mod m2
z= a3z mod m3
で与えられる数列があります、aとｍの数値が与えられますので。
x,y,zが1から出発し全ての数が1に戻ってくる最小回数を求めよという問題です。
解法
ｘ、ｙ、ｚそれぞれが1に戻るまでの最小回数を求めます。
答えはｘ、ｙ、ｚともに揃う時なので、最小回数の最小公倍数を求めます。
intだと桁あふれが起こるのでlong long intを使う点に注意すれば簡単な問題です。
#include <iostream>
#include<stdio.h>
long long int gcd(long long int a, long long int b)
{
long long int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
long long int re(long long int x,long long int m){
long long int ans=1,t=x%m;
while(t!=1){
t=(t*x)%m;
ans++;
}
return ans;
}
int main(){
long long int a1,a2,a3,m1,m2,m3,t,n1,n2,n3,c;
while(1){
std::cin>>a1>>m1>>a2>>m2>>a3>>m3;
if(a1==0) break;
n1=re(a1,m1);
n2=re(a2,m2);
n3=re(a3,m3);
c=n1*(n2/gcd(n1,n2));
c=c*(n3/gcd(n3,c));
std::cout<<c<<"\n";
}
}
----
*0116 Rectangular Searching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116
枡目で区切られた図の中から最大の長方形を探せという問題です。
解法
一段ずつ何段連続で.が続いたかを記録し、記録した内容の各点から両側に長方形を伸ばして作れる最大の長方形を調べます。
このコードはn^2の計算量ですが漸化式を使い線形的に計算する方法もあるようです。
#include<stdio.h>
#include<string.h>
int map[2][503];
char row[503];
void setMap(int h,int w){
char t;
int lp,rp,cp,sum,max=0,up,y;
memset(map,0,2*503*4);
for(int i=0;i<h;i++){
y=i%2;
up=(i+1)%2;
scanf("%s",row);
for(int x=0;x<w;x++){
map[y][x+1]=row[x]=='.'?map[up][x+1]+1:0;
}
for(int x=1;x<=w;x++){
if(map[y][x]!=0){
cp=map[y][x];
lp=rp=0;
while(map[y][x-lp-1]>=cp) lp++;
while(map[y][x+rp+1]>=cp) rp++;
sum=cp*(rp+lp+1);
max=max<sum ? sum:max;
}
}
}
printf("%d\n",max);
}
int main()
{
int w,h;
scanf("%d %d",&h,&w);
while(h!=0 && w!=0){
setMap(h,w);
scanf("%d %d",&h,&w);
}
}
----
*0117 A reward for a Carpenter
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117
大工が町から出発して建材のある町で建材をうけとり、町にかえるまでのコストを最小化せよという問題。
グラフの問題です。
解法
サイズが小さいので最も素朴なダイクストラで解くことができます。
ダイクストラ法を丁寧に実装するだけです。
#include<stdio.h>
int max=1000000000;
int g[21][21];
int Dijkstras(int start,int goal,int n){
int cost[21],flag[21]={0},p,min;
for(int i=1;i<=n;i++){
cost[i]=max;
flag[i]=0;
}
cost[start]=0;
while(1){
min=max;
p=-1;
for(int i=1;i<=n;i++){
if(cost[i]<min && flag[i]==0){
min=cost[i];
p=i;
}
}
if(p==-1) break;
flag[p]=1;
for(int j=1;j<=n;j++){
if(g[p][j]+cost[p]<cost[j]){
cost[j]=g[p][j]+cost[p];
}
}
}
return cost[goal];
}
int main(){
int n,m,a1,b1,c1,d1,x1,x2,y1,y2;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=max;
}
}
for(int i=0;i<m;i++){
scanf("%d,%d,%d,%d",&a1,&b1,&c1,&d1);
g[a1][b1]=c1;
g[b1][a1]=d1;
}
scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
int ans=y1-y2-Dijkstras(x1,x2,n)-Dijkstras(x2,x1,n);
printf("%d\n",ans);
}
----
*0118 Property Distribution
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118
枡目で区切られた果樹園の地図を区画分けせよという問題。
解法
マップサイズが小さいので再帰探索で十分に解けます。
新しいエリアを見つけたら、そこからたどれる全ての地点を再帰でたどるだけです。
#include<stdio.h>
char map[101][101];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
int h,w;
void saiki(int x,int y,char t){
int nx,ny;
map[y][x]='.';
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(nx<0 || w<=nx || ny<0 || h<=ny || map[ny][nx]!=t) continue;
saiki(nx,ny,t);
}
}
void calc(){
for(int i=0;i<h;i++){
scanf("%s",map[i]);
}
int count=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(map[i][j]!='.'){
count++;
saiki(j,i,map[i][j]);
}
}
}
printf("%d\n",count);
}
int main(){
while(1){
scanf("%d %d",&h,&w);
if(w==0 && h==0) break;
calc();
}
}
----
*0119 Taro's Obsession
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119
部屋に入った順番の証言からありうる順番を一つだけ挙げる問題。
証言と矛盾がなければどんな答えを出力しても良い。
解法
こんな簡単な問題なら頭にグラフを思い浮かべれば10分で解けます。
グラフ化すると最後に入った人の後には誰も入ってないのでまずはその人が最後と判明します。
するとその最後に入った人をグラフから消去するとその人の直前に入った人が最後に入った人になります。
これを繰り返していけば簡単に答えがでコードサイズ491バイトとコードサイズで2位を取れました。
がこの問題をコードサイズ165byteという変態コードでクリアしてる人がいました。
どんなコードを書いたのやらもはや尊敬するレベルです。
#include<stdio.h>
#include<set>
#include<vector>
std::set<int> G[21];
std::vector<int> ans;
int spents[21]={0};
int main(){
int m,n,x,y;
scanf("%d %d",&m,&n);
for(int i=0;i<n;i++){
scanf("%d %d",&x,&y);
G[x].insert(y);
}
for(int i=0;i<m;i++){
int no=-1;
for(int j=1;j<=m;j++){
if(G[j].empty()==true&&spents[j]==0){
no=j;
spents[j]=1;
break;
}
}
ans.push_back(no);
for(int j=1;j<=m;j++)G[j].erase(no);
}
for(int i=m-1;i>=0;i--)printf("%d\n",ans[i]);
}
----
*0120 Patisserie
ｎ個のケーキを箱に詰められるかを答える問題。
箱に詰められるならＯＫ、詰められないならＮＡと答えます。
解法
動的計画法で解きます。
左からケーキを詰めていきます。
この時今まで入れたケーキの組を1bit単位で管理し、一番右端のケーキの番号をmemo[13]に割り当てて探索します。
計算の途中入れた順番が違うだけで同じケーキの組になっている組み合わせを比べ、一番詰め込めている組み合わせのみを残すことで計算量を下げます。
#include<stdio.h>
#include<map>
#include<math.h>
void calc(int n,double wide,double size[13]){
std::map<int,double> memo[13];
std::map<int,double> next[13];
std::map<int,double>::iterator it;
double sizeMemo[13][13];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sizeMemo[i][j]=sqrt((size[i]+size[j])*(size[i]+size[j])-(size[i]-size[j])*(size[i]-size[j]));
}
}
for(int i=0;i<n;i++){
memo[i][int(1<<i)]=size[i];
}
int state;
double len;
for(int i=1;i<n;i++){
for(int j=0;j<n;j++){
it=memo[j].begin();
while(it!=memo[j].end()){
for(int k=0;k<n;k++){
if((((*it).first)&(1<<k))==0){
state=(*it).first|(1<<k);
len=(*it).second+sizeMemo[j][k];
if(next[k].find(state)==next[k].end()){
next[k][state]=len;
}else if(next[k][state]>len){
next[k][state]=len;
}
}
}
it++;
}
}
for(int j=0;j<n;j++){
memo[j].clear();
memo[j].insert(next[j].begin(),next[j].end());
next[j].clear();
}
}
for(int i=0;i<n;i++){
it=memo[i].begin();
if(wide-size[i]-(*it).second>=0){
printf("OK\n");
return ;
}
}
printf("NA\n");
}
int main(){
double wide,size[13];
int i;
char t;
while(scanf("%lf",&wide)!=EOF){
i=0;
t=' ';
while(t!='\n'){
scanf("%lf%c",&size[i],&t);
i++;
}
calc(i,wide,size);
}
}
