新人SEの学習記録

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

参加記録:AtCoder Regular Contest #31

[参加記録] AtCoder Regular Contest #31

コンテストURL


Welcome to AtCoder Regular Contest 031 - AtCoder Regular Contest 031 | AtCoder

結果

  • A, Bの2問解答の200点。
    • B問題に時間が掛かり過ぎたのが無念。

プログラム

A問題
  • 入力された文字列が回文かどうか判定する。
  • 自分の解答は以下。前と後ろを一文字ずつ判定していく。
import java.util.Scanner;

public class Main {

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

        String S = scan.next();
        char[] name = S.toCharArray();
        boolean flag = true;

        for (int i = 0; i < name.length / 2; i++) {
            if (name[i] != name[name.length-1-i]) {
                flag = false;
                break;
            }
        }
        
        if (flag)
            System.out.println("YES");
        else
            System.out.println("NO");

        scan.close();
    }
}
B問題
  • 10x10の陸(o)と海(x)のマップが与えられ、1箇所海を陸地にしたら陸地が全部繋がるような箇所があるか判定する。
    • 繋がっている=上下左右のどれかのマスで陸地が隣接している
    • 繋がっている陸地(島)を全て繋げるような埋め立て箇所を見つける必要がある。
  • 自分の解答は以下。
    • 条件式を後から付け足しまくったのでひどいコードだけど…
    • 島の座標をリストに入れ、各島の座標リストをリスト(list)に入れている。
    • 島と島で1箇所埋め立てれば陸続きになるような座標があるか探し、その座標が他の島と島にも適用されるか判定する。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static boolean flag[][] = new boolean[10][10];
    static char A[][] = new char[10][10];
    static List<List<Pos>> list = new ArrayList<List<Pos>>();

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

    public void run() {
        Scanner scan = new Scanner(System.in);

        for (int i = 0; i < 10; i++) {
            A[i] = scan.next().toCharArray();
        }

        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (flag[i][j]) {
                    continue;
                }

                if (A[i][j] == 'x') {
                    flag[i][j] = true;
                } else {
                    list.add(new ArrayList<Main.Pos>());
                    saiki(i, j);
                }
            }
        }

        if (list.size() == 1) {
            System.out.println("YES");
        } else if (list.size() > 4) {
            System.out.println("NO");
        } else {
            List<Pos> ansList = new ArrayList<Main.Pos>();
            for (int i = 0; i < list.size() - 1; i++) {
                List<Pos> plist1 = list.get(i);
                List<Pos> plist2 = list.get(i + 1);

                if (ansList.size() == 0) {
                    for (Pos p1 : plist1) {
                        for (Pos p2 : plist2) {
                            List<Pos> ret = judge(p1, p2);
                            if (ret != null) {
                                for (Pos r : ret) {
                                        ansList.add(r);
                                }
                            }
                        }
                    }
                } else {
                    List<Pos> newAnsList = new ArrayList<Main.Pos>();
                    for (Pos p1 : plist1) {
                        for (Pos p2 : plist2) {
                            List<Pos> ret = judge(p1, p2);
                            if (ret != null) {
                                for (Pos r : ret) {
                                    newAnsList.add(r);
                                }
                            }
                        }
                    }
                    
                    List<Pos> newNewAns = new ArrayList<Main.Pos>();

                    for (Pos an : ansList) {
                        for (Pos an2 : newAnsList)
                            if (an.x == an2.x && an.y == an2.y) {
                                newNewAns.add(an2);
                         }
                    }

                    ansList = newNewAns;
                }

                if (ansList.size() == 0)
                    break;
            }

            if (ansList.size() > 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

        scan.close();
    }

    public boolean judge2(List<Pos> l1, List<Pos> l2, Pos p) {
        boolean flag = false;
        for (Pos p1 : l1) {
            if (judgebool(p1, p)) {
                flag = true;
                break;
            }
        }

        if (!flag) {
            return false;
        }

        flag = false;

        for (Pos p2 : l2) {
            if (judgebool(p2, p)) {
                flag = true;
                break;
            }
        }
        return flag;
    }

    public List<Pos> judge(Pos p1, Pos p2) {
        List<Pos> ret = new ArrayList<Main.Pos>();
        if (p1.x == p2.x && Math.abs(p1.y - p2.y) == 2) {
            ret.add(new Pos(p1.x, (p1.y + p2.y) / 2));
        } else if (p1.y == p2.y && Math.abs(p1.x - p2.x) == 2) {
            ret.add(new Pos((p1.x + p2.x) / 2, p1.y));
        } else if (Math.abs(p1.x - p2.x) == 1 && Math.abs(p1.y - p2.y) == 1) {
            Pos tmp;
            if (p1.y > p2.y) {
                tmp = p1;
                p1 = p2;
                p2 = tmp;
            }

            ret.add(new Pos(p1.x, p2.y));
            ret.add(new Pos(p2.x, p1.y));
        }

        if (ret.size() == 0)
            return null;
        else
            return ret;
    }

    public boolean judgebool(Pos p1, Pos p2) {
        if (p1.x == p2.x && Math.abs(p1.y - p2.y) == 2) {
            return true;
        } else if (p1.y == p2.y && Math.abs(p1.x - p2.x) == 2) {
            return true;
        } else if (Math.abs(p1.x - p2.x) == 1 && Math.abs(p1.y - p2.y) == 1) {
            return true;
        }

        return false;
    }

    public void saiki(int i, int j) {
        if (flag[i][j])
            return;

        flag[i][j] = true;

        if (A[i][j] == 'x')
            return;

        List<Main.Pos> poslist = list.get(list.size() - 1);
        poslist.add(new Pos(i, j));

        if (i > 0)
            saiki(i - 1, j);
        if (i < 9)
            saiki(i + 1, j);
        if (j > 0)
            saiki(i, j - 1);
        if (j < 9)
            saiki(i, j + 1);

    }

    class Pos {
        int x;
        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "[" + x + ", " + y + "]";
        }
    }
}
  • 解説の解答
    • 埋め立てを行う地点を全探索。
    • 全座標について埋め立てを行ってみて、全ての陸地が陸続きになっているかを判定する。
    • さっきのプログラムの「ここを埋め立てるとこことここの島が繋がって…」みたいな面倒な判定が不要
    • 言われて見れば…という感じですが、全く思いつきませんでしたorz
    • 適当に作ってみたプログラムが以下。もっとシンプルに書けるかも
import java.util.Scanner;

public class Main {

    static boolean flag[][];
    static char A[][];
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        A = new char[10][10];

        for (int i = 0; i < 10; i++) {
            A[i] = scan.next().toCharArray();
        }
        
        boolean ans = false;

        LOOP: for (int x = 0; x < 10; x++) {
            for (int y = 0; y < 10; y++) {
                
                if (A[x][y] == 'o') {
                    continue;
                }

                flag = new boolean[10][10];
                
                A[x][y] = 'o';
                int shima = 0;
                
                LOOP2: for (int i = 0; i < 10; i++) {
                    for (int j = 0; j < 10; j++) {
                        if (flag[i][j]) {
                            continue;
                        }

                        if (A[i][j] == 'x') {
                            flag[i][j] = true;
                        } else {
                            if (shima == 0) {
                                saiki(i, j);
                                shima++;
                            }
                            else {
                                shima++;
                                break LOOP2;
                            }
                            
                        }
                    }
                }
                
                if (shima == 1) {
                    ans = true;
                    break LOOP;
                }
                
                A[x][y] = 'x';

            }
        }

        if (ans) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
        scan.close();
    }
    
    public static void saiki(int i, int j) {
        if (flag[i][j])
            return;

        flag[i][j] = true;

        if (A[i][j] == 'x')
            return;

        if (i > 0)
            saiki(i - 1, j);
        if (i < 9)
            saiki(i + 1, j);
        if (j > 0)
            saiki(i, j - 1);
        if (j < 9)
            saiki(i, j + 1);

    }
}