ABC 033

2016.02.17

先週に続き、またAtCoderをやってきました。2月6日に開催されたAtCoder Beginner Contest 033の感想です。A問題からC問題までは難なく解けましたが、D問題に阻まれる結果となりました。330点40:51で53位です。

A 暗証番号

入力された4ケタの番号がゾロ目か判定する問題。1111で割る方法で解きました。

import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    if (n % 1111 == 0) System.out.println("SAME");
    else System.out.println("DIFFERENT");
  }
}

B 町の合併

合併前の町々の最大人口が、合併後の総人口の過半数かを判定する問題。一つずつ読みながら最大値と合計を計算して解きました。

import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String s[] = new String[n];
    int p[] = new int[n];

    String smax = "";
    int pmax = 0;
    int psum = 0;

    for (int i = 0; i < n; i++) {
      s[i] = sc.next();
      p[i] = sc.nextInt();
      psum += p[i];
      if (p[i] > pmax) {
        smax = s[i];
        pmax = p[i];
      }
    }
    if (pmax > psum / 2) {
      System.out.println(smax);
    } else {
      System.out.println("atcoder");
    }
  }
}

C 数式の書き換え

問題名から数式の計算と探索が必要な問題かと身構えたのですが違いました。一桁の正整数と加法・乗法のみからなる数式の答えを0にするために、いくつの数を0に書き換えればよいかを調べる問題。

普段この手のひらめきが苦手だと思っていたので、序盤に解けて嬉しかった問題です。

import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next() + '+';
    int l = s.length();
    int n = 0;

    for (int i = 0; i < l; i++) {
      if (s.charAt(i) == '0') {
        for (; i < l && s.charAt(i) != '+'; i++);
      } else {
        i++;
        if (s.charAt(i) == '+') {
          n++;
        }
      }
    }

    System.out.println(n);
  }
}

D 三角形の分類

問題のD問題。与えられたN個の頂点から作られうる三角形が、鋭角三角形、直角三角形、鈍角三角形のどれかを調べてその個数を答える問題。

どうしてもO(N^3)から削る方法が思いつかなかったので、そのまま提出しましたが、やはりTLE。そのまま1時間悩んだものの何も分からず、実行時間短縮を狙ってC言語（GCC）で提出しましたがTLEでした。

しかし、終了後に改めてC言語（Clang）で出したところすんなりACに。模範解法ではないとは言え、取れた点数を逃したことにがっかり……。