第三回アルゴリズム実技検定参加記

int main() {
    string s[2];
    cin >> s[0] >> s[1];
    string S[2];
    rep(j,2)rep(i,3){
        if(s[j][i] - 'a' >= 0)S[j].push_back(s[j][i]);
        else S[j].push_back(char(s[j][i]-'A'+'a'));
    }
    print(s);
    print(S);
    if(s[0] == s[1]){
        cout << "same" << endl;
    }
    else if(S[0] == S[1]){
        cout << "case-insensitive" << endl;
    }
    else{
        cout << "different" << endl;
    }
}

B - ダイナミック・スコアリング

クエリのたびに人の点数を更新すると間に合いません。誰が何問目を解いたかどうかを管理し、ある人の点数を聞かれたときは更新された点数を足していきます。計算量は $\Theta(QM + N)$ になり間に合います。

提出コード

int main() {
 
    int N, M, Q;
    cin >> N >> M >> Q;
    vec<int> ans(N, 0);
    vec<int> value(M, N);
    vvec<bool> solved(N, vec<bool>(M, false));
    while (Q--) {
        int ord, n, m;
        cin >> ord;
        if (ord == 1) {
            cin >> n;
            n--;
            ll tmp = 0;
            rep(j,M){
                if(solved[n][j]){
                    tmp += value[j];
                }
            }
            cout << tmp << endl;
        } else {
            cin >> n >> m;
            n--, m--;
            if (!solved[n][m]) {
                value[m]--;
                solved[n][m] = true;
            }
        }
    }
}

C - 等比数列

オーバーフローに注意しましょう。Pythonならある程度オーバーフローを気にせず書けます。

提出コード

A,R,N = map(int,input().split())

if(R == 1):
    print(A)
else:
    v = [A]
    for i in range(32):
        v.append(v[-1]*R)
        if(v[-1] > 1e9):
            break
    if N < len(v):
        print(v[N-1])
    else:
        print("large")

D - 電光掲示板

サンプルから数字と文字列の対応をもらっておくのが本質です。

提出コード

int main() {
    int N;
    cin >> N;
    vec<string> S(5);
    rep(i,5){
        cin >> S[i];
    }
    string tehon[] = {
        "####.##.##.####", 
        ".#.##..#..#.###", 
        "###..#####..###", 
        "###..####..####", 
        "#.##.####..#..#", 
        "####..###..####", 
        "####..####.####", 
        "###..#..#..#..#", 
        "####.#####.####", 
        "####.####..####"
    };
    string ans;
    for(int j = 1; j < 4*N+1; j+= 4){
        string tmp;
        rep(i,5)rep(k,3){
            tmp.push_back(S[i][j+k]);
        }
        rep(l,10){
            if(tmp == tehon[l]){
                ans.push_back(char(l + '0'));
            }
        }
    }
    cout << ans << endl;
}

E - スプリンクラー

愚直にクエリに答えても間に合います。

提出コード

int main() {
 
    int N,M,Q;
    cin >> N >> M >> Q;
    vvec<int> G(N);
    rep(i,M){
        int u, v;
        cin >> u >> v;
        u--,v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vec<int> col(N);
    rep(i,N)cin >> col[i];
    while(Q--){
        int ord, x,y;
        cin >> ord;
        if(ord == 1){
            cin >> x;
            x--;
            cout << col[x] << endl;
            for(auto &nv: G[x]){
                col[nv] = col[x];
            }
        }
        else{
            cin >> x >> y;
            x--;
            cout << col[x] << endl;
            col[x] = y;
        }
    }
}

F - 回文行列

i文字目にある文字をmapで管理して左右を確認します。

提出コード

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
 
    int N;
    cin >> N;
    vec<string> S(N);
    vec<map<char,int>> vmp(N);
    rep(i,N){
        cin >> S[i];
        rep(j,N){
            vmp[i][S[i][j]]++;
        }
    }
    string ans;
    string cent;
    rep(l,N){
        int r = N - l - 1;
        if(l > r)break;
        if(l == r){
            cent.push_back(S[l][0]);
            break;
        }
        bool ok = false;
        rep(j,26){
            if(vmp[l][char(j+'a')] > 0 && vmp[r][char(j + 'a')]){
                ans.push_back(char(j + 'a'));
                ok = true;
                break;
            }
        }
        if(!ok){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << cent;
    reverse(all(ans));
    cout << ans << endl;
}

G - グリッド金移動

本番は幅を+200していたのでWAが消えませんでした。一個奥に行ってからいくほうが近道の場合があるので、余裕を持って座標を変換すると解けます。BFSでもダイクストラでも大丈夫です。

提出コード

const int dx[] = {1,0,-1,1,-1,0};
const int dy[] = {1,1,1,0,0,-1};
const int H = 1000;
const int W = 1000;

bool IsIn(int x, int y) {
    return 0 <= x && x < H && 0 <= y && y < W;
}
template<class T> class Dijkstra {
public:
    int N;
    T inf;
    vector<T> cost;
    vector<vector<pair<T, int>>> edge;
 
    Dijkstra(const int N, T inf) : N(N), inf(inf),cost(N), edge(N) {
    }
 
    void make_edge(int from, int to, T w) {
        edge[from].push_back({ w,to });
    }
 
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf;
 
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
 
        while (!pq.empty()) {
            T v = pq.top().first;
            int from = pq.top().second;
            pq.pop();
            for (auto u : edge[from]) {
                T w = v + u.first;
                int to = u.second;
                if (w < cost[to]) {
                    cost[to] = w;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
};

int f(int i, int j){
    return i * H + j;
}

int main() {
    Dijkstra<ll> G(H*W, INFLL);
    char S[H][W];
    rep(i, H)rep(j, W)S[i][j] = '.';

    int N, X, Y;
    cin >> N >> X >> Y;
    X += 250;
    Y += 250;
    S[X][Y] = 'G';
    S[200][200] = 'S';
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        x += 250;
        y += 250;
        S[x][y] = '#';
    }
    rep(i,H)rep(j,W){
        rep(k,6){
            int ni = i + dx[k];
            int nj = j + dy[k];
            if(not IsIn(ni,nj))continue;
            if(S[ni][nj] == '#')continue;
            G.make_edge(f(i,j),f(ni,nj),1);
        }
    }
    G.solve(f(250,250));
    if(G.cost[f(X,Y)] == INFLL){
        cout << -1 << endl;
        return 0;
    }
    cout << G.cost[f(X,Y)] << endl;
}

H - ハードル走

DPですが、少しややこしいです。DPの状態を足をついていくときの最小値を、ジャンプで通過の場合で分けて実装すると楽だと思います。

提出コード

ll dp[100010][2];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
 
    int N,L;
    cin >> N >> L;
    vec<int> S(L+1,0);//ハードルの有無
    rep(i,N){
        int x;
        cin >> x;
        S[x] = 1;
    }
    ll T[3];
    rep(i,3)cin >> T[i];
    rep(i,L+1)rep(j,2)dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i,L+1){
        //0
        {
            ll cost = T[0] + (S[i+1] ? T[2]:0);
            chmin(dp[i+1][0], dp[i][0] + cost);
        }
        //1
        {
            ll cost = T[0] + T[1] + (S[i+2] ? T[2]:0);
            chmin(dp[i+2][0], dp[i][0] + cost);
            //ジャンプして通過の最小値
            chmin(dp[i+1][1], dp[i][0] + T[0]/2+T[1]/2);
        }
        //2
        {
            ll cost = T[0] + 3*T[1] + (S[i+4] ? T[2]: 0);
            chmin(dp[i+4][0], dp[i][0] + cost);
            //ジャンプ
            for(int k = 1; k <= 3; k++){
                cost = T[0]/2 + T[1]/2 + (k-1)*T[1];
                chmin(dp[i+k][1], dp[i][0] + cost);
            }
        }
    }
    cout << min(dp[L][0],dp[L][1]) << endl;
}

I - 行列操作

行と列について、mod Nのみを持っておけば、あとで変換できます。転置は行と列の状態のswapにあたり、行（列）の入れ替えはmod Nの交換だと思えば高速にできます。本番中はオーバーフローにギリギリまで気づけずに困っていました。

提出コード

int main() {
    int N,Q;
    cin >> N >> Q;
    vec<ll> gyo(N);
    vec<ll> retu(N);
    rep(i,N){
        gyo[i] = i;
        retu[i] = i;
    }
    int cnt = 0;
    while(Q--){
        int ord,a,b;
        cin >> ord;
        if(ord == 1){
            cin >> a >> b;
            a--,b--;
            if(cnt&1){
                swap(retu[a],retu[b]);
            }
            else{
                swap(gyo[a],gyo[b]);
            }
        }
        if(ord == 2){
            cin >> a >> b;
            a--,b--;
            if(cnt&1){
                swap(gyo[a],gyo[b]);
            }
            else{
                swap(retu[a],retu[b]);
            }
        }
        if(ord == 3){
            /*転置*/
            cnt++;
        }
        if(ord == 4){
            cin >> a >> b;
            a--,b--;
            if(cnt&1){
                cout << gyo[b] * N + retu[a] << endl;
            }
            else {
                cout << gyo[a] * N + retu[b] << endl;
            }
        }
    }
}

J - 回転寿司

人に着目すると、人が前回にとった寿司の美味しさは前から広義単調減少になります。よって、ある寿司が流れてきたとき、それを取る人は二分探索で高速に計算することができます。

提出コード

int main() {
    int N,M;
    cin >> N >> M;
    vec<int> a(M);
    rep(i,M)cin >> a[i];
    vec<int> v(N,-1);
    vec<int> ans(M,-1);
    rep(i,M){
        int idx = lower_bound(all(v), a[i]) - v.begin();
        idx--;
        if(idx == -1){
            continue;
        }
        v[idx] = a[i];
        ans[i] = N-idx;
    }
    rep(i,M){
        cout << ans[i] << endl;
    }
}

K - コンテナの移動

トップにあるコンテナと、あるコンテナの上下がわかっていれば、コンテナの移動は高速に実装できます。

提出コード

int main() {

    int N, Q;
    cin >> N >> Q;
    vec<int> top(N);
    rep(i,N)top[i] = i;
    //下上
    vec<i_i> conte(2*N);
    rep(i,2*N){
        if(i < N){
            conte[i] = {N+i, -1};
        }
        else{
            conte[i] = {-1, i-N};
        }
    }
    while(Q--){
        int f, t, x;
        cin >> f >> t >> x;
        f--;t--;x--;
        //fromの処理
        int tmp_topf = top[f];
        //topが下になる
        top[f] = conte[x].first;
        //その上はなし
        conte[top[f]].second = -1;

        //toの処理
        //移動先のtopが下になる
        conte[x].first = top[t];
        conte[top[t]].second = x;
        //移動前のtopが移動先のtopになる
        top[t] = tmp_topf;
    }
    vec<int> ans(N);
    rep(i,N){
        int from = N+i;
        while(1){
            int to = conte[from].second;
            if(to == -1)break;
            ans[to] = i+1;
            from = to;
        }
    }
    rep(i,N){
        cout << ans[i] << endl;
    }
}

L - スーパーマーケット

最も手前と次の商品それぞれを持つpriority queue一本ずつを持って更新していくと解けます。

提出コード

int main() {

    int N;
    cin >> N;
    vec<deque<int>> v(N);
    priority_queue<i_i> pq[2];
    rep(i, N) {
        int K;
        cin >> K;
        rep(j, K) {
            int t;
            cin >> t;
            if (j == 0){
                pq[0].push({t, i});
                pq[1].push({t, i});
            }
            if (j == 1) {
                pq[1].push({t, i});
            }
            v[i].push_back(t);
        }
    }
    auto tmp = pq[0];
    int M;
    cin >> M;
    vec<int> a(M), ans(M);
    rep(i, M)cin >> a[i];
    map<int, int> used;
    rep(k, M) {
        if (a[k] == 1) {
            while(not pq[0].empty()){
                int t, idx;
                tie(t, idx) = pq[0].top();
                pq[0].pop();
                if(used[t] > 0)continue;
                if(v[idx].empty())continue;
                ans[k] = t;
                used[t]++;
                v[idx].pop_front();
                if(v[idx].size() > 0)pq[0].push({v[idx][0], idx});
                if(v[idx].size() > 1)pq[1].push({v[idx][1], idx});
                break;
            }
        }
        if (a[k] == 2) {
            while(not pq[1].empty()){
                int t, idx;
                tie(t,idx) = pq[1].top();
                pq[1].pop();
                if(used[t] > 0)continue;
                if(v[idx].empty())continue;
                ans[k] = t;
                used[t]++;
                if(v[idx].front() == t){
                    v[idx].pop_front();
                    if(v[idx].size() > 0)pq[0].push({v[idx][0],idx});
                    if(v[idx].size() > 1)pq[1].push({v[idx][1],idx});
                }
                else{
                    int tmp_top = v[idx].front();
                    v[idx].pop_front();
                    v[idx].pop_front();
                    v[idx].push_front(tmp_top);
                    if(v[idx].size() > 1)pq[1].push({v[idx][1], idx});
                }
                break;
            }
        }
    }
    rep(i,M){
        cout << ans[i] << endl;
    }
}