今日の競プロ(2020/4/10) - gyouzasushi’s diary

JOI 1問

GCJ 2問

Codeforces 4問 rating : 1940 → 1936 (-4)

JOI2007春合宿 Day3 Route: 象使い

問題

しんどかった。(直前にいた頂点, 今いる頂点)を頂点とするグラフをつくって、Dijkstra。

提出

Google Code Jam 2019 Round 1A A - Pylons

問題

$(R,C)=(4,4)$ のときだけ上手くいかなかったけど、このサイズならギリギリ常識的な時間で全探索できたのでセーフ。

提出

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << ": ";
        int r, c;
        cin >> r >> c;
        bool rev = r > c;
        if (rev) swap(r, c);
        vector<pair<int, int>> ans;
        if (r == 4 && c == 4) {
            cout << "POSSIBLE" << endl;
            cout << 4 << " " << 3 << endl;
            cout << 3 << " " << 1 << endl;
            cout << 4 << " " << 4 << endl;
            cout << 3 << " " << 2 << endl;
            cout << 2 << " " << 4 << endl;
            cout << 4 << " " << 1 << endl;
            cout << 2 << " " << 2 << endl;
            cout << 3 << " " << 4 << endl;
            cout << 1 << " " << 1 << endl;
            cout << 2 << " " << 3 << endl;
            cout << 4 << " " << 2 << endl;
            cout << 1 << " " << 3 << endl;
            cout << 2 << " " << 1 << endl;
            cout << 1 << " " << 4 << endl;
            cout << 3 << " " << 3 << endl;
            cout << 1 << " " << 2 << endl;
        } else if (r == c && c % 2 == 0 && c > 4) {
            cout << "POSSIBLE" << endl;
            rep(k, c) {
                rep(i, r) {
                    int j = (k + (i % 2) * 3) % c;
                    ans.emplace_back(i + 1, j + 1);
                }
            }
            for (auto p : ans) {
                if (rev)
                    cout << p.second << " " << p.first << endl;
                else
                    cout << p.first << " " << p.second << endl;
            }
        } else if (r >= 3 && c >= 4) {
            cout << "POSSIBLE" << endl;
            rep(k, c) {
                rep(i, r) {
                    int j = (k + (i % 2) * 2) % c;
                    ans.emplace_back(i + 1, j + 1);
                }
            }
            for (auto p : ans) {
                if (rev)
                    cout << p.second << " " << p.first << endl;
                else
                    cout << p.first << " " << p.second << endl;
            }
        } else if (r == 2 && c >= 5) {
            cout << "POSSIBLE" << endl;
            rep(k, c) {
                rep(i, r) {
                    int j = (k + (i % 2) * 3) % c;
                    ans.emplace_back(i + 1, j + 1);
                }
            }

            for (auto p : ans) {
                if (rev)
                    cout << p.second << " " << p.first << endl;
                else
                    cout << p.first << " " << p.second << endl;
            }
        } else {
            cout << "IMPOSSIBLE" << endl;
        }
    }
}

Google Code Jam 2019 Round 1A C - Alien Rhyme

問題

長いsuffixから貪欲にペアにしていく。

提出

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}

int main() {
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << ": ";
        int n;
        cin >> n;
        map<string, int> mp;
        rep(_, n) {
            string s;
            cin >> s;
            reverse(all(s));
            string t = "";
            for (char c : s) {
                t += c;
                mp[t]++;
            }
        }

        int ans = 0;
        for (auto itr = rbegin(mp); itr != rend(mp); itr++) {
            string s = (*itr).first;
            if (mp[s] >= 2) {
                ans += 2;
                string t = "";
                for (char c : s) {
                    t += c;
                    mp[t] -= 2;
                }
            }
        }
        cout << ans << endl;
    }
}