ニートが学ぶプログラミング

ニートの日記。プログラムのことやら、くだらないこと、思ったことをまとめていきます。頑張って毎日更新するぞぉ_(:3」∠)_ 更新が連続して途切れたら察してください。

トップ > AtCoder > AtCoderの過去問に挑戦 ABC002 AtCoder Beginner Contest 002

AtCoderの過去問に挑戦 ABC002 AtCoder Beginner Contest 002

AtCoder AtCoder Beginner Contest ABC Java プログラミング

atcoderの画像を使わせていただきました。問題があれば削除痛いします。

はじめに

私はプログラムやプログラミングコンテストに対して何ら知識はありません。私が書くコードは、性能的にも優れているものではありません。私自身が考え、学んでいく過程でできたコードです。無駄がありますが、お許しください。また、改善等の指導があればコメント欄に記入していただけると助かります。

公式URL

使用したもの等

名称 使用したもの
言語 JavaSE8
エディタ pleiades All in one var.4.7.0
プラグイン addons.mozilla.org

A - 正直者

略

B - 罠

問題

問題文

B問題のリジャッジ（再採点）が終了しました。21: 50
B問題のテストケースにミスがあったので、提出されたコードをリジャッジ（再採点）してます。21: 40

神の恵みで財産を築いた高橋くんですが、なんとそこには罠がありました。
神は、高橋くんの発した言葉から母音 a、i、u、e、o を全て盗んでいったのです。
高橋くんが発した言葉を表す文字列 W が与えられるので、周囲の人が聞く言葉を表す文字列を出力するプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。 
W
  1. 1 行目には、高橋くんの発した言葉を表す文字列 W が与えられる。
    • W の長さ |W| は 1≦|W|≦30 を満たす。
    • W は半角英小文字（a から zまで）のみで構成される。
    • W には母音以外の文字が少なくとも 1 文字含まれることが保証されている。

出力

W から母音を全て除いた文字列を 1 行で出力してください。
また、出力の末尾には改行を入れること。

入力例 1

  1. chokudai

出力例 1

  1. chkd
  • chokudai から a、i、u、e、o を除くと chkd になります

入力例 2

  1. okanemochi

出力例 2

  1. knmch
  • okanemochi から a、i、u、e、o を除くと knmch になります

入力例 3

  1. aoki

出力例 3

  1. k
  • aoki から a、i、u、e、o を除くと k になります
  • このように、与えられる文字列 W には母音以外の文字が少なくとも 1 文字含まれます

入力例 4

  1. mazushii

出力例 4

  1. mzsh

見出しをクリックすると開きます。↓↓

回答

母音を取り除くという問題ですね。

正規表現を使って解く

正規表現を使って解くのが一番わかりやすく、かつコードもシンプルなものになると思います。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      String w = br.readLine();
      System.out.println(w.replaceAll("[aiueo]", ""));
    }
  }
}

正規表現を使った置換のメソッドは多くの言語が実装しているのではないでしょうか？Javaの場合はStringクラスにreplaceAll(String regex, String replace)というメソッドがあります1。それを使い正規表現を元に空文字に置換してあげましょう。正規表現は他言語で共通している部分が多いですが、言語によっては方言のように詳しく指定できるものもあります2。

問題ではa,i,u,e,oを取り除いてあげるという事ですね。

正規表現では[aiueo]と簡単に書けます。

後はその正規表現をメソッドを使い、空文字に置換しましょう。

System.out.println(w.replaceAll("[aiueo]", ""));

Streamを使って解く

Java8から追加されたStreamを使っても解くことができます。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      String w = br.readLine();
      StringBuilder sb = new StringBuilder();
      w.chars()
       .filter(c -> !(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'))
       .forEach(c -> sb.append((char) c));
      System.out.println(sb.toString());
    }
  }
}

配列を使って解く

勿論配列を使って問題を解くこともできます。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      String w = br.readLine();
      char[] ans = new char[w.length()];
      int index = 0;
      for (char c : w.toCharArray()) {
        if (!(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')) {
          ans[index++] = c;
        }
      }
      // new String(ans)だとchar=0が入り、改行文字がなくなる
      System.out.println(String.valueOf(ans, 0, index));
    }
  }
}

このときnull文字が入って、改行文字が消されないように気を付けましょう。

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
79 ms 24916 KB

C - 直訴

問題

問題文

神に盗まれた母音を取り戻すため、高橋くんは神へ直訴しました。
「神様、どうかお願いです。僕の母音を返してください。」
神はこう言いました。
「そんなに母音がほしいのか。ならば私の仕事を手伝ってもらおう。」

現在、神は天界のいたるところで測量を行っており、高橋くんは神の測量を手伝わなければなりません。
今回は三角形の測量です。高橋くんには 2 次元平面上の 3 つの点 A, B, C が与えられます。
少しでも早く母音を取り戻すために、三角形 ABC の面積を出力するプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。 
xa ya xb yb xc yc
  1. 1 行目には、3 点 A, B, C の座標が半角空白区切りで与えられる。
    • 点 A の座標が (xa, ya)、点 B の座標が (xb, yb)、点 C の座標が (xc, yc) であることを表す。
    • 各座標の値 xa, ya, xb, yb, xc, yc は −1,000 以上 1,000 以下の整数であることが保証されている。
    • 3 点 A, B, C が同一直線上に配置されていることはない。

出力

三角形 ABC の面積を 1 行で出力してください。
また、出力の末尾には改行を入れること。
出力は絶対誤差が 10−2 以下であれば許容される。

ヒント

3 点 (0,0), (a,b), (c,d) で構成される三角形の面積は、|ad−bc|⁄2 となります。
（このヒントは、コンテスト開始 1 時間後に公開されたものです。）

入力例 1

  1. 1 0 3 0 2 5

出力例 1

  1. 5.0
    図1：入力例 1 を図示したもの

入力例 2

  1. -1 -2 3 4 5 6

出力例 2

  1. 2.0

入力例 3

  1. 298 520 903 520 4 663

出力例 3

  1. 43257.5

見出しをクリックすると開きます。↓↓

回答

3点から三角形の面積を求める問題ですね。学校でやったなぁ…でももう忘れたよという私のような方も多いのでは。

ヘロンの公式で3角形の面積を求める

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      String[] array = br.readLine().split(" ");

      Point x = new Point(Integer.parseInt(array[0]), Integer.parseInt(array[1]));
      Point y = new Point(Integer.parseInt(array[2]), Integer.parseInt(array[3]));
      Point z = new Point(Integer.parseInt(array[4]), Integer.parseInt(array[5]));

      double a2 = x.distanceSq(y);
      double b2 = y.distanceSq(z);
      double c2 = z.distanceSq(x);

      double t = Math.sqrt((a2 + b2 + c2) * (a2 + b2 + c2) - 2 * (a2 * a2 + b2 * b2 + c2 * c2)) / 4.0;

      System.out.println(t);
    }
  }

}

3角形の面積を求める方法はいろいろあったのですが、学校で習った記憶がかすかにあるなと思ったこの公式で面積を求めてみましょう。

ヘロンの公式は辺a,b,cに対して

{ \huge {\displaystyle{ T = \sqrt{s(s-a)(s-b)(s-c)} \\ s = \frac{a+b+c}{2} }}}

これで求めることができます。懐かしい！その公式のままプログラムを書いてもいいですが、辺abcを求めるときに平方根を取ります。平方根はできるだけ最後にした方が、計算の誤差が少なくなるため変形した公式を使いましょう。

{ \huge {\displaystyle T = \frac{\sqrt{(a^2+b^2+c^2)^2-2(a^4+b^4+c^4)}}{4} }}

この公式ですと、abcがそれぞれ2乗4乗されてますね。距離を求めるときに平方根を取らないでよいという事ですね。

JavaにはPoint2D::distanceSq(Point2D)というメソッドがあります3。距離を求める計算の途中で平方根を取らない値を返してくれます。

これを使うことで、計算の最後のみに平方根をとるようにできます。

1点を原点にずらす

問題のヒントにもあるように、原点、他2点から作られる三角形の面積は

{ \huge {\displaystyle T = \frac{1}{2}|ad-bc| }}

で求まるようです。そんな便利なのがあるんですね！なんだか行列の計算を思い出します。

という事で、与えられた3点のうちの最初の点を原点とみなすようにしてあげましょう。

package abc002.c;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      String[] array = br.readLine().split(" ");

      Point a = new Point(Integer.parseInt(array[0]), Integer.parseInt(array[1]));
      Point b = new Point(Integer.parseInt(array[2]), Integer.parseInt(array[3]));
      Point c = new Point(Integer.parseInt(array[4]), Integer.parseInt(array[5]));

      // aを原点にするように全体をずらす

      Point b2 = new Point(b.x - a.x, b.y - a.y);
      Point c2 = new Point(c.x - a.x, c.y - a.y);

      double s = Math.abs(b2.getX() * c2.getY() - b2.getY() * c2.getX()) / 2.0;

      System.out.println(s);
    }
  }

}

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
85 ms 23252 KB

D - 派閥

問題

問題文

神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。
人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。 
N M
x1 y1
x2 y2
:
xM yM
  1. 1 行目には、高橋くん以外の国会議員の数 N (1≦N≦12) と、人間関係の数 M (0≦M≦N(N−1)⁄2) が半角空白区切りで与えられる。
  2. 2 行目から M+1 行目までの M 行で、人間関係が与えられる。
    • 各議員は 1 から N までの整数で番号がつけられている。
    • 2 行目を基準とした第 i (1≦i≦M) 行において、議員 xi と議員 yi は知り合いであることを意味する。
    • xi と yi はともに整数で、 1≦xi<yi≦N を満たす。
    • i≠j のとき、(xi, yi)≠(xj, yj) であることが保証されている。

出力

高橋くんが作成することができる最大の派閥に属する議員数を 1 行で出力してください。
また、出力の末尾には改行を入れること。

入力例 1

  1. 5 3
  2. 1 2
  3. 2 3
  4. 1 3
  • 1 行目：5 人の議員と 3 つの人間関係が存在する。
  • 2 行目：議員 1 と議員 2 は知り合いである。
  • 3 行目：議員 2 と議員 3 は知り合いである。
  • 4 行目：議員 1 と議員 3 は知り合いである。

出力例 1

  1. 3
  • 議員 1、議員 2、議員 3 は互いに知り合いなので、この 3 人は派閥を構成することができる。

入力例 2

  1. 5 3
  2. 1 2
  3. 2 3
  4. 3 4

出力例 2

  1. 2
  • 議員数 2 の派閥として
    1. 議員 1 と議員 2 の派閥
    2. 議員 2 と議員 3 の派閥
    3. 議員 3 と議員 4 の派閥
    の 3 通りが考えられます。

入力例 3

  1. 7 9
  2. 1 2
  3. 1 3
  4. 2 3
  5. 4 5
  6. 4 6
  7. 4 7
  8. 5 6
  9. 5 7
  10. 6 7

出力例 3

  1. 4

入力例 4

  1. 12 0

出力例 4

  1. 1
  • たとえ 12人の議員がいても、誰も知りあいでなければ 1 人からなる派閥しか作成することはできません。

見出しをクリックすると開きます。↓↓

回答

難問でした…この問題では組み合わせを考慮する必要があります(たぶん)。 bit演算を使うなんて変態のすることだ！なんて思ってましたが、どうやら私は変態になったようです(´;ω;｀)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
      String[] array = br.readLine().split(" ");

      int n = Integer.parseInt(array[0]);

      HumanMap map = new HumanMap(n);

      String str = null;
      while ((str = br.readLine()) != null) {
        map.put(str);
      }
      System.out.println(map.max());
    }
  }

  private static class HumanMap {
    private final int[] map;
    private final int size;
    private final int[] key;

    public HumanMap(int n) {
      map = new int[n];
      key = new int[n];
      for (int i = 0; i < n; i++) {
        map[i] = 1 << i;
      }

      size = n;

    }

    public void put(String str) {
      String[] array = str.split(" ");
      this.put(Integer.parseInt(array[0]), Integer.parseInt(array[1]));
    }

    public void put(int a, int b) {
      map[a - 1] |= (1 << (b - 1));
      map[b - 1] |= (1 << (a - 1));
    }

    public int max() {
      int max = 1;

      for (int line : map) {
        if (Integer.bitCount(line) > max) {
          for (int filter = Integer.lowestOneBit(line); filter <= line; filter++) {
            int combination = filter & line;
            if (combination > 0 && Integer.bitCount(combination) > max) {
              int keySize = setKey(combination);
              int value = combination;
              for (int k = 0; k < keySize; k++) {
                value &= map[key[k]];
              }
              max = Math.max(Integer.bitCount(value), max);
            }
          }
        }
      }
      return max;
    }

    private int setKey(int line) {
      int index = 0;
      for (int i = 0; i < size; i++) {
        if ((line & (1 << i)) > 0) {
          key[index++] = i;
        }
      }
      return index;
    }
  }
}

ポイント1 人間関係を対戦表に入れる

問題では、人間関係(x,y)が入力されます。人間関係をPointクラスのように新しく作ってもいいのですが、クラス作成時やリスト追加などの処理でメモリ・時間のリソースを奪ってしまいます。

ABC001-Dから学んだように人間関係を入れて置ける配列を用意しましょう。具体的には総当たりの対戦表のようなものをイメージします。下の例は入力例1の場合です。

f:id:neet-utsu-taro:20171024212513p:plain

こんな風に配列を用意しておけば、どんなに人間関係が増えても配列の大きさに影響はありません。

人間関係(x,y)が与えられた場合、この配列の[x-1][y-1]と[y-1][x-1]に○(true)を入れてあげるだけです。

人間関係の配列を作る場合、2次元配列はできるだけやめましょう。私の経験不足なだけかもしれませんが、2次元配列でいろいろと処理をしようとすると、頭の中が混乱してしまいます。下のように配列の行をビットとして考え、intの数値配列として保存するのがいいと思います。

f:id:neet-utsu-taro:20171024213808p:plain

  • 対戦表の行を検索する場合はint[i]などのアクセス
  • 対戦表の列を検索する場合はビット演算によるアクセス

という風に分けることで混乱を最小限に抑えました。

またビット演算&を使うことで、人間関係で共通の部分を簡単に求めることができます。

例えば、人間関係1,2,3の共通の関係を求める場合は

7(111) & int[0] & int[1] & int[2] = 7(111)

と求めることができます。

ポイント2. 組み合わせをビット演算で表現する

問題の後半高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。の部分を求める際に、組み合わせを考えなくてはいけません。

{ \huge {\displaystyle{ \sum_{r=1}^{n}{}_n C _r }}}

この数だけ、可能性を考慮する必要があります。私にはよくわからなかったので、ビット演算を使って組み合わせを表現しました。

先ほどの例があるとします。

f:id:neet-utsu-taro:20171024213808p:plain

人間1の人間関係で共通している人数を求めるとします。

  1. 人間1の人間関係を調べる。
    人間1の人間関係は7(111)です。

  2. 1から7までの数値と&演算して組み合わせを求める。
    人間関係7の最小ビットの数値1からその値7(111)までの値を使って組み合わせを求めます。
    7 & 1 = 1, 7(111) & 2(010) = 2(010), 7(111) & 3(011) = 3(011)のようにします。すると、1,2,4, 3,5,6, 7という7通りの関係を取得できます。これは

3C1 + 3C2 + 3C3 = 3 + 3 + 1 = 7

という考え方と同じですね。

人間3の人間関係の場合も同様に

最小のビット1からその値23(10111)までの値で&演算します。すると、
1,2,4,16, 3,5,17,6,18,20, 7,19,22,21, 23の15通りの関係を取得できます。

4C1 + 4C2 + 4C3 + 4C4 = 4 + 6 + 4 + 1 = 15

と同じです。

成績

プログラムの実行時間およびメモリ使用量をまとめました。

実行時間 メモリ使用量
86 ms 23252 KB

まとめ

問題Dは最大クリーク問題と呼ばれるものの小さいものらしいですね！問題の正答に1日以上かかったわけですが、解説を見ると改善するところはあまりなかったのが嬉しかったです

終わりに

ここまで読んでくださってありがとうございます！

長かったですが、ようやくABC002クリアできました！ 今週末にABCのコンテストがあるらしいので、参加したいと思います。（前回あったの知らなかった(´;ω;｀)）

スター、ブックマーク、読者登録等ありがとうございます！いつも励みになってます！

ブログ巡りもまだなので明日したいと思います。

またね('ω')ノ

  1. String (Java Platform SE 8)↩

  2. Javaにおける正規表現の文法↩

  3. Point2D (Java Platform SE 8)↩