ACM/ICPC 2008 国内予選

問題A　『等しい合計点』

無難に全探索。

import java.io.*;
import java.util.*;

public class ProblemA {
    
    public static void main(String[] args) {
        try {
            Scanner in = new Scanner(new File("A.in"));
            
            while (true) {
                int n = in.nextInt();
                int m = in.nextInt();
                
                // 終了条件
                if (n == 0 && m == 0)
                    break;
                
                // 持っているカードの管理
                int[] tarou = new int[n];
                int[] hanako = new int[m];
                
                // 合計点を格納
                int sumTarou = 0;
                int sumHanako = 0;
                
                // 入力の読み取りと合計点の計算
                for (int i = 0; i < n; i++) {
                    tarou[i] = in.nextInt();
                    sumTarou += tarou[i];
                }
                for (int i = 0; i < m; i++) {
                    hanako[i] = in.nextInt();
                    sumHanako += hanako[i];
                }
                
                // 持っているカードをソートしておく
                Arrays.sort(tarou);
                Arrays.sort(hanako);
                
                // 交換するカードの点数の和の最小値を格納
                int min = 10000;
                
                // 交換するカードを記録
                int tarouAns = 0, hanakoAns = 0;
                
                // 題意の交換方法が存在すればtrue
                boolean ok = false;
                
                // 全探索
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        // 交換してみる
                        sumTarou = sumTarou - tarou[i] + hanako[j];
                        sumHanako = sumHanako - hanako[j] + tarou[i];
                        
                        // 合計点が一緒だったら
                        if (sumTarou == sumHanako) {
                            // 交換するカードの点数の和が最小だったら
                            if (min > tarou[i] + hanako[j]) {
                                min = tarou[i] + hanako[j];
                                tarouAns = tarou[i];
                                hanakoAns = hanako[j];
                                ok = true;
                            }
                        }
                        
                        // 交換したのを元に戻す
                        sumTarou = sumTarou + tarou[i] - hanako[j];
                        sumHanako = sumHanako + hanako[j] - tarou[i];
                    }
                }
                
                // 結果の出力
                if (ok)
                    System.out.println(tarouAns + " " + hanakoAns);
                else
                    System.out.println("-1");
            }
            
        } catch(Exception e) {
            System.err.println(e);
        }
    }

}

問題B　『月曜土曜素因数』

まずは問題文をしっかり読む。

月曜土曜数を順番に生成していって、入力数の約数かどうかを確認。

約数なら、さらに素因数であるかどうかを確認すればOK。

素因数の確認は、それまでの月曜土曜数で割り切れるかどうかを確認すれば良い。

import java.util.*;
import java.io.*;

public class ProblemB {

    public static void main(String[] args) {
        try {
            Scanner in = new Scanner(new File("B.in"));
            
            while(true) {
                int num = in.nextInt();
                
                // 終了条件
                if (num == 1)
                    break;
                
                int monNum = 0, satNum = 0;
                int[] primeAns = new int[10000];
                int pt = 0;
                
                // 6が月曜土曜素因数かどうか
                if (num % 6 == 0) {
                    primeAns[pt] = 6;
                    pt++;
                }
    
                for (int i = 1; 7 * i < num; i++) {
                    // 月曜数の生成
                    monNum = 7 * i + 1;
                    
                    // この月曜数が入力数の因数かどうか
                    if (num % monNum == 0) {
                        // この月曜数が入力数の素因数かどうか
                        boolean thisIsPrime = true;
                        if (monNum % 6 == 0)
                            thisIsPrime = false;
                        for (int j = 1; j < i; j++) {
                            if (monNum % (7 * j + 1) == 0 || monNum % (7 * j + 6) == 0) {
                                thisIsPrime = false;
                                break;
                            }
                        }
                        // 素因数なら記録
                        if (thisIsPrime) {
                            primeAns[pt] = monNum;
                            pt++;
                        }
                    }
                    
                    // 土曜数の生成
                    satNum = 7 * i + 6;
                    
                    // この土曜数が入力数の因数かどうか
                    if (num % satNum == 0) {
                        // この土曜数が入力数の素因数かどうか
                        boolean thisIsPrime = true;
                        if (satNum % 6 == 0)
                            thisIsPrime = false;
                        for (int j = 1; j < i; j++) {
                            if (satNum % (7 * j + 1) == 0 || satNum % (7 * j + 6) == 0) {
                                thisIsPrime = false;
                                break;
                            }
                        }
                        // 素因数なら記録
                        if (thisIsPrime) {
                            primeAns[pt] = satNum;
                            pt++;
                        }
                    }
                }
                
                // 結果の出力
                System.out.print(num + ":");
                if (pt == 0)
                    System.out.println(" " + num);
                else {
                    for (int i = 0; i < pt; i++)
                        System.out.print(" " + primeAns[i]);
                    System.out.println();
                }
            }
            
        } catch(Exception e) {
            System.err.println(e);
        }
        
    }

}

問題C　『如何に汝を満足せしめむ？いざ数え上げむ…』

replaceAll()を使って、順次置換していく。

import java.util.*;
import java.io.*;

public class ProblemC {

    public static void main(String[] args) {
        try {
            Scanner in = new Scanner(new File("C.in"));
            
            while (true) {
                // 入力の読み取り
                String str = in.nextLine();
                
                // 終了条件
                if (str.equals("."))
                    break;
                
                int count = 0;
                
                for (int p = 0; p < 3; p++) {
                    for (int q = 0; q < 3; q++) {
                        for (int r = 0; r < 3; r++) {
                            String expr = str.replaceAll("P", ""+p);
                            expr = expr.replaceAll("Q", ""+q);
                            expr = expr.replaceAll("R", ""+r);
                            
                            if (analyze(expr) == 2)
                                count++;
                        }
                    }
                }
                
                System.out.println(count);
            }
            
        } catch (Exception e) {
            System.err.println(e);
        }
    }
    
    public static int analyze(String expr) {
        String start = expr;
        
        // --の消去
        expr = expr.replaceAll("--", "");
        
        // 否定の処理
        expr = expr.replaceAll("-0", "2");
        expr = expr.replaceAll("-1", "1");
        expr = expr.replaceAll("-2", "0");
        
        // 論理積の処理
        expr = expr.replaceAll("\\(0\\*0\\)", "0");
        expr = expr.replaceAll("\\(0\\*1\\)", "0");
        expr = expr.replaceAll("\\(0\\*2\\)", "0");
        expr = expr.replaceAll("\\(1\\*0\\)", "0");
        expr = expr.replaceAll("\\(1\\*1\\)", "1");
        expr = expr.replaceAll("\\(1\\*2\\)", "1");
        expr = expr.replaceAll("\\(2\\*0\\)", "0");
        expr = expr.replaceAll("\\(2\\*1\\)", "1");
        expr = expr.replaceAll("\\(2\\*2\\)", "2");
        
        // 論理和の処理
        expr = expr.replaceAll("\\(0\\+0\\)", "0");
        expr = expr.replaceAll("\\(0\\+1\\)", "1");
        expr = expr.replaceAll("\\(0\\+2\\)", "2");
        expr = expr.replaceAll("\\(1\\+0\\)", "1");
        expr = expr.replaceAll("\\(1\\+1\\)", "1");
        expr = expr.replaceAll("\\(1\\+2\\)", "2");
        expr = expr.replaceAll("\\(2\\+0\\)", "2");
        expr = expr.replaceAll("\\(2\\+1\\)", "2");
        expr = expr.replaceAll("\\(2\\+2\\)", "2");
        
        if (expr.equals(start))
            return Integer.parseInt(expr);
        else
            return analyze(expr);
    }

}

問題D　『ちょろちょろロボット』

ロボットの向き毎にノード（4個）を作成し、dijkstraにかけるだけ。

import java.util.*;
import java.io.*;

public class problemD {

    public static void main(String[] args) {
        try {
            Scanner in = new Scanner(new File("D.in"));

            while(true) {
                int w = in.nextInt();
                int h = in.nextInt();
                
                // 終了条件
                if (w == 0 && h == 0)
                    break;
                
                // mapの生成
                Node[][] north = new Node[h][w];
                Node[][] east = new Node[h][w];
                Node[][] south = new Node[h][w];
                Node[][] west = new Node[h][w];
                
                //　命令表
                int[][] com = new int[h][w];
                
                // 経路が見つかっていないノードの集合U（自然順序付け）
                Queue groupU = new PriorityQueue();
                
                // mapの初期化
                for (int i = 0; i < h; i++) {
                    for (int j = 0; j < w; j++) {
                        // 命令表の作成
                        com[i][j] = in.nextInt();
                        
                        // ノードの作成
                        north[i][j] = new Node(""+i+"-"+j+"u");
                        east[i][j] = new Node(""+i+"-"+j+"r");
                        south[i][j] = new Node(""+i+"-"+j+"d");
                        west[i][j] = new Node(""+i+"-"+j+"l");
                        
                        // 集合Uに格納する
                        groupU.add(north[i][j]);
                        groupU.add(east[i][j]);
                        groupU.add(south[i][j]);
                        groupU.add(west[i][j]);
                    }
                }
                
                // コストの読み取り
                int c0 = in.nextInt();
                int c1 = in.nextInt();
                int c2 = in.nextInt();
                int c3 = in.nextInt();
            
                // エッジを加える
                for (int i = 0; i < h; i++) {
                    for (int j = 0; j < w; j++) {
                        int straight = c0;
                        int right = c1;
                        int reverse = c2;
                        int left = c3;
                        
                        // 命令ごとにコストを設定
                        if (com[i][j] == 0)
                            straight = 0;
                        else if (com[i][j] == 1)
                            right = 0;
                        else if (com[i][j] == 2)
                            reverse = 0;
                        else if (com[i][j] == 3)
                            left = 0;
                        
                        if (i - 1 >= 0) {
                            north[i][j].addEdge(north[i - 1][j], straight);
                            west[i][j].addEdge(north[i - 1][j], right);
                            south[i][j].addEdge(north[i - 1][j], reverse);
                            east[i][j].addEdge(north[i - 1][j], left);
                        }
                        
                        if (j + 1 < w) {
                            east[i][j].addEdge(east[i][j + 1], straight);
                            north[i][j].addEdge(east[i][j + 1], right);
                            west[i][j].addEdge(east[i][j + 1], reverse);
                            south[i][j].addEdge(east[i][j + 1], left);
                        }
                        
                        if (i + 1 < h) {
                            south[i][j].addEdge(south[i + 1][j], straight);
                            east[i][j].addEdge(south[i + 1][j], right);
                            north[i][j].addEdge(south[i + 1][j], reverse);
                            west[i][j].addEdge(south[i + 1][j], left);
                        }
                        
                        if (j - 1 >= 0) {
                            west[i][j].addEdge(west[i][j - 1], straight);
                            south[i][j].addEdge(west[i][j - 1], right);
                            north[i][j].addEdge(west[i][j - 1], left);
                            east[i][j].addEdge(west[i][j - 1], reverse);
                        }
                    }
                }
                
                List groupV = dijkstra(groupU, east[0][0]);
                        
                // ゴールへの入り方は東向きか南向きのみ
                Node goalEast = (Node) groupV.get(groupV.indexOf(east[h - 1][w - 1]));
                Node goalSouth = (Node) groupV.get(groupV.indexOf(south[h - 1][w - 1]));
                
                System.out.println(Math.min(goalEast.distance, goalSouth.distance));
            }
        } catch(Exception e) {
            System.err.println(e);
        }    
    }
    
    public static List dijkstra(Queue groupU, Node start) {
        // 最短経路が確定している集合V
        List groupV = new ArrayList();
        
        // 出発点の距離を0にする
        start.distance = 0;
        start.routeFound = true;
        
        // startノードをgroupUの先頭に持ってくる
        groupU.remove(start);
        groupU.add(start);
        
        while(groupU.size() > 0) {
            // 集合Uから最も距離の小さいノードを取り出す
            Node st = (Node) groupU.poll();
            
            // これ以上先に進めない（連結グラフでない）
            if (!st.routeFound)
                break;
            
            // stノードを集合Vに追加する
            st.inV = true;
            groupV.add(st);
            
            for (int i = 0; i < st.arrows.size(); i++) {
                Edge arrow = (Edge) st.arrows.get(i);
                Node target = arrow.target;
                int weight = arrow.weight;
                
                if (!target.inV) {
                    if (!target.routeFound || target.distance > (st.distance + weight)) {
                        
                        // 最短経路の更新
                        target.distance = st.distance + weight;
                        target.routeFound = true;
                        
                        // groupUを最短経路順にソートしておく
                        groupU.remove(target);
                        groupU.add(target);
                        }
                }
            }
            
        }
        
        return groupV;
    }

}

class Node implements Comparable {
    String name;    // ノード名
    int distance;    // 現時点での最短経路の距離
    List arrows;    // ノードから出ているエッジのリスト
    boolean routeFound;    // 最短経路が見つかっているか
    boolean inV;    // 最短路が見つかっていれば集合Vに含まれる
    
    // コンストラクタ
    public Node(String name) {
        this.name = name;
        this.distance = Integer.MAX_VALUE;
        this.arrows = new ArrayList();
        this.routeFound = false;
        this.inV = false;
    }
    
    // このノードを出発点とするエッジを追加
    public void addEdge(Node target, int weight) {
        arrows.add(new Edge(target, weight));
    }

    // distanceに応じてソートする
    public int compareTo(Object o) {
        return this.distance - ((Node) o).distance;
    }
}

class Edge {
    Node target;
    int weight;
    
    // コンストラクタ
    public Edge(Node target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}