1072 Rearranging Seats
#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
#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
#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
解法
まずpのうちより小さいpの倍数だと重複するのでこれを事前に削除します。
全部を足した場合を最初に考えます。
これからpの倍数をひいた場合を等差数列の式から求めます。
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
#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
この問題最悪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);
}
}
最終更新:2013年02月15日 09:24