ICPC予選

ICPC予選突破無理でした。解けたのは3問。まあ、ほとんどまともに練習していかなかったから当然といえば当然だけど。

問題は

http://icpc.tanaka.ecc.u-tokyo.ac.jp/icpc2008/contest/all_ja.html

まず、Aは、手札から一枚カードを交換して手札の合計値を相手と同じ数にするという問題。普通に全通り試して終了。

Bは、数が 7i+{1,6} しか無い世界で素因数分解する問題なんだけど、最初は問題の意味が理解できなかったのでチームメイトにコーディングを任せて問題を読んでいたら、もうすぐできそうということになったので、CやDの問題の解き方を考え始める。

Bが予想以上に手間取っているようだったので、先にCをすることに。Cは、式をパースせよという問題。簡単なパーサなら書いたことがあったのですぐに終了。

Dは、ロボットをマップの左上から右下に導くためのコストの最小値を求める問題。ダイクストラで出来そうだと思って書き始める。入力部を書き終えたころに、Bのデバッグができたと言われたので一旦中断してBにもどってコンパイル&実行。無事にBが通った。ということで全力でDを解く体勢に。かなり力技なコードを書いて実行するもバグが発生。しかもなかなか取れない。デバッグするほどコードが複雑化していき、収集がつかなくなる。そのままバグが取れないまま予選終了。

Dは落ち着いてやれば解けそうだっただけに解けなかったのはくやしい。まあ、Dが解けていたとしても予選突破は厳しかっただろうけど。

とりあえず、Dを予選が終ったあとで解いたので、ここに載せておく。サンプルインプットしか通してないけど。

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

struct Node {
    int cost;
    bool marked; 
    Node(): cost(999999999), marked(false) {}
};

struct Vector3 {
    int d, x, y;
    Vector3(int d, int x, int y): d(d), x(x), y(y) {} 
};

int main()
{
    int w, h;
    while (cin >> w >> h, w | h) {
        int field[30][30];
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                cin >> field[i][j];
            }
        }
        int costs[4];
        for (int i = 0; i < 4; ++i) 
            cin >> costs[i];

        multimap<int, Vector3> queue;
        Node nodes[4][30][30];
        nodes[0][0][0].cost = 0;
        queue.insert(make_pair(0, Vector3(0, 0, 0)));
        while (!queue.empty()) {
            Vector3 p(queue.begin()->second);
            queue.erase(queue.begin());
            Node& node = nodes[p.d][p.y][p.x];
            node.marked = true; 
            for (int i = 0; i < 4; ++i) {
                int dx[] = { 1, 0, -1, 0 };
                int dy[] = { 0, 1, 0, -1 };
                int new_d = (p.d + i) % 4; 
                Vector3 next(new_d, p.x+dx[new_d], p.y+dy[new_d]);
                if (next.x < 0 || next.y < 0 || next.x >= w || next.y >= h)
                    continue;
                Node& next_node = nodes[next.d][next.y][next.x];
                if (next_node.marked)
                    continue;
                int cost = node.cost;
                if (i != field[p.y][p.x])
                    cost += costs[i];
                if (cost < next_node.cost) {
                    next_node.cost = cost; 
                    queue.insert(make_pair(cost, next)); 
                }
            }
        }
        cout << min(nodes[0][h-1][w-1].cost, nodes[1][h-1][w-1].cost) << endl;
    }
}