2020年JOI予選に参加し、420点(100-100-100-100-20)で予選を通過しました。以下にその解説と思考過程とコードを載せます。

A - ポスター (Poster)

回した後に塗っても無駄なので、最初に回してから塗る。回転前と後の座標の関係が問題文中に書いてあるので、それを借りた。

#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;
string  s[505], t[505];
int n;
void rotate() {
    string u[505];
    rep(i, n)u[i].resize(n);
    rep(i, n) {
        rep(j, n) {
            u[j][n - i - 1] = s[i][j];
        }
    }
    rep(i, n)rep(j, n)s[i][j]=u[i][j];
}
int dis() {
    int cnt = 0;
    rep(i, n) {
        rep(j, n) {
            if (s[i][j] != t[i][j])cnt++;
        }
    }
    return cnt;
}

signed main() {
    cin >> n;
    rep(i, n)cin >> s[i];
    rep(i, n)cin >> t[i];

    int ans = dis();
    rotate();
    ans = min(ans, dis() + 1);
    rotate();
    ans = min(ans, dis() + 2);
    rotate();
    ans = min(ans, dis() + 1);
    cout << ans << endl;
}

B - いちご (Strawberry)

Garbage Collector みたいな発想をすると、一番奥以外で折り返す動きがムダであって進むか立ち止まるかしかしなくてよいことがわかる。行きに収穫できるイチゴは帰りにとっても問題ないので、最初に一番奥まで行き後ろから順に収穫すればよい。

あとは各イチゴについて、それが熟していたら収穫し熟していなければ熟すまで待つプログラムを書けば正解できる。

#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
int a[100006], t[100006];
vector<P>V;
signed main() {
    int n; cin >> n;
    rep(i, n) {
        cin >> a[i] >> t[i];
        V.push_back(P(a[i], t[i]));
    }
    sort(V.begin(), V.end());
    int ans = max(V[n - 1].first,V[n-1].second);
    for (int i = n - 1; i > 0; i--) {
        int d = V[i].first - V[i - 1].first;
        ans = max(ans + d, V[i - 1].second);
    }
    ans += V[0].first;
    cout << ans << endl;
}

C - 桁和 (Digit Sum)

操作をグラフに対応させるのはよくあるので、　(参考: https://twitter.com/Zen_Re_Kkyo/status/1203586372365254657) これもグラフに対応させる。あとは連結判定をすればよいので、Union-Findを貼る。

下の実装は5分で考えながらやったので少々ムダが多いです...

#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
int nxt[1000006];

int par[1000006], siz[1000006];
void init(int n) {
    rep(i, n) {
        par[i] = i; siz[i] = 1;
    }
}
int find(int x) {
    if (par[x] == x)return x;
    return par[x] = find(par[x]);
}
void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)return;
    if (siz[x] < siz[y])swap(x, y);
    par[y] = x;
    siz[x] += siz[y];
}

int dgt(int x) {
    if (!x)return 0;
    return x % 10 + dgt(x / 10);
}
signed main() {
    int n; cin >> n;
    rep(i, n)nxt[i + 1] = i+1+dgt(i + 1);
    init(n + 1);
    for (int i = 1; i <= n; i++) {
        if (nxt[i] <= n)unite(i, nxt[i]);
    }
    cout << siz[find(n)] << endl;
}

D - テンキー (Tenkey)

出たよJOI特有の実装がめんどくさい問題

とりあえず現在のあまりと今どこにいるかさえわかれば遷移ができるのでダイクストラができそう、ということでダイクストラをします

#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;
int dp[100006][10];

int tcost(int x, int y) {
    if (x > y)swap(x, y);
    int xi = (x - 1) / 3, yi = (y - 1) / 3;
    int xj = (x - 1) % 3, yj = (y - 1) % 3;
    if (x == 0 && y == 0)return 0;
    else if (x == 0) {
        return yi + yj + 1;
    }
    else return abs(xj - yj) + abs(xi - yi);
}

signed main() {
    int m, r; cin >> m >> r;
    priority_queue<PP, vector<PP>, greater<PP>>Q;
    rep(i, m)rep(j, 10)dp[i][j] = inf;
    dp[0][0] = 0;
    Q.push(PP(0, P(0, 0)));

    while (Q.size()) {
        PP pp = Q.top(); Q.pop();
        int vi = pp.second.first, vj = pp.second.second;
        if (dp[vi][vj] < pp.first)continue;
        rep(i, 10) {
            int ni = (vi * 10 + i) % m, nj = i;
            int C = tcost(vj, i)+1;
            if (dp[ni][nj] > dp[vi][vj] + C) {
                dp[ni][nj] = dp[vi][vj] + C;
                Q.push(PP(dp[ni][nj], P(ni, nj)));
            }
        }
    }
    int ans = inf;
    rep(i, 10)ans = min(ans, dp[r][i]);
    cout << ans << endl;
}

TLが心配だったが542msecで通って一安心。

E - じゃんけん式 (Rock-Scissors-Paper Expression)

問題文を見た瞬間に「うえぇ構文解析...」と思いながら「構文解析　競プロ」でググるとイイ感じの実装が出てくる手元で演算表を作成し、ある程度観察したところ結合法則も分配法則も成り立たずうれしくないことがわかる(成り立ってもうれしくない)

とりあえず全探索を書いて構文解析をコピーして20点を得た。

#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
const int inf = 1e17;
const int mod = 1000000007;
typedef pair<int, int> P;
typedef pair<int, P> PP;
int n; string e; char A; int B;
int add(int x, int y) {
    if (x > y)swap(x, y);
    if (x == 0 && y == 2)return 2;
    else return x;
}
int sub(int x, int y) {
    if (x > y)swap(x, y);
    if (x == 0 && y == 2)return 0;
    return y;
}
int mul(int x, int y) {
    if (x == y)return x;
    return 3 - x - y;
}

int com(char a) {
    if (a == 'R')return 0;
    if (a == 'S')return 1;
    if (a == 'P')return 2;
    return a;
}
int expr(string& s, int& i);
int term(string& s, int& i);
int factor(string& s, int& i);
int number(string& s, int& i);
int expr(string &s, int &i) {
    int val = term(s, i);
    while (s[i] == '+' || s[i] == '-') {
        char op = s[i];
        i++;
        int val2 = term(s, i);
        if (op == '+')val = add(val, val2);
        else val = sub(val, val2);
    }
    return val;
}
int term(string &s, int &i) {
    int val = factor(s, i);
    while (s[i] == '*') {
        i++;
        int val2 = factor(s, i);
        val = mul(val, val2);
    }
    return val;
}
int factor(string &s, int &i) {
    if (s[i] == 'R' || s[i] == 'S' || s[i] == 'P')return number(s, i);
    i++;
    int ret = expr(s, i);
    i++;
    return ret;
}
int number(string &s, int &i) {
    int n = com(s[i++]);
    return n;
}
int ans = 0;
void dfs(string s,int now) {
    if (now == s.size()) {
        int i = 0;
        int res = expr(s, i);
        if (res == B)ans++;
        return;
    }
    if (s[now] == '?') {
        s[now] = 'R'; dfs(s, now + 1);
        s[now] = 'S'; dfs(s, now + 1);
        s[now] = 'P'; dfs(s, now + 1);
        s[now] = '?';
    }
    else dfs(s, now+1);
    
}

void input() {
    cin >> n; cin >> e; cin >> A;
    B = com(A);
}
signed main() {
    input();
    if (n > 16)return 0;
    dfs(e, 0);
    cout << ans << endl;
}

安全圏だと思って安心しながら満点を考えたが未確定の扱いで実装が破滅して投げ出した。

todo: 満点解法の実装

コンテスト後

大量に全完ツイートが流れてきて背筋が凍るが、有志による暫定順位表を見て何とか安心する。

本選に向けてがんばります...

ZenReKkyo Industry

🏭

JOI予選'20参加記