読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

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

参加記録:Code Thanks Festival 2014 A、CodeIQ

[参加記録] Code Thanks Festival 2014 A

コンテストURL


Welcome to code thanks festival 2014 A日程(オープンコンテスト) - code thanks festival 2014 A日程(オープンコンテスト) | AtCoder

結果

  • A〜F完答、G部分点の630点でした。
    • 難易度低めとのことでしたが、やっぱりこれくらいの難易度だとありがたく楽しめました。

プログラム

A問題
  • 亀と鶴の数がA, Bが与えられるので、足の総本数を求める。
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(A * 4 + B * 2);
        
        scan.close();
    }

}
B問題
  • 一分間にA, B, C個バッジを作れる製造機が3つあり、順番に動かすときN個のバッジを作る最短時間を求める。
  • 以下プログラム。
    • 降順にソートするため、A, B, Cを配列Dに入れてマイナスしてソート。
public class Main {

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

        int N = scan.nextInt();
        int[] D = new int[3];
        D[0] = -(scan.nextInt());
        D[1] = -(scan.nextInt());
        D[2] = -(scan.nextInt());

        Arrays.sort(D);

        int index = 0;
        int time = 0;
        
        while (N > 0) {
            time++;
            N += D[index];
            index = (index + 1) % 3;
        }
        
        System.out.println(time);
        
        scan.close();
    }

}
C問題
  • コンテストでN個の問題中M個解けたとき、合計点を求める。
    • 問題Nの配点は配列Pで、解けたM個の問題番号は配列Sで与えられる。
  • 以下プログラム。
    • P[S[i] - 1]を足していく。-1するのは問題番号が1オリジンのため。
public class Main {

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

        int N = scan.nextInt();
        int M = scan.nextInt();
        int P[] = new int[N];
        int S[] = new int[M];
       
        for (int i = 0; i < N; i++) {
            P[i] = scan.nextInt();
        }

        for (int i = 0; i < M; i++) {
            S[i] = scan.nextInt();
        }
        
        int result = 0;
        
        for (int i = 0; i < M; i++) {
            result += P[S[i] - 1];
        }
        
        System.out.println(result);
        
        scan.close();
    }

}
D問題
  • N個の駅があり、持っている定期券の範囲と乗りたい区間がQ個与えられ、それぞれで掛かる料金を求める。
    • 配列a, bが持っている定期券の範囲、配列s, tが乗りたい区間。料金は1駅間100円一律。
  • 以下プログラム。
    • ひと駅ずつ判定していたら間に合わなかったので場合分け。変数名がいろいろひどい。
    • 場合分けでは以下の5つを判定。
  1. 乗車区間が完全に定期券の範囲内。料金は0。
  2. 乗車区間が完全に定期券の範囲外。料金は乗車区間*100。
  3. 後の数駅は定期券の範囲。料金は定期が始まるまでの区間*100。
  4. 前の数駅は定期券の範囲。料金は定期が切れてからの区間*100。
  5. 乗車区間の中間部分が定期券の範囲。料金は(乗車区間-定期範囲)*100。
public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();
        
        int N = scan.nextInt();
        int Q = scan.nextInt();
        int a[] = new int[Q];
        int b[] = new int[Q];
        int s[] = new int[Q];
        int t[] = new int[Q];
       
        for (int i = 0; i < Q; i++) {
            a[i] = scan.nextInt();
            b[i] = scan.nextInt();
            s[i] = scan.nextInt();
            t[i] = scan.nextInt();
        }

        for (int i = 0; i < Q; i++) {
            int start = s[i];
            int end = t[i];
            int startTeiki = a[i];
            int endTeiki = b[i];
            int result = 0;

            if (startTeiki <= start && end <= endTeiki) {
                result = 0;
            }
            else if (endTeiki <= start || end <= startTeiki) {
                result = (end - start) * 100;
            }
            else if (start < startTeiki && startTeiki < end && end <= endTeiki) {
                result = (startTeiki - start) * 100;
            }
            else if (endTeiki < end && startTeiki < start && start <= endTeiki) {
                result = (end - endTeiki) * 100;
            }
            else {
                result = ((end - start) - (endTeiki - startTeiki)) * 100; 
            }

            sb.append(result + "\n");
        }
        
        System.out.print(sb);

        scan.close();
    }
}
E問題
  • R * Cに並べられた石像があり、ある範囲の石像を左に90度回転させる手順がN個与えられる。
    • 最後に南を向いている石像の数Mが与えられるが、N個の手順のうちどれか一つを行うのを忘れてしまっている。
    • どの手順をやり忘れたか、可能性のある手順の番号を全て挙げよ。
    • i番目の手順では、縦ra[i]〜rb[i]、横ca[i]〜cb[i]の範囲の石像を90度回転させる。
  • 以下プログラム。
    • N個の手順全てを実施したときの状態を配列szに格納。0が南。
    • その後、それぞれの手順で回転させる石像の向きを戻してみて、南を向いている石像の数を数える。
    • 数numがMと等しければその手順を忘れている可能性がある。
public class Main {

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

        int R = scan.nextInt();
        int C = scan.nextInt();
        int M = scan.nextInt();
        int N = scan.nextInt();
        int ra[] = new int[N];
        int rb[] = new int[N];
        int ca[] = new int[N];
        int cb[] = new int[N];

        for (int i = 0; i < N; i++) {
            ra[i] = scan.nextInt() - 1;
            rb[i] = scan.nextInt() - 1;
            ca[i] = scan.nextInt() - 1;
            cb[i] = scan.nextInt() - 1;
        }

        int[][] sz = new int[R][C];
        for (int i = 0; i < N; i++) {

            for (int r = ra[i]; r <= rb[i]; r++) {
                for (int c = ca[i]; c <= cb[i]; c++) {
                    sz[r][c] = (sz[r][c] + 1) % 4;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            int[][] sz2 = new int[R][C];
            
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    sz2[r][c] = sz[r][c];
                }
            }
            
            
            for (int r = ra[i]; r <= rb[i]; r++) {
                for (int c = ca[i]; c <= cb[i]; c++) {
                    sz2[r][c]--;
                    if (sz2[r][c] < 0)
                        sz2[r][c] = 3;
                }
            }
            int num = 0;
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    if (sz2[r][c] == 0) {
                        num++;
                    }
                }
            }
            
            if (num == M) {
                System.out.println(i + 1);
            }
        }

        scan.close();
    }
}
F問題
  • N人の参加したコンテストで、自分が最高で何位だったか求める。
    • M個の情報A, Bが与えられ、「AがBよりも順位が高かった」ことを表す。
  • 以下プログラム。
    • 機能のABCで出てきたワーシャルフロイドとやらを使ってみたら解けてしまった。
    • 「最低でも自分よりどれだけ順位が高いか」を距離として表す。
    • 自分自身との距離は0、情報がないor自分より順位が低い場合は距離は無限(MAX)になる。
    • 距離が0でもMAXでもない(=自分より順位が高い)人数を数え、1を足したものが自分の(推測される)最高順位。
public class Main {

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

        int N = scan.nextInt();
        int M = scan.nextInt();
        int A[] = new int[M];
        int B[] = new int[M];
        
        for (int i = 0; i < M; i++) {
            A[i] = scan.nextInt() - 1;
            B[i] = scan.nextInt() - 1;
        }
        
        int[][] dist = new int[N][N];
        int MAX = 999999;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = MAX;
            }
            dist[i][i] = 0;
        }
        
        for (int i = 0; i < M; i++) {
            dist[B[i]][A[i]] = 1;
        }
        
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < N; i++) {
            if (dist[0][i] != 0 && dist[0][i] != MAX) {
                result++;
            }
        }

        System.out.println(result + 1);

        scan.close();
    }

}
G問題
  • N人の(自分より前に並んでいる)乗客とK個の直列に並んだ席があるとき、自分が電車の席に座れる期待値を求める。
    • N人それぞれの「とにかく座りたい」と気分かどうかの確率Pが与えられる。
    • 「とにかく座りたい」気分のとき、空席の中で一番番号の若い席に座る。
    • そうでない(余裕があれば座りたい)気分のとき。空席で両側が空いている席に座る。
  • 以下プログラム
    • 再帰で一人ひとりの行動と埋まった座席を管理しながら期待値を求める。
    • 時間掛かりすぎでTLE。メモ化しようとしたものの埋まった座席とメモとの関連が付けられなくて断念。
    • ACの人の解答を見ると座席の管理はしてないっぽいので、座席の情報は要らないのか…?後で見直す。
public class Main {
    static int N;
    static int K;
    static int P[];
    static boolean seki[];
    static int index;
    static double kitai = 0.0;
 
    public static void saiki(int person, int aki, double prob) {
        if (person == N) {
            kitai += aki * prob;
            return;
        }
        
        if (aki == 0) {
            return;
        }
        
        double tonikaku = prob * (P[person] / 100.0);
        double yoyuu = prob * (1.0 - (P[person] / 100.0));
        
        if (tonikaku != 0.0) {
            int tmp = index;
            seki[index++] = true;
            if (index != K) {
                while (index < K && seki[index]) {
                    index++;
                }
            }
            saiki(person+1, aki-1, tonikaku);
            seki[tmp] = false;
            index = tmp;
        }
        
        if (yoyuu != 0.0) {
            int tmp = -1;
            if (index == 0) {
                tmp = index;
                seki[index++] = true;
                saiki(person+1, aki-1, yoyuu);
                seki[tmp] = false;
                index = tmp;
                
            }
            else if (index == K - 1) {
                if (seki[K - 2] == true) {
                    saiki(person+1, aki, yoyuu);
                }
                else {
                    tmp = index;
                    seki[index++] = true;
                    saiki(person+1, aki-1, yoyuu);
                    seki[tmp] = false;
                    index = tmp;
                }
            }
            else {
                for (int i = index; i < K; i++) {
                    if (seki[i] == true) {
                        continue;
                    }
                    
                    if (i == K - 1) {
                        if (seki[i-1] == false) {
                            tmp = i;
                        }
                        continue;
                    }
 
                    if (seki[i-1] == false && seki[i+1] == false) {
                        tmp = i;
                        break;
                    }
                }
                
                if (tmp >= 0) {
                    seki[tmp] = true;
                    if (index == tmp) {
                        while (seki[index] && index < K) {
                            index++;
                        }
                    }
                    saiki(person+1, aki-1, yoyuu);
                    seki[tmp] = false;
                    if (index > tmp) {
                        index = tmp;
                    }
                }
                else {
                    saiki(person+1, aki, yoyuu);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        N = scan.nextInt();
        K = scan.nextInt();
        P = new int[N];
        seki = new boolean[K];
        index = 0;
        
        for (int i = 0; i < N; i++) {
            P[i] = scan.nextInt();
        }
        
        saiki(0, K, 1.0);
        
        System.out.println(kitai);
        
        scan.close();
    }
 
}

[プログラム作成] CodeIQ


挑戦者求む!【アルゴリズム】サルベジオン社で宇宙船のデータを救え by The Essence of Programming 結城 浩│CodeIQ

  • サルベジオン問題。面白かった。


挑戦者求む!【言語不問】私をエンジニア界の巫女にして! by 私を天界に連れてって実行委員会 問題作成:tbpgr│CodeIQ

  • Sエナジー送っときました。