Atcoder Regular Contest #011

ARC、今回、A〜Cの問題原案を作らせていただきました。楽しんでいただけたならば幸いです。http://arc011.contest.atcoder.jp/

Writer想定解法：AとBはやるだけです。Bは結構面倒かもしれませんが。Cは文字列を比較してグラフ作ってからのDijkstraで間に合う想定で作りました。

今回のB問題、C問題の原案(私作成)の原案は「不思議の国の論理学」(ルイス・キャロル著, 柳瀬 尚紀訳,2005, ちくま学芸文庫)を元にしています。興味のある方はご一読ください。 

今回のA問題は、「頭の体操」シリーズの煙草の問題。煙草の吸殻3本から煙草1本を作る男が17本の煙草を持ってる時に何本吸えるか、という問題を元にしています。私が文具が好きであることから、鉛筆に変えてみました。

以下、Writer解です。ソースやアルゴリズムが下手なのはご容赦ください。

[A.鉛筆リサイクルの新技術]
#include<stdio.h>

int main(void){

  unsigned int m,n,honsu,hanbai=0,kaishu=0;

  scanf("%u %u %u",&m,&n,&honsu);

  hanbai=honsu;

  do{

    kaishu+=honsu;

    honsu=(kaishu/m)*n;

    kaishu%=m;

    hanbai+=honsu;

  }while(honsu>0);

  printf("%u\n",hanbai);

  return 0;

}

[B.ルイス・キャロルの記憶術]

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int trans(char c);

int main(void){
  int n,i,j,l,flg=0,c,count,wc=0;
  char word[32];
  scanf("%d%*c",&n);
  for(i=0;i<n;i++){
    scanf("%30s%*c",word);
    l=strlen(word);
    for(j=count=0;j<l;j++){
      if((c=trans(word[j]))==-1) continue;
      if(flg) putchar(' '+(flg=0));
      putchar('0'+c);
      count++;
    }
    wc+=(count?1:0);
    flg=(wc?1:0);
  }
  putchar('\n');
  return 0;
}

int trans(char c){
  char * p;
  const char *str="zrbcdwtjfqlvsxpmhkng";
  c=tolower(c);
  if((p=strchr(str,c))==NULL) return -1;
  return (p-str)/2;
}

[C.ダブレット]
#include<stdio.h>

#include<string.h>

short root[1002];

char word[1002][32];

int chkword(char *str1,char *str2,int len);

void printroot(int num);

int main(void){

  int i,j,k,l,n,tmp;

  char graph[1002][1002];

  short dist[1002];

  scanf("%32s%*c%32s%*c%d%*c",word[0],word[1],&n);

  l=strlen(word[0]);

  for(i=2;i<=n+1;i++) scanf("%32s%*c",word[i]);

  for(i=0;i<=n+1;i++) graph[i][i]=0;

  for(i=0;i<n+1;i++){

    for(j=i+1;j<=n+1;j++){

      tmp=chkword(word[i],word[j],l);

      if(tmp<2) graph[i][j]=graph[j][i]=tmp;

      else graph[i][j]=graph[j][i]=-1;

    }

  }

  

  for(i=1,dist[0]=0;i<=n+1;i++) dist[i]=10000;

  memset(root,-1,sizeof(root));

  

  for(i=0;i<=n+1;i++){

    for(j=0;j<=n+1;j++){

      if(dist[j]==i){

for(k=0;k<=n+1;k++){

 if(graph[j][k]==1 && dist[k]>i+1) dist[k]=i+1,root[k]=j;

 else if(graph[j][k]==0 && dist[k]>i) dist[k]=i,root[k]=j;

}

      }

    }

    if(dist[1]!=10000) break;

  }

  if(dist[1]>=1) printf("%d\n",dist[1]!=10000?dist[1]-1:-1);

  else puts("0");

  if(dist[1]!=10000) printroot(1);

  return 0;

}

int chkword(char *str1,char *str2,int len){

  int i,check=0;

  for(i=0;i<len;i++) check+=(str1[i]!=str2[i]);

  return check;

}

void printroot(int num){

  if(num) printroot(root[num]); 

  puts(word[num]);

}