「AOJ1071～1080」の編集履歴（バックアップ）一覧に戻る
AOJ1071～1080 - (2013/02/15 (金) 09:24:18) のソース
----
*1072 Rearranging Seats
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1072
升目に並んだ座席で特殊なルールに従った席替えが出来るか出来ないかを答える問題。
理屈はわからないが直感的に縦*横が奇数だと席替え不可能な気がしたので直観に従ってコードを書いたらアセプト。
何か15パズルで答えに行きつける場合といきつけない場合と同じ理屈があるような気がする？
#include<stdio.h>
int main(){
int r,c;
while(1){
scanf("%d %d",&r,&c);
if(r+c==0) break;
printf("%s\n",(r*c)&1==1?"no":"yes");
}
}
----
*1074 Popularity Estimation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1074
アニメキャラの出演データから各キャラのスコアを求め最もスコアの低いキャラを求める問題。
時間の範囲が狭いので力づくの方法で解ける問題。
#include<stdio.h>
#include<string>
#include<iostream>
#include<vector>
#include <algorithm>
struct chara{
std::string name;
int point,no;
bool operator<(const chara& c)const{
if(point!=c.point)return point<c.point;
return name<c.name;
}
};
bool setData(){
int n,r,t;
std::cin>>n;
if(n==0) return false;
std::vector<int> memo[31];
chara c;
std::vector<chara> charas;
for(int i=0;i<n;i++){
std::cin>>c.name>>r;
c.point=0;
c.no=i;
charas.push_back(c);
for(int j=0;j<r;j++){
std::cin>>t;
memo[t].push_back(i);
}
}
int add;
for(int i=0;i<31;i++){
add=n-memo[i].size()+1;
for(int j=0;j<memo[i].size();j++){
charas[memo[i][j]].point+=add;
}
}
std::sort(charas.begin(),charas.end());
std::cout<<charas[0].point<<" "<<charas[0].name<<"\n";
return true;
}
int main(){
while(setData()){
}
}
----
*1075 High and Low Cube
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1075
２つのさいころのデータを読み取って、どちらのさいころが大きな値を出すか判断する問題。
とにかくひたすらめんどくさいだけの悪問。
個人的に好きな問題は誰が読んでも一瞬で理解でき、柔軟な発想か奥深い原理から答えが導き出され、正解はとてもスマートでコードサイズが小さくなる。
というのが好きだし良問だと思う。
この問題はひたすらデータ作りの作業を強いるだけなのであまり面白い問題ではなかった。
#include<stdio.h>
char data[6][10][5][6];//さいころの面、数字,面データ
char base[10][5][6]={ {
".....",
".....",
".....",
".....",
"....."
},{
".....",
"...|.",
".....",
"...|.",
"..-.."
},{
"..-..",
"...|.",
"..-..",
".|...",
"..-.."},
{
"..-..",
"...|.",
"..-..",
"...|.",
"..-.."
},{
".....",
".|.|.",
"..-..",
"...|.",
"....."
},{
"..-..",
".|...",
"..-..",
"...|.",
"..-.."
},{
"..-..",
".|...",
"..-..",
".|.|.",
"..-.."
},{
"..-..",
"...|.",
".....",
"...|.",
"....."
},{
"..-..",
".|.|.",
"..-..",
".|.|.",
"..-.."
},{
"..-..",
".|.|.",
"..-..",
"...|.",
"..-.."
}
};
char xai[21][58];
void reUD(char flat1[5][6],char flat2[5][6]){
for(int j=0;j<5;j++){
for(int i=0;i<5;i++){
flat2[j][i]=flat1[4-j][i];
}
}
}
void reLR(char flat1[5][6],char flat2[5][6]){
for(int j=0;j<5;j++){
for(int i=0;i<5;i++){
flat2[j][i]=flat1[j][4-i];
}
}
}
void round270(char flat1[5][6],char flat2[5][6]){
char c;
for(int j=0;j<5;j++){
for(int i=0;i<5;i++){
c=flat1[j][i];
if(c=='-'){
c='|';
}else if(c=='|'){
c='-';
}
flat2[i][4-j]=c;
}
}
}
void round90(char flat1[5][6],char flat2[5][6]){
char c;
for(int j=0;j<5;j++){
for(int i=0;i<5;i++){
c=flat1[j][i];
if(c=='-'){
c='|';
}else if(c=='|'){
c='-';
}
flat2[4-i][j]=c;
}
}
}
int xaiCheck(int no,int x,int y){
for(int i=1;i<10;i++){
bool hit=true;
for(int dy=0;dy<5;dy++){
for(int dx=0;dx<5;dx++){
if(data[no][i][dy][dx]!=xai[y+dy][x+dx])hit=false;
}
}
if(hit==true)return i;
}
return -1000;//テスト用の異常値これがでたら大問題
}
int main(){
char temp[5][6];
for(int i=1;i<10;i++){
reLR(base[i],data[0][i]);
round90(data[0][i],data[1][i]);
reLR(base[i],data[2][i]);
round270(data[0][i],data[3][i]);
reLR(base[i],data[4][i]);
reUD(base[i],temp);
reLR(temp,data[5][i]);
}
int pys[]={1,8,8,8,8,15};
int pxs[]={8,1,8,15,22,8};
int xai1[6],xai2[6];
while(1){
for(int i=0;i<21;i++){
scanf("%s",xai[i]);
if(i==0&&xai[0][0]=='0')return 0;
}
for(int i=0;i<6;i++){
xai1[i]=xaiCheck(i,pxs[i],pys[i]);
//printf("%d ",xai1[i]);
}
//printf("\n");
for(int i=0;i<6;i++){
xai2[i]=xaiCheck(i,pxs[i]+29,pys[i]);
//printf("%d ",xai2[i]);
}
//printf("\n");
int h=0,l=0;//ハイになる場合をカウントする
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
h+=xai1[i]>xai2[j]?1:0;
l+=xai1[i]<xai2[j]?1:0;
}
}
printf("%s\n",h>=l?"HIGH":"LOW");
}
}
*1076 Time Manipulation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076
古酒をつくる魔法使い屋さんの一日の収入期待値を求める問題。
解法
まずｐのうちより小さいｐの倍数だと重複するのでこれを事前に削除します。
全部を足した場合を最初に考えます。
これからｐの倍数をひいた場合を等差数列の式から求めます。
piとpjの最小公倍数を重複してひいてるのでこれを足しなおします。
するとpi,pj,pkの最小公倍数を足し過ぎたのでこれをひいてとpの数を増やして繰り返していきます。
私はこの解法しか考えつかなかったのですが、他のかたはもっとスマートに解いているようです。
#include<stdio.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include <iomanip>
long long int GCD(long long int a, long long int b){
while( 1 ){
a = a % b;
if( a == 0 )return b;
b = b % a;
if( b == 0 )return a;
}
}
void saiki(long long int n,int no,std::vector<long long int>& ps,
long long int& sum,long double& perm,long long int mult,int count){
if(count>0){
long long int a=n/mult,b;
b=((a*(a+1))/2)*mult;
if(count%2==1){
sum-=b;
perm-=a;
}else{
sum+=b;
perm+=a;
}
}
for(int i=no;i<ps.size();i++){
saiki(n,i+1,ps,sum,perm,mult*(ps[i]/GCD(mult,ps[i])),count+1);
}
}
void setData(long long int n,int m){
long long int p,sum=0;
long double perm=0;
std::vector<long long int> v,ps;
for(int i=0;i<m;i++){
std::cin>>p;
v.push_back(p);
}
std::sort(v.begin(),v.end());
if(v[0]==1){
printf("0.0000000000\n");
return ;
}
for(int i=0;i<v.size();i++){
bool ok=true;
for(int j=0;j<i;j++){
if(v[i]%v[j]==0)ok=false;
}
if(ok==true)ps.push_back(v[i]);
}
sum=(n*(n+1))/2;
perm=n;
saiki(n,0,ps,sum,perm,1,0);
std::cout << std::setprecision(18);
//std::cout<<sum<<" "<<perm<<"\n";
std::cout << ((long double)sum)/perm<<"\n";
}
int main(){
int m;
long long int n;
while(1){
std::cin>>n>>m;
if(n==0&&m==0)break;
setData(n,m);
}
}
----
*1078 SAT-EN-3
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1078
与えられた論理式が真になる場合があるかどうかをチェックする問題。
(z And y And z)がorでつながっているという単純さを利用して超手抜きコードでアセプト。
A and V and ~AのようにＡ∧~Aという場合がなければ自動的に真になる場合があるのでこれがないかチェックするだけ。
非常に簡単な問題。
後は再帰下降構文解析みたいな真面目な手法を取らず以下に手抜きをするかだけが問題となった。
文字列の切り分けに労力の80％取られた感じ。
#include<stdio.h>
bool calc(){
char text[20],L,R,ts[3][3],k1,k2;
bool b1,b2;
bool ans=false;
scanf("%c",&L);
if(L=='#')return false;
while(scanf("%[^)]%c",text,&R)!=EOF){
//printf("<%s>",text);
sscanf(text,"%[^&]%c%[^&]%c%s",ts[0],&L,ts[1],&R,ts[2]);
//printf("(%s,%s,%s)",t1,t2,t3);
bool hit=true;
for(int i=0;i<2;i++){
if(ts[i][0]=='~'){
k1=ts[i][1];
b1=false;
}else{
k1=ts[i][0];
b1=true;
}
for(int j=i+1;j<3;j++){
if(ts[j][0]=='~'){
k2=ts[j][1];
b2=false;
}else{
k2=ts[j][0];
b2=true;
}
if(k1==k2&&b1!=b2)hit=false;
}
}
if(hit==true)ans=true;
scanf("%c",&R);
if(R=='\n')break;
scanf("%c",&L);
}
printf("%s\n",ans==true?"yes":"no");
return true;
}
int main(){
while(calc()){
}
}
*1079 Cosmic Market
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1079
コミけ会場の入り口でｒ*ｃ行列に座ってる人たちにある一行か一列に対し全員すわれ、全員立ての命令が繰り返されたとき最終的に立ってる人の数を答える問題。
この問題最悪50000行*50000列のデータを保持する必要があるため単純にシミュレートするわけにはいきません。
以下は私独自の発想ですが、ほとんどの方が1位のタイムと僅差で私も僅差だったことを考えると模範解答に近い考え方のようです。
まずある一行に注目すればどの行もその行に対する最後の命令で座った立ったで完全に上書きされます。
その後、列からの立った座った命令を受けて最終的にその行で立ってる人の数が決まる。
次に考えると列も同様にどの列もその列に対する最後の命令以外無意味なことが判明します。
となると命令を逆回しで実行すればいいと自然な発想で到達するはずです。
後はこれを素直に実装するだけです。
最後のforループは少し蛇足でした。
独自発想といっても今まで会津大学オンラインジャッジの問題を477問解いた中でカンニングして解いたのは31問。
他は全部独自発想で解いてるわけで大体毎回独自発想で解いてるわけです。
今回は解を思いつくまでの2日間特別苦労したのでちょっと特別です。
#include<stdio.h>
#include<string.h>
int as[50002],bs[50002],os[50002];//a,b,oの記録
bool rowCommit[50002],colCommit[50002];//その行か列が逆回しで確定したか
void setData(int r,int c,int q){
for(int i=0;i<q;i++){
scanf("%d %d %d",&as[i],&bs[i],&os[i]);
}
memset(rowCommit,false,sizeof(rowCommit));
memset(colCommit,false,sizeof(colCommit));
unsigned int ans=0;
int stantCol=0,downCol=0;
//逆回しに実行
for(int i=q-1;i>=0;i--){
if(as[i]==0){
//行命令
if(rowCommit[bs[i]]==true)continue;//この行は確定済み
rowCommit[bs[i]]=true;//行は確定済み
if(os[i]==0)ans+=stantCol;//座ってる状態から立ってる人を足す
else ans+=(c-downCol);//立ってる状態から座ってる状態を引く
}else{
if(colCommit[bs[i]]==true)continue;//この列は確定済み
colCommit[bs[i]]=true;//列は確定済み
if(os[i]==0)downCol++;
else stantCol++;
}
}
for(int i=0;i<r;i++){
if(rowCommit[i]==false){
ans+=stantCol;
}
}
printf("%u\n",ans);
}
int main(){
int r,c,q;
while(1){
scanf("%d %d %d",&r,&c,&q);
if(r==0&&c==0&&q==0)break;
setData(r,c,q);
}
}
