こんちか、たくみんです。
今日は、2018年09月08日に行われたAtCoder Beginner Contest 109に挑戦してみました。時間が取れなかったので、競技時間外に行いました。 A問題とB問題は解くことができましたが、C問題とD問題は解けませんでした。 C言語で解いたのですが、かなり苦行だったので、WriteUpを兼ねてお話しします。

以下が結果となります。

f:id:takuminv:20180914223153p:plain:w400

A問題 ABC333

問題文
1以上3以下の整数A,Bが与えられます。
A×B×Cが奇数となるような1以上3以下の整数が存在するか判定してください。

制約
入力はすべて整数である
1≦A, B≦3

入力

A B

出力
存在するならYes、存在しないならNo

解法
では、解いていきましょう。問題文ではごちゃごちゃ言っていますが、ようするにAとBを入力して、A×B×C=奇数になるようなCが存在するかどうかを判定しろということです。
掛け算の性質として、偶数×偶数の答えは必ず偶数、偶数×奇数の答えは、偶数、奇数×奇数の答えは奇数となります。つまり、2つの値のうち、片方が偶数だと、絶対に奇数にはならないということです。ではここで、A×B×CのA×BをDとおき、D×Cとします。掛け算の性質から、この式の答えが奇数になるかどうかは、Dが偶数か奇数かどうかで判定することができます。

このプログラムをCで書くと以下のようになります。 A×Bの答えが偶数か奇数かによって出力をわけているだけですね。このくらいならCでも問題なく書けます。

#include<stdio.h>

int main(void) {

  int a,b;

  scanf("%d %d", &a, &b);

  if (((a*b) % 2) == 0 ) {
    printf("No");
  } else {
    printf("Yes");
  }

  return 0;
}

B問題 Shiritori

問題文

高橋くんは今日も1人でしりとりの練習をしています。
しりとりとは以下のルールで遊ばれるゲームです。

はじめ、好きな単語を発言する
以降、次の条件を満たす単語を発言することを繰り返す
その単語はまだ発言していない単語である
その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する

高橋くんは、10秒間にできるだけ多くの単語を発言する練習をしています。
高橋くんが発言した単語の個数 Nと i番目に発言した単語 Wiが与えられるので、どの発言もしりとりのルールを守っていたかを判定してください。

制約
Nは2≦N≦100を満たす整数である
Wiは英小文字からなる長さ1以上10≦の文字列である

入力

N
W1
W2
:
Wn

出力
しりとりのルールを守っているならYes、守っていないならNo

解法
では、解いていきましょう。これは、文字列検索の問題ですね。チェックしなければならないのは、同じ文字列が出現していないかという点と、文字列の先頭が、一つ前の文字列の末尾と同じかどうかという点です。前者はCでも簡単に書けます。チェックする関数は以下のようになります。愚直に、2重for文を用いました。入力する文字列は2次元配列のchar型変数wordsとして定義しています。stecmp関数ですべての組み合わせをチェックし、同じ文字列があれば0(No)を返しています。

int check_shiritori1(int n) {

  int k1,k2;

  for (k1 = 0; k1 < n; k1++) {
    for (k2 = 0; k2 < n; k2++) {
      if (k1 == k2) { continue; }
      if (strcmp(words[k1], words[k2]) == 0) {
        return 0;
      }
    }
  }

  return 1;
}

では、後者の点をチェックしてみます。このチェックに必要なのは、文字列の先頭と末尾です。先頭は[0]で表せますが、末尾をCで表そうとするとかなりめんどくさいです。(RubyとかPythonだと[-1]でいけるらしい。いいなぁ) 悩んだ結果、strlenで文字列の長さを取得し、-1することで末尾を表しました。以下のような関数になりました。いまみてもif文の条件がひどいですね… for文を回し、文字列の先頭と一つ前の文字列の末尾が違う文字の場合0(No)を返しています。

int check_shiritori2(int n) {

  int k;

  for (k = 1; k < n; k++) {
    if (words[k][0] != words[k-1][strlen(words[k-1])-1]) {
      return 0;
    }
  }

  return 1;
}

最後にmain文です。set_words関数は、入力した文字列を変数wordsに格納する関数です。 check_shiritori1関数と、check_shiritori2関数の両方が1を返したときにYesと表示します。一応、正解することはできましたが、Cで競プロは厳しいと思った問題でした。

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

#define MAX_N 100
#define MAX_L 10

void set_words(int n);
int check_shiritori1(int n);
int check_shiritori2(int n);
  
char words[MAX_N][MAX_L+1];

int main(void) {

  int n;
  int result1, result2;
  
  scanf("%d", &n);
  set_words(n);

  result1 = check_shiritori1(n);

  result2 = check_shiritori2(n);

  if ( (result1 * result2) == 0) {
    printf("No");
  } else {
    printf("Yes");
  }
  
  return 0;
}

おわりに

Cで競プロをしようとする場合、文字列検索や、ソートなどを自分で実装しないといけないため、かなり厳しいと感じました。次は、Rubyとかでやってみようかと思います。ではでは。

P.S.

ブログって日本語力が試される

たくみん成長日記

開発したアプリやプログラミングの備忘録を不定期に上げていきます。

C言語で競プロは苦行だった話

A問題 ABC333

B問題 Shiritori

おわりに

P.S.