プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

AtCoder Beginner Contest 103 に出ました

久々にリアルタイムでAtCoder出ました!ABC103です。
abc103.contest.atcoder.jp

結果は・・・なんと、開始48分で4問全完できました!とても嬉しい。
トリッキーな3問目の解き方にすぐ気づけたことと、
過去に似たような問題を解いていた4問目をしっかり丁寧に解けたことが、
全問正解につながったのだと思います。
レーティングあがるかな、ドキドキ・・・


では、解答を書いていきます。過去問やるときとかは色んな言語で解いていますが、今回は本当に少しでも高い順位を狙おうと思い、一番スムーズに書けるJavaでコードを書きました。
※A⇒B⇒C⇒Dの順で解きました

A問題

全パターン(全ての順番を試しても6通り)試すのも可能ですが、考えてみれば「数字の小さい順からタスクを片付ける」ときにコストが最小になるのが分かります(大きい順でもOK)。
比較を書くのが面倒&漏れがあったら怖いので、3個しか数字はないですがArrays.sort()を使いました。

import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    int[] ar = new int[3];
    ar[0] = sc.nextInt();
    ar[1] = sc.nextInt();
    ar[2] = sc.nextInt();
    Arrays.sort(ar);
    System.out.println(ar[2]-ar[0]);
  }
}

B問題

2つの文字列を読み込んで、単純に全探索しました。charAt()を使います。

import java.util.*;
 
public class Main {
  public static void main(String[] args) {
 	  Scanner sc = new Scanner(System.in);
 
    String s = sc.next();
    String t = sc.next();
 
    boolean answer = false;
 
    for(int i = 0; i < s.length(); i++){
      boolean checker = true;
      for(int j = 0; j < s.length(); j++){
        if(s.charAt(j) != t.charAt((j+i)%s.length())){
          checker = false;
        }
      }
      if(checker){
        answer = true;
        break;
      }
    }
 
    System.out.println(answer? "Yes" : "No"); 
  }
}

C問題

問題を読んでみたものの、nの大きさ的に全探索でいいのでは?と思い、変数を1〜100000まで変化させるコードを書いてみるも、3つ目の入力例で答えが一致せず・・・
ならばもっとたくさん試せば!と思い、下記のコードを書いてみました(上限大きくしただけ、10^8まで調べました)。

import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    int n = sc.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++){
      nums[i] = sc.nextInt();
    }

    int max = 0;
    for(int i = 1; i < 100000000; i++){
      int sum = 0;
      for(int j = 0; j < n; j++){
        sum += i % nums[j];
      }
      if(sum > max){
        max = sum;
      }
    }

    System.out.println(max); 
  }
}

ただ、これでも3つ目の入力例で答えが合わない上、制限時間である2000msをオーバーしてしまいました(コードテストで実行時間がでるの、本当にありがたい)。
正解との差を見ると、少しずつ近付いてはいるのだが・・・

じゃあ全探索じゃないんやな、ということで数学的に考えることに。
そこで、ふとひらめきました。
すべてのiに対して、 m mod a(i) = a(i)-1 とできるmが存在するのでは?
実際、よくよく考えてみると、

2 <= a(i)   であることから、
     M = a(1) * a(2) * .... * a(N) - 1
とすると、
すべてのiに対して 
     M mod a(i) = a(i) - 1
となりますね。
ということで、
     最大値 = (a(1) - 1) + (a(2) - 1) + ... + (a(N) - 1)
になります。

よって、解答コードはこうなりました。シンプル!

import java.util.*;
 
public class Main {
  public static void main(String[] args) {
 	  Scanner sc = new Scanner(System.in);
 
    int n = sc.nextInt();
    int sum = 0;
    for(int i = 0; i < n; i++){
      sum += sc.nextInt() - 1;
    }
 
    System.out.println(sum);
  }
}

D問題

C問題までで15分ほど、そこからD問題を解くのに30分以上かかりました。
条件的に全探索は間に合わない、こういう場合は累積和?いや、でもなんかピンと来ない・・・と考えて、色々と思いついた解き方でコードを書くも、3つのサンプルですら答えが合わず。
ただ、恐らくは貪欲法みたいにやるんだろうなー、と紙に殴り書きしながらやってて、下記の方針なら解けるのでは?となりました。

それは、各要望の「"どの島"から"どの島"まで(前者を"from",後者を"to"とします、from < toです)」を「toが小さい順に見ていく」というやり方です。
そして、toが小さい順で、一番右にある橋を切り落としていきます。
そして切り落とした橋を覚えておき、それで解決している要望(fromがその橋より左にあるもの)はもう無視する、という方針です。
これでコードを書いてみたら・・・サンプルも答えが合い、提出したらACが出ました!やったぜ全問正解!!!

toでソートする必要があったため、自分でdemandというクラスを作りました。
※クラスの作り方は、過去に僕が悪戦苦闘した下記記事をご参照ください
Javaで自分の作ったクラスに順序を入れる方法(Comparable編)(CodeFestivalあさぷろMiddle B問題) - プログラミングを上達させたい

コードはこんな感じです。

import java.util.*;
 
class demand implements Comparable{
  int from;
  int to;
 
  public int compareTo(Object other){
    demand otherdemand = (demand)other;
    return to - otherdemand.to;
  }
}
 
public class Main {
  public static void main(String[] args) {
 	  Scanner sc = new Scanner(System.in);
 
    int n = sc.nextInt();
    int m = sc.nextInt();
 
 
    demand[] demands = new demand[m];
 
    for(int i = 0; i < m; i++){
      demand newdemand = new demand();
      newdemand.from = sc.nextInt();
      newdemand.to = sc.nextInt();
      demands[i] = newdemand;
    }
 
    Arrays.sort(demands);
 
    int ans = 0;
    int nowclear = 0;
    for(int i = 0; i < m; i++){
      int nowfrom = demands[i].from;
      int nowto = demands[i].to;
      if(nowclear < nowfrom){
        ans++;
        nowclear = nowto - 1;
      }
    }
 
    System.out.println(ans);
  }
}


というわけで、とても達成感があります。
レーティングどうなるかなー、1000乗ったら嬉しいですね。現在944。
引き続き頑張ります!


P.S.レーティング、1063になりました。やったね!反映はやっ(同日22:50)