新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

参加記録:Code Festival 予選B

[参加記録] Code Festival 予選B

コンテストURL


Welcome to CODE FESTIVAL 2014 予選B - CODE FESTIVAL 2014 予選B | AtCoder

結果

  • A, B, D(部分点)の230点でした。
    • C, D はずっとTLE…orz
    • Dの方はDPの使い方をもうちょっと工夫すべきでした。
A問題:あるピアニスト
  • 2つの入力された数字の大きい方を出力。
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int a = scan.nextInt();
        int b = scan.nextInt();

        System.out.println(Math.max(a, b));
        
        scan.close();
    }
}
B問題:歩く人
  • N日間ウォーキングしたとき、K歩数に達する日にちを求める
    • i日目に歩いた歩数はa_iとして与えられる
    • 歩数を足していって超えたら出力。
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int K = scan.nextInt();
        int[] a = new int[N];

        for (int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }
        
        int walk = 0;
        
        for (int i = 0; i < N; i++) {
            walk += a[i];
            
            if (walk >= K) {
                System.out.println(i+1);
                break;
            }
        }        
        scan.close();
    }
}
C問題:錬金術
  • 2N文字の文字列S1, S2, S3が与えられ、S1とS2に含まれる文字を組み合わせてS3が作れるか判定
    • ただし、S1, S2から取り出せる文字はそれぞれN文字ずつ
    • 全探索は当然間に合わず。
  • 解説によると、全アルファベットについて、S1から取り出せる文字数の範囲を調べると良いらしい
    • あるアルファベットがS1, S2, S3に含まれている数をそれぞれC1, C2, C3とすると、
    • 最低でもC3 - C2個はS1から取り出さないとS3は作れない
      • S1 = "ABBCCC", S2 = "CZZZZZ", S3 = "ACCZZZ"のとき、文字'C'は少なくとも1個はS1から取り出す必要がある
      • 文字'Z'についてはC3 - C2が負の値になってしまうので、その場合は0個取り出すものとする
      • よって、S1から取り出せる文字数の範囲の下限はmax(0, C3 - C2)となる
    • また、最大でC1かC3の小さい方だけ取り出すことができる
      • 前述の0だと、文字'C'は最大で2個取り出すことができる
      • S1に'C'は3個含まれるが、3個取り出したところでS3に文字'C'は2個しかない
      • よって、S1から取り出せる文字数の範囲の上限はmin(C1, C3)となる
    • 全アルファベットについてこれを求めて、上限と下限についてそれぞれ総和を出す
    • 上限と下限の総和を求めたら、その範囲にNが入っていれば文字S3を作成することができる
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String s1 = scan.next();
        String s2 = scan.next();
        String s3 = scan.next();

        int N = s1.length() / 2;

        int max = 0;
        int min = 0;
        
        for (char c = 'A'; c <= 'Z'; c++) {
            int c3 = s3.length() - s3.replace(c + "", "").length();
            if (c3 == 0) {
                continue;
            }
            
            int c2 = s2.length() - s2.replace(c + "", "").length();
            int c1 = s1.length() - s1.replace(c + "", "").length();

            min += Math.max(0, c3 - c2);
            max += Math.min(c1, c3);
        }
        
        if (min <= N && N <= max) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }

        scan.close();
    }
}
  • 解説を元に書いてみたプログラムが上のもの。
    • S3に含まれていないアルファベットについては処理をスキップした。
    • ある文字が文字列に含まれる数を求める方法が他に思いつかなかったので、空文字に置換して長さの差を取っている。
D問題:登山家
  • 東西に並んでいる山小屋の標高が与えられ、各山小屋から見える他の山小屋の数を求める
    • 山小屋iから山小屋jが見える条件は、間にある山小屋の高さが全てiの標高より低い場合。
    • 東西それぞれ全探索した場合、部分点。
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
            int N = scan.nextInt();
            int[] h = new int[N];
            int[] y = new int[N];
		
            for (int i = 0; i < N; i++) {
                h[i] = scan.nextInt();
            }
 
            for (int i = 0; i < N; i++) {
                 // 東側
                for (int j = i + 1; j < N; j++) {
                    if (h[j] > h[i])
                        break;
                    y[i]++;
                }
 
                // 西側
                for (int j = i - 1; j >= 0; j--) {
                    if (h[j] > h[i])
                        break;		
                    y[i]++;
                }
            }
 
            for (int i = 0; i < N; i++) {
                System.out.println(y[i]);
            }
            scan.close();
    }
}
  • 解説によると、dp[i]を東/西側にある、見えないかつ一番近い山小屋の位置とすると良いらしい
    • 東端と西端に一番高い山小屋を配置
      • 東側を考えるとき、自分の一個東の山小屋が自分より高い場合:dp[i] = i + 1で終了
      • 自分より低い場合には、その山小屋のdpを自身のdpに代入:dp[i] = dp[dp[i]]
      • 上を繰り返す
    • これを東西それぞれに行うと、dp[i]から自身の山小屋から見える範囲を求めることができる
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int[] h = new int[N+2];
        int[] dpEast = new int[N+2];
        int[] dpWest = new int[N+2];
        
        for (int i = 1; i < N+1; i++) {
            h[i] = scan.nextInt();
        }

        h[0] = Integer.MAX_VALUE;
        h[N + 1] = Integer.MAX_VALUE;
        
        for (int i = N; i > 0; i--) {
            dpEast[i] = i + 1;
            while (h[i] >= h[dpEast[i]]) {
                dpEast[i] = dpEast[dpEast[i]];
            }
        }

        for (int i = 1; i < N + 1; i++) {
            dpWest[i] = i - 1;
            while (h[i] >= h[dpWest[i]]) {
                dpWest[i] = dpWest[dpWest[i]];
            }
            System.out.println(dpEast[i] - dpWest[i] - 2);
        }
        
        scan.close();
    }
}
  • 解説を元に書いてみたのが上。
    • 東側のdpと西側のdpをそれぞれ求めている。
    • 最後-2しているのは、範囲なので-1、自分自身は数にいれないのでさらに-1。
    • これが全探索より早い理由がわかっているようであんまりわかってなかったり…