AtCoder: Tenka1 Programmer Beginner Contest 2019 -A,B,C

AtCoder

目次

はじめに

ブログ主の競技プログラミング歴→８ヶ月くらい

書こうと思った動機：
せっかくブログを開設したんだし何か手軽にアウトプットできるものないかなと探したところ、競プロの自分が解けた問題をどのように解いたのかをとりあえず書き出そうと思い、今書いている。(まだ未熟なので計算量などの考察についてはおいおいしていくつもり)


A問題　問題概要

数直線上の点1,2,3にそれぞれ座標A,B,Cが入力として与えられ、点1から点2に行くときに点3を通れば' Yes '、通らなければ' No 'を出力しろ

制約

・0≤A,B,C≤100
・A,B,Cは相異なる整数

考えたこと

数直線上での各点の関係が小さい方から
1->3->2 or 2->3->1
の順になっていれば点3によることができるので

1<3<2 or 2<3<1　なら' Yes '、他なら' No 'を出力

コード

#include<stdio.h>

int main(void){
  int a,b,c;

  scanf("%d %d %d",&a,&b,&c);
  if((a<c && c<b) || (b<c && c<a)){
    printf("Yes\n");
  }else{
    printf("No\n");
  }

  return 0;
}



B問題　問題概要

英小文字からなる長さNの文字列Sと整数Kが与えられるので、文字列Sの中でK番目の文字と異なる文字を' * 'に置き換えて出力しろ

制約

・1≤K≤N≤10
・Sは英小文字からなる長さNの文字列
・N,Kは整数

考えたこと

K番目の文字をどこかに格納して、文字列の１文字１文字と比較してその都度' * 'に置き換え、その後文字列を出力すればいけそう

コード

#include<stdio.h>

int main(void){
  int n,k,i;
  char target;   //k番目の文字列を格納する変数

  scanf("%d",&n);

  char s[n];

  scanf("%s",s);
  scanf("%d",&k);

  target = s[k-1];   //配列は0から数えるので添え字はk-1

  for(i=0;i<n;i++){
    if(s[i]!=target){
      s[i] = '*';
    }
  }

  printf("%s",s);

  return 0;
}



C問題　問題概要

N個の白か黒の石が一列に並んでいる。
石の状態は長さNの文字列Sであらわされ、白の時は' . '、黒の時は' # '。
黒い石のすぐ右に白い石が来ないように色を0回以上変更する。
変更した回数の最小値を出力しろ。

制約

・1≤N≤2×105
・Sは英小文字からなる長さNの文字列
・N,Kは整数

考えたこと

まず、黒い石のすぐ右側に白い石を置けないので作る白黒の列は
白白白白白(すべて白)
黒黒黒黒黒(すべて黒)
白白白黒黒(白黒はっきり分かれる)
の３種類だなと考えた。

次に、どうやってこの白黒の列を実現するかを考える。
左から順に石を見ていって、今見ている石の左側の黒い石と右側の白い石の数をそれぞれ数え、合計し、最小のが答えになる。

ただ、左から見ていく際に一回一回その場で左右の白黒をカウントしていては計算量が多く(多分)、時間がかかる。

そこで、先にそれぞれについてカウントして配列として持っておく累積和というものを使う。(説明するの難しいのでコードみてちょ)

コード

#include<stdio.h>

//a,bの小さい方を返す関数
int min(int a,int b){
  if(a>b) return b;
  return a;
}

int main(void){
  int n,i,tmp,ans=100000;

  scanf("%d",&n);
  
  char s[n];
/*
   a[n]->見ている石(左からi番目)からそれを含め左に何個黒があるかa[i]
   b[n]->見ている石からそれを含め右に何個白があるかb[i]
*/
  int a[n],b[n]; 

  //初期化
  for(i=0;i<n;i++){
    a[i]=0;
    b[i]=0;
  }
  
  scanf("%s",s);
  
  if(s[0]=='#') a[0]=1;   //一番左が黒なら1
  if(s[n-1]=='.') b[n-1]=1;   //一番右が白なら1
  
  for(i=1;i<n;i++){
    if(s[i]=='#') a[i]=a[i-1]+1;   //i番目が黒なら+1
    else a[i]=a[i-1];   //i番目が黒でないならそのままの値を代入
    if(s[n-1-i]=='.') b[n-1-i]=b[n-i]+1;   //i番目が白なら+1
    else b[n-1-i]=b[n-i];   //i番目が白でないならそのままの値を代入
  }
  
  for(i=0;i<n;i++) ans=min(ans,a[i]+b[i]-1);   //-1しているのは自分の分を引いている
  
  printf("%d\n",ans);
  
  return 0;
}

累積和を行っている部分は

if(s[i]=='#'){
  a[i]=a[i-1]+1;
  b[n-1-i]=b[n-i]+1;
}else{
  a[i]=a[i-1];
  b[n-1-i]=b[n-i];
}

とも書けるかもしれない

黒は左から、白は右から数えたので配列a,bの累積和もそれぞれ
aは1->n-1
bはn-2->0
へ伸びている

読みにくいかもしれない(自分はそのまんまなのでこちらが読みやすいと思っている)


おわりに

競技プログラミングの初記事だったので自身との関連をはじめに長々と書いてしまったがこれからはないので安心してほしい。
以前のABC(AtCoder Beginner Contest)で累積和を出され、その時解けなくて苦い思いをしたので今回自分の頭で累積和が出てきてとてもうれしかった。

こんな感じでゆるーくやっていきます

A問題はプログラミングが始めて間もない方でも少し考えればできると思うので、ぜひコンテストが開催されていれば初心者の方も参加してみてほしい。