AtCoder - ABC#2 C言語

A問題

　2つの整数が比較できれば特に問題なく書ける。

#include <stdio.h>

int main() {
  int max, x, y;
  scanf("%d %d", &x, &y);
  max = (x >= y)? x : y;
  printf("%d\n", max);
  return 0;
}

B問題

　答えを入れておく配列を別で作っておいて、'a','i','u','e','o'以外の文字を蓄えていく方針で解いたものが以下のコードである。
　わざわざ他の配列を作りたくない人はprintf()で1文字ずつ出力すれば実装できる。

#define LENGTH 31
#include <stdio.h>

int main() {
  char phrase[LENGTH], ans[LENGTH];
  int i, count = 0;
  scanf("%s", phrase);
  for(i = 0; i < LENGTH; i++) {
    if((phrase[i] != 'a') && (phrase[i] != 'i') && (phrase[i] != 'u') && (phrase[i] != 'e') && (phrase[i] != 'o')) {
      ans[count] = phrase[i];
      count++;
    }
  }
  printf("%s\n", ans);
  return 0;
}

C問題

　2つのベクトルが張る面の面積を求める問題の応用でできる。1つの頂点をベクトル２つのベクトルの始点として考えることで面積を求める方法だ。
　絶対値を求める必要があるため、abs()を用いている。abs()を使うためにはstdlib.hをインクルードする必要があるので忘れないようにしよう。

#include <stdio.h>
#include <stdlib.h>

int main() {
  int point_a_x, point_a_y, point_b_x, point_b_y, point_c_x, point_c_y;
  double area;
  scanf("%d %d %d %d %d %d", &point_a_x, &point_a_y, &point_b_x, &point_b_y, &point_c_x, &point_c_y);
  /*3つの点を平行移動させ点cを原点に持ってくる*/
  point_a_x -= point_c_x;
  point_a_y -= point_c_y;
  point_b_x -= point_c_x;
  point_b_y -= point_c_y;

  area = abs(point_a_x * point_b_y - point_a_y * point_b_x) / 2.0;
  printf("%f\n", area);
  return 0;
}

別解

　先ほどのものは3つの点から2つのベクトルにして考える方法だったが、別解ではヘロンの公式を使った解放を紹介する。ヘロンの公式とは三角形の3辺がわかっているときに面積を求めることができる公式である。今回の問題では座標が与えられるため3辺の長さが容易に求めることができる。そのためヘロンの公式を知っていれば真っ先にこちらの解放が思い浮かぶだろう。

#include <stdio.h>
#include <math.h>

int main() {
  int point_a_x, point_a_y, point_b_x, point_b_y, point_c_x, point_c_y;
  double area;
  double side[3];
  scanf("%d %d %d %d %d %d", &point_a_x, &point_a_y, &point_b_x, &point_b_y, &point_c_x, &point_c_y);
  /*3辺の長さを求める*/
  side[0] = sqrt(pow(point_a_x - point_b_x, 2.0) + pow(point_a_y - point_b_y, 2.0));
  side[1] = sqrt(pow(point_b_x - point_c_x, 2.0) + pow(point_b_y - point_c_y, 2.0));
  side[2] = sqrt(pow(point_c_x - point_a_x, 2.0) + pow(point_c_y - point_a_y, 2.0));
  /*ヘロンの公式*/
  double s = (side[0] + side[1] + side[2]) / 2.0;
  area = sqrt(s * (s - side[0]) * (s - side[1]) * (s - side[2]));
  printf("%f\n", area);
  return 0;
}

D問題

　知り合い関係にある組みを構造体でまとめて管理している。あとは各々が派閥に参加する場合と参加しない場合で、二分木を再帰で実装し深さ優先探索すれば実行時間内に解ける。

#include <stdio.h>

struct Relation {
  int left;
  int right;
};

/*派閥内全員が互いに知り合いであるかを確認している関数*/
int check(struct Relation *relation, int *member, int number_of_assembly, int number_of_relationship) {
  int i, j, k, flag, count = 0;
  int temp[12];
  for(i = 0; i < number_of_assembly; i++) {
    if(member[i] == 1) {
      temp[count] = i;
      count++;
    } else {
      continue;
    }
  }
  for(i = 0; i < count - 1; i++) {
    for(j = i + 1; j < count; j++) {
      flag = 0;
      for(k = 0; k < number_of_relationship; k++) {
        if(relation[k].left == temp[i] && relation[k].right == temp[j]) {
          break;
        } else {
          flag++;
        }
      }
      if(flag == number_of_relationship) return 1;
    }
  }
  return count;
}

int countBinaryTree(int number, struct Relation *relation, int *member, int number_of_assembly, int number_of_relationship) {
  int left = 1, right = 1;
  if(number == 0) {
    member[number] = 1;
    left = check(relation, member, number_of_assembly, number_of_relationship);
    member[number] = 0;
    right = check(relation, member, number_of_assembly, number_of_relationship);
  } else {
    member[number] = 1;
    left = countBinaryTree(number - 1, relation, member, number_of_assembly, number_of_relationship);
    member[number] = 0;
    right = countBinaryTree(number - 1, relation, member, number_of_assembly, number_of_relationship);
  }
  return (left > right)? left : right;
}

int main() {
  int number_of_assembly, number_of_relationship, i, max_count;
  scanf("%d %d", &number_of_assembly, &number_of_relationship);
  int member[12] = {};
  struct Relation relation[number_of_relationship];
  for(i = 0; i < number_of_relationship; i++) {
    scanf("%d %d", &relation[i].left, &relation[i].right);
    relation[i].left--;
    relation[i].right--;
  }
  max_count = countBinaryTree(number_of_assembly, relation, member, number_of_assembly, number_of_relationship);
  printf("%d\n", max_count);
  return 0;
}

最後まで見ていただきありがとうございます。また別の記事でお会いできることを祈っております。

---

---