新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

参加記録:Atcoder Beginner Contest #018

[参加記録] Atcoder Beginner Contest #018

コンテストURL


Welcome to AtCoder Beginner Contest #018 - AtCoder Beginner Contest #018 | AtCoder

結果

  • A, BとCの部分点の230点
    • まだまだーって感じですね。

プログラム

A問題
  • A〜Cのとった得点1〜100がそれぞれ与えられるので、A〜Cの順位を1行に1つずつ出力する。
    • なんのひねりもなく6通り書いたのでした。。。
    • ソートして探索とか、自分より得点の高い人の数+1が順位とか色々あるはず
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();
        int C = scan.nextInt();

        if (A > B && A > C) {
            System.out.println("1");
            if (B > C) {
                System.out.println("2");
                System.out.println("3");
            }
            else {
                System.out.println("3");
                System.out.println("2");                
            }
        }
        else if (B > C && B > A) {
            if (A > C) {
                System.out.println("2");
                System.out.println("1");
                System.out.println("3");
            }
            else {
                System.out.println("3");
                System.out.println("1");
                System.out.println("2");
            }
        }
        else {
            if (A > B) {
                System.out.println("2");
                System.out.println("3");
                System.out.println("1");                
            }
            else {
                System.out.println("3");
                System.out.println("2");
                System.out.println("1");                                
            }
        }
        
        scan.close();
    }
}
B問題
  • 文字列SとN個の操作に対応するli, riが与えられる。
    • Sのli文字目からri文字目までの部分文字列を逆転させ、N個の操作が終わったときの文字列を出力する。
import java.util.Scanner;

public class Main {

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

        String S = scan.next();
        int N = scan.nextInt();
        int[] l = new int[N];
        int[] r = new int[N];
        for (int i = 0; i < N; i++) {
            l[i] = scan.nextInt();
            r[i] = scan.nextInt();
        }
		
        char[] chars = S.toCharArray();
		
        for (int i = 0; i < N; i++) {
            int left = l[i] - 1;
            int right = r[i] - 1;
            while (left < right) {
                char tmp = chars[left];
                chars[left] = chars[right];
                chars[right] = tmp;
                left++;
                right--;
            }
        }
        
	System.out.println(chars);
	scan.close();
    }
}
C問題
  • RかけるCマスのマス目があり、それぞれ白か黒に塗られている。
    • 制約通りの菱型にマス目を緑色に塗るとき、塗る対象のマス目が全て白色の数は何通りか。
    • 問題名がヒントになっていたのに気づかず…とりあえず塗る対象の全範囲を調べたのが以下。
public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
 
    public static void main(String[] args) {
        new Main().calc();
    }
 
    public void calc() {
        int R = in.nextInt();
        int C = in.nextInt();
        int K = in.nextInt();
        char[][] s = new char[R][C];
        for (int i = 0; i < R; i++) {
            s[i] = in.next().toCharArray();
        }
 
        int count = 0;
 
        for (int x = K; x <= R - K + 1; x++) {
            for (int y = K; y <= C - K + 1; y++) {
                boolean flag = true;
                LOOP : for (int i = 1; i <= R; i++) {
                    int abs = i - x >=  0 ? i - x : x - i;
                    int start = abs + 1 - K;
                    if (start > 0) {
                        continue;
                    }
                    int end = -start;
                    start += y;
                    end += y;
                    for (int j = start; j <= end; j++) {
                        if (s[i - 1][j - 1] != 'o') {
                            flag = false;
                            break LOOP;
                        }
                    }
                }
 
                if (flag) {
                    count++;
                }
            }
        }
 
        out.println(count);
        out.close();
    }
}
  • 上の計算量はO(RCK^2)ということでTLE。
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }

    public void calc() {
        int R = in.nextInt();
        int C = in.nextInt();
        int K = in.nextInt();
        char[][] s = new char[R][C];

        for (int i = 0; i < R; i++) {
            s[i] = in.next().toCharArray();
        }

        // up[i][j] : マス(i, j)から数えて、上に何マス連続で白マスが続くか
        int[][] up = new int[R][C];
        // down[i][j] : マス(i, j)から数えて、下に何マス連続で白マスが続くか
        int[][] down = new int[R][C];

        // 横を固定で縦にup, downを数えていくのでC -> Rの順
        for (int j = 0; j < C; j++) {
            // up[i][j]の計算
            int count = 0;
            for (int i = 0; i < R; i++) {
                if (s[i][j] == 'x') {
                    count = 0;
                } else {
                    count++;
                }
                up[i][j] = count;
            }
            // down[i][j]の計算
            count = 0;
            for (int i = R - 1; i >= 0; i--) {
                if (s[i][j] == 'x') {
                    count = 0;
                } else {
                    count++;
                }
                down[i][j] = count;
            }
        }

        int ret = 0;
        for (int x = K - 1; x <= R - K; x++) {
            for (int y = K - 1; y <= C - K; y++) {
                boolean isAllWhite = true;
                // 菱型はx, yを中心に-K〜Kの範囲
                for (int len = -(K - 1); len <= K - 1; len++) {
                    // 菱型の範囲を横に見ていき、upとdownをチェックする
                    // ex) x, yが2, 2、K=2のとき
                    // 左図の@がx, yの地点。これを中心に、長さ2の菱型が入るか調べればOK(右図)。
                    // 1 2 3 1 2 3
                    // 1 X X X x o x
                    // 2 X @ X o o o
                    // 3 X X X x o x
                    // よって、上から2番目の列を横に見ていき、
                    // 順にup/downがどちらも1以上、2以上、1以上あればOK
                    if (up[x][y + len] < K - Math.abs(len)
                            || down[x][y + len] < K - Math.abs(len)) {
                        isAllWhite = false;
                        break;
                    }
                }
                if (isAllWhite) {
                    ret++;
                }
            }
        }

        out.println(ret);
        out.close();
    }
}
D問題
  • N人の女子とM人の男子の中から、女子・男子をP・Q人ずつ選んで一つのグループを作る。
    • また、R個の情報(女子xiが男子yiにチョコを上げた時、幸福度がzi上がる)が与えられる。
    • チョコを上げるのは、xiとyiが同じグループのときのみである。
    • このとき、一番幸福度の高い女子と男子のグループを作ったときの幸福度を求めよ。
  • とりあえず全探索…をしたかったけど方法がわからず。bitを使うんだろうけどどう書けばいいのか…
    • bitCountを上手いこと使うんでした。JavaだとInteger.bitCountがある。
    • 1〜1<
    • 解説スライド・解説放送を参考に書いたのが以下。
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
    FastScanner in = new FastScanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Main().calc();
    }
    
    public void calc() {
        int N = in.nextInt();
        int M = in.nextInt();
        int P = in.nextInt();
        int Q = in.nextInt();
        int R = in.nextInt();
        
        int[] x = new int[R];
        int[] y = new int[R];
        int[] z = new int[R];

        // 女子fと男子mが同グループにいたとき得られる幸福度をpoint[f][m]で表す
        int[][] point = new int[N][M];
        
        for (int i = 0; i < R; i++) {
            x[i] =in.nextInt() - 1;
            y[i] =in.nextInt() - 1;
            z[i] =in.nextInt();
            point[x[i]][y[i]] = z[i];
        }

        int ret = 0;
       
        // 女子を固定して、男子は貪欲法で探索する。
        // まずは女子の組み合わせを作るため、N人からP人を選ぶ。
        for (int i = 1; i <= (1<<N); i++) {
            // iのbitがP個立っていなければ(=P人選択されていなければ)スキップ
            if (Integer.bitCount(i) != P) {
                continue;
            }

            // malePoint[i]は男子iを入れたことで増加する幸福度を表す
            int[] malePoint = new int[M];
 
            // 女子fが選択されているか確認
            for (int f = 0; f < N; f++) {
                // iのf番目のbitが立っていなければスキップ
                if ((i >> f) % 2 == 0) {
                    continue;
                }
                
                // 続いて男子mを入れたときの幸福度をmalePoint[m]に格納
                for (int m = 0; m < M; m++) {
                    malePoint[m] += point[f][m];
                }
            }

            // malePointを昇順にソート
            Arrays.sort(malePoint);
            
            int tmp = 0;

            // 大きい方からQ個足した結果が、この女子の組み合わせにおける幸福度の最大値
            for (int j = M - 1; j >= M - Q; j--) {
                tmp += malePoint[j];
            }

            // 答えの更新
            ret = Math.max(ret, tmp);
        }

        out.println(ret);
        out.close();
    }
}