Hatena::Grouptopcoder

Topcoderと数オリを目指す日記

2017-02-21

SRM701 SortingSubsets(div2 Medium)

23:08

Graph Theory

昇順にソートした配列と元の配列で異なる要素数を求めれば良い。

import java.util.*;

public class SortingSubsets {
  public int getMinimalSize(int[] a) {
    int[] b = a.clone();
    Arrays.sort(a);
    int count = 0;
    for(int i = 0; i < a.length; i++) {
      if(a[i] != b[i]) count++;
    }
    return count;
  }
}

Passed System Test

SRM331 CarolsSinging(div2 Medium)

22:42

Graph Theory

全探索をしても計算量は高々2^10*300<10^6なので間に合う。DFS(深さ優先探索)を使ってみた。はじめて使ったので、上手くいくかは不明である。するめ直前なので、Arenaに過去問がないのである。

歌の選択をビットを用いて表せば、簡単に全探索出来た。ビット演算の復習を行う事が出来た。

import java.util.*;

public class CarolsSinging {
  public int choose(String[] lyrics) {
    int num = lyrics.length;
    int songNum = lyrics[0].length();
    int[] masks = new int[num];
    for(int i = 0; i < num; i++) {
      String str = (lyrics[i].replace('Y', '1')).replace('N', '0');
      masks[i] = Integer.parseInt(str, 2);
    }
    int ans = 100;
    for(int i = 1; i < (1 << songNum); i++) {
      int count = 0;
      for(int j = 0; j < num; j++) {
        if((masks[j] & i) == 0) count++;
      }
      if(count == 0) ans = Math.min(ans, Integer.bitCount(i));
    }
    return ans;
  }
}

Passed System Test

2017-02-20

SRM686 TreeAndVertex(div2 easy)

22:05

Graph Theory

木がハミルトン閉路を持たない事がポイントでした。

public class TreeAndVertex {
  public int get(int[] tree) {
    int N = tree.length + 1;
    int[][] edge = new int[N][N];
    for(int i = 0; i < tree.length; i++) {
      edge[i + 1][tree[i]] = 1;
      edge[tree[i]][i + 1] = 1;
    }
    int max = 0;
    for(int i = 0; i < N; i++) {
      int a = 0;
      for(int j = 0; j < N; j++) {
        if(edge[i][j] == 1) a++;
      }
      max = Math.max(max, a);
    }
    return max;
  }
}

27min Passed System Test

2017-02-19

SRM479 TheAirTripDivTwo(div2 easy)

21:07

Graph Theory

1回毎のflightでfuelを減らしていき、マイナスになるまで続ける。

public class TheAirTripDivTwo {
  public int find(int[] flights, int fuel) {
    int point = 0;
    for(int i = 0; i < flights.length; i++) {
      fuel -= flights[i];
      if(fuel >= 0) {
        point++;
      } else {
        break;
      }
    }
    return point;
  }
}

5min Passed System Test

SRM436 FriendScore(div2 easy)

20:46

Graph Theory

計算量は高々O(N^3)なので間に合う。

import java.util.*;

public class FriendScore {
  public int highestScore(String[] friends) {
    int N = friends.length;
    int[][] twoFriends = new int[N][N];
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(i == j) {
          twoFriends[i][j] = 0;
        } else {
          if(friends[i].charAt(j) == 'Y') {
            twoFriends[i][j] = 1;
          } else {
            for(int k = 0; k < N; k++) {
              if(friends[i].charAt(k) == 'Y' && friends[j].charAt(k) == 'Y') {
                twoFriends[i][j] = 1;
                break;
              }
            }
          }
        }
      }
    }
    int[] twoNum = new int[N];
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(twoFriends[i][j] == 1) twoNum[i]++;
      }
    }
    Arrays.sort(twoNum);
    return twoNum[N - 1];
  }
}

14.7min Passed System Test

AtCoder Beginner Contest 046

13:05

A:AtCoDeerくんとペンキ / AtCoDeer and Paint Cans

HashSetに色を格納すれば良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < 3; i++) {
      set.add(sc.nextInt());
    }
    System.out.println(set.size());
  }
}

AC

B:AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

左端のボールの色はK種類選べ、以降のボールの色は(K-1)種類選べる。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int ans = K;
    for(int i = 1; i < N; i++) {
      ans *= (K - 1);
    }
    System.out.println(ans);
  }
}

AC

AtCoder Beginner Contest 047

10:05

A:キャンディーと2人の子供 / Fighting over Candies

a,b,cを小さい順にソートし、1番大きいものが残り2つの和となるかを判定すれば良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] candy = new int[3];
    candy[0] = sc.nextInt();
    candy[1] = sc.nextInt();
    candy[2] = sc.nextInt();
    Arrays.sort(candy);
    String ans = "No";
    if(candy[2] == (candy[0] + candy[1])) ans = "Yes";
    System.out.println(ans);
  }
}

AC

B:すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit)

aの値に応じて、白領域のxmin,xmax,ymin,ymaxを更新していけば良い。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int W = sc.nextInt();
    int H = sc.nextInt();
    int N = sc.nextInt();
    int xmin = 0;
    int xmax = W;
    int ymin = 0;
    int ymax = H;
    for(int i = 0; i < N; i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      int a = sc.nextInt();
      if(a == 1) xmin = Math.max(xmin, x);
      if(a == 2) xmax = Math.min(xmax, x);
      if(a == 3) ymin = Math.max(ymin, y);
      if(a == 4) ymax = Math.min(ymax, y);
    }
    int ans = Math.max(0, xmax - xmin) * Math.max(0, ymax - ymin);
    System.out.println(ans);
  }
}

AC

C:一次元リバーシ / 1D Reversi

B→W,W→Bの変化がいくつあるかをカウントすれば良い。1回の操作により変化は高々1つ減り、また丁度1つ減らす事が出来る。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int count = 0;
    for(int i = 0; i < S.length() - 1; i++) {
      if(S.charAt(i) != S.charAt(i + 1)) count++;
    }
    System.out.println(count);
  }
}

AC

2017-02-18

AtCoder Beginner Contest 048

21:50

A:AtCoder *** Contest

簡単です。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    String s = sc.next();
    System.out.println("A" + String.valueOf(s.charAt(0)) + "C");
  }
}

AC

B:Between a and b ...

場合分けで少し迷ったが、難しくはない。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long b = sc.nextLong();
    long x = sc.nextLong();
    long ans = 0;
    if(a % x == 0) {
      ans = b / x - a / x + 1;
    } else {
      ans = b / x - a / x; 
    }
    System.out.println(ans);
  }
}

AC

C:Boxes and Candies

Greedy。countをint型にしていたため、WAされてしまっていた。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int x = sc.nextInt();
    int[] a = new int[N];
    for(int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
    }
    long count = 0;
    for(int i = 1; i < N; i++) {
      if(a[i - 1] + a[i] > x) {
        count += (a[i] + a[i - 1] - x);
        if(a[i - 1] > x) {
          a[i] = 0;
        } else {
          a[i] = x - a[i - 1];
        }
      }
    }
    System.out.println(count);
  }
}

AC

AtCoder Beginner Contest 049

11:25

A:居合を終え、青い絵を覆う / UOIAUAI

難しい箇所はない。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String c = sc.next();
    String ans = "consonant";
    if(c.equals("a") || c.equals("e") || c.equals("i") || c.equals("o") || c.equals("u")) ans = "vowel";
    System.out.println(ans);
  }
}

AC

B:たてなが / Thin

1行まとめて読み込まれる事が分からなかった。解説配信を見て解きました。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    for(int i = 0; i < H; i++) {
      String row = sc.next();
      System.out.println(row);
      System.out.println(row);
    }
  }
}

AC

C:白昼夢 / Daydream

細かいミスで中々通らなかったが、DPを使って素直に解けた。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int len = S.length();
    String ans = "NO";
    if(len >= 5) {
      // dp[i]はインデックスi~末尾までの部分文字列に対する判定結果を返す(出来るなら1、出来ないなら-1)
      int[] dp = new int[len + 1];
      dp[len] = 1;
      dp[len - 1] = -1;
      dp[len - 2] = -1;
      dp[len - 3] = -1;
      dp[len - 4] = -1;
      dp[len - 5] = -1;
      String str = S.substring(len - 5);
      if(str.equals("dream") || str.equals("erase")) dp[len - 5] = 1;
      for(int i = len - 6; i >= 0; i--) {
        dp[i] = -1;
        String str5 = S.substring(i, i + 5);
        String str6 = S.substring(i, i + 6);
        if((str5.equals("dream") || str5.equals("erase")) && dp[i + 5] == 1) dp[i] = 1;
        if(str6.equals("eraser") && dp[i + 6] == 1) dp[i] = 1;
        if(i + 7 <= len) {
          String str7 = S.substring(i, i + 7);
          if(str7.equals("dreamer") && dp[i + 7] == 1) dp[i] = 1;
        }
      }
      if(dp[0] == 1) ans = "YES";
    }
    System.out.println(ans);
  }
}

AC

2017-02-16

AtCoder Beginner Contest 050

19:31

A:Addition and Subtraction Easy

簡単でした。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    String op = sc.next();
    int B = sc.nextInt();
    int ans = A + B;
    if(op.equals("-")) ans = A - B;
    System.out.println(ans);
  }
}

AC

B:Contest with Drinks Easy

これも簡単。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int sumTime = 0;
    int[] time = new int[N];
    for(int i = 0; i < N; i++) {
      time[i] = sc.nextInt(); 
      sumTime += time[i];
    }
    int M = sc.nextInt();
    for(int i = 0; i < M; i++) {
      int P = sc.nextInt() - 1;
      int ans = sumTime - time[P] + sc.nextInt();
      System.out.println(ans);
    }
  }
}

AC

C:Lining Up

HashMapを使うと上手くいかなかった。原因不明。Arrays.equalsメソッドで配列の一致判定を行うようにした。

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long MOD = 1000000007;
    int[] diff = new int[N];
    for(int i = 0; i < diff.length; i++) {
      diff[i] = sc.nextInt();
    }
    Arrays.sort(diff);
    int[] a = new int[N];
    if(N % 2 == 0) {
      for(int i = 0; 2 * i + 1 < N; i++) {
        a[2 * i] = 2 * i + 1;
        a[2 * i + 1] = 2 * i + 1;
      }
    } else {
      a[0] = 0;
      for(int i = 0; 2 * i + 2 < N; i++) {
        a[2 * i + 1] = 2 * i + 2; 
        a[2 * i + 2] = 2 * i + 2;
      }
    }
    long ans = 0;
    if(Arrays.equals(diff, a)) {
      int time = N / 2;
      ans = 1;
      for(int i = 0; i < time; i++) {
        ans = (ans * 2) % MOD;
      }
    }
    System.out.println(ans);
  }
}

AC