UTPC 2012 - くじらにっき++

東京大学プログラミングコンテスト2012に参加していました(オンラインです)

結果は100+100+50+50でした。野暮用で長時間の参加ができなかったとはいえ、部分点があるコンテストなのですから、もっと貪欲に点数を取って行きたいですね。

A: 2012年12月02日

yyyyに含まれる文字を数えたハッシュAと、mmおよびddに含まれる文字を数えたハッシュBを作り、内容が等しいか判定しました。

Rubyのハッシュはデフォルト値が設定できるので、それを使ったほうが楽です (コンテストが終わってから知りました)

# ruby
yyyy,mm,dd = gets.chomp.split('/')
 
ha = {} # ha = Hash.new(0) を使うと楽です
yyyy.each_char do |c|
  ha[c] ||= 0
  ha[c] += 1
end
 
hb = {} # hb = Hash.new(0) を使うと楽です(2回目)
mm.each_char do |c|
  hb[c] ||= 0
  hb[c] += 1
end
 
dd.each_char do |c|
  hb[c] ||= 0
  hb[c] += 1
end
 
puts (ha == hb) ? 'yes' : 'no'

B: 残像に口紅を

最初は部分点を取りに行きました。

後ろから順にでてきた文字について調べていく貪欲法で解けます。

分かりやすい解説をどなたかが書いてくれると思うので、そちらにお任せします。

私は部分点解法から満点解法に書き換えるにあたって、出現しなかった文字の対処に関して方針を変える必要があったので、まず部分点を狙いに行って正解だったと思いました。

// c++ 部分点解法
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cassert>
using namespace std;
 
int main() {
    string str;
    cin >> str;
 
    assert(str.length() == 8); // WAの時の問題切り分けのために使いました
 
    set<char> s; // 出現しなかった文字
    for(int i = 0; i < 8; i++) s.insert('A' + i);
    for(int i = 0; i < 8; i++) s.erase(str[i]);
 
    set<char> t; // 後ろから見ていった時に、既に出現した文字
    vector<char> ans;
 
    for(int i = 7; i >= 0; i--) {
        char c = str[i];
        if(t.count(c) == 0) {
            ans.push_back(c);
            t.insert(c);
        }
        else {
            ans.push_back(*s.begin());
            t.insert(*s.begin());
            s.erase(s.begin());
        }
    }
 
    for(int i = 7; i >= 0; i--) {
        cout << ans[i];
    }
    cout << endl;
}

// c++11 満点解法
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;
 
int main() {
    string str;
    cin >> str;
 
    const int N = str.length();
 
    set<char> s;
    for(int i = 0; i < 8; i++) s.insert('A' + i);
    for(int i = 0; i < N; i++) s.erase(str[i]);
 
    set<char> t;
    vector<char> ans;
 
    for(int i = N - 1; i >= 0; i--) {
        char c = str[i];
        if(t.count(c) == 0) {
            ans.push_back(c);
            t.insert(c);
        }
    }
 
    for (char c : s) {
        ans.push_back(c);
    }
 
    for(int i = 7; i >= 0; i--) {
        cout << ans[i];
    }
    cout << endl;
}

C: 森ですか？

部分点しかとれませんでした。

木が閉路を持つかどうかの判定はUnion Find木を使うと効率的に実装できます。蟻本2版の101ページ中ほどに解説が乗っています。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
bool tree[100][100];
 
class union_find {
    vector<int> a;
public:
    union_find(int N) : a(N, -1) {}
    int find(int x) {
        if (a[x] < 0) return x;
        return a[x] = find(a[x]);
    }
    void unit(int x,int y) {
        x = find(x), y = find(y);
        if (x != y) {
            a[x] += a[y];
            a[y] = x;
        }
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
 
int main() {
    int N, M;
    scanf("%d%d", &N, &M);
 
    for(int i = 0; i < N; i++)
        fill(tree[i], tree[i] + N, true);
 
    while(M--) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        tree[a][b] = !tree[a][b];
        tree[b][a] = !tree[b][a];
        union_find uf(N);
        bool ok = true;
        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                if(tree[i][j]) {
                    if(uf.same(i,j)) ok = false;
                    uf.unit(i,j);
                }
            }
        }
 
        puts(ok?"yes":"no");
    }
}

D: 地図が２枚

幾何ですが、部分点に関しては100*100の正方形と、その1/2縮小図についてのみ考えればよいので、優しそうに見えます。

問題の意味がよく分かっていなかったのですが、サンプル入出力から x_21 * 2 と y_21 が答えになっているような気がしたので、ダメ元で提出してみると部分点を得ることができました。

大きい地図は小さい地図の200%の縮尺なので、当然といえば当然ですよね。

今気づいたのですが、stdioとiostreamを混ぜていて、教育的でないですね。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    int N; cin >> N;
    vector<double> xs(N);
    vector<double> ys(N);
    vector<double> xt(N);
    vector<double> yt(N);
 
    for(int i = 0; i < N; i++) {
        cin >> xs[i] >> ys[i];
    }
 
    for(int i = 0; i < N; i++) {
        cin >> xt[i] >> yt[i];
    }
 
    printf("%.9f %.9f\n", 2 * xt[0], 2 * yt[0]);
}