読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 18/19/20

- 18 うーさー暗号

  • 問題概要

文字列の復号をします。
文字列の暗号方法がi文字目の文字をi回右にずらす(Aを2回ずらすとC,Zを1回ずらすとA)という変換をします。
暗号が与えられるので復号した文字列を出力してください。

  • 解説

逆の操作をするだけです。
i回左にずらすだけ,iが52を超える場合とかに気をつければ大丈夫です。

#include<iostream>
#include<string>
using namespace std;


int main(void){
    string s;
    cin >> s;
    int N = (int)s.size();
    for (int i = 0; i < N; i++)
    {
        int k = s[i] - 'A';
        k += 26*(i+1) - (i + 1);
        k %= 26;
        s[i] = 'A' + k;
    }
    cout << s << endl;
    return 0;
}

- 19

  • 問題概要

N個のステージをクリアしたい。全てのステージには難易度と、事前にクリアしておくとそのステージの難易度が半分になるステージが存在する。
全てのステージをクリアするとき、難易度の合計の最小値を求めよという問題です。

  • 解説

この問題を解くのに丸二日かかってます。
ある頂点の入次数は必ず1以下なので,ループが存在しても他のループと絡み合うことがありません。
そこで、ループになっている部分さえ求めてしまえばよいことが分かります。
強連結成分分解という単語というかアルゴリズムがございまして、そちらを使います。
DFSをして根から遠い順に若い番号を頂点につけていき,番号が大きい順から再度DFSをします。
これをすると部分グラフが強連結成分になっている頂点集合を取り出せます。
強連結成分を一つ取りだしたとき,一つのステージだけそのままの難易度でクリアすれば他のステージは半分の難易度でクリアすることができます。
明らかに難易度が一番低いステージをそのままクリアすればいいので,強連結成分のステージ全部をクリアするのに必要な難易度の合計が求められます。
自己ループになっている頂点の難易度が半額になり得ないことに注意してください。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

bool used[100];
int p[100];
int num = 0;
vector<list<int>> good;
vector<list<int>> bad;
int level[100];
void dfs(int s){
    used[s] = true;
    for(auto v :good[s])
    {
        if (used[v])continue;
        dfs(v);
    }
    p[num++] = s;
}

int bfs(int s){

    int res = level[s];
    int mini = res;
    int cnt = 1;
    queue<int> que;
    que.push(s);
    used[s] = true;
    if (bad[s].size() == 0)return level[s] * 2;
    while (que.empty() == false){
        auto v = que.front(); que.pop();
        //cout << v << " ";
        for(auto u: bad[v])
        {
            if (used[u])continue;
            used[u] = true;
            que.push(u);
            res += level[u];
            mini = min(mini, level[u]);
            cnt++;
        }


    }
    if (cnt > 1)res += mini;
//	cout << endl;
    return res;
}
int main(void){
    int N,s,sum=0;
    cin >> N;
    good.resize(N);
    bad.resize(N);
    for (int i = 0; i < N; i++)
    {
        used[i] = false;
        cin >> level[i] >> s;
        s--;
        if (s != i){
            good[s].push_back(i);
            bad[i].push_back(s);
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (used[i])continue;
        dfs(i);
    }
    reverse(p, p + N);
    for (int i = 0; i < N; i++)
    {
        used[i] = false;
    //	cout << p[i] << " ";
    }
    //cout << endl;
    for (int i = 0; i < N; i++)
    {
        if (used[p[i]])continue;
        sum += bfs(p[i]);
    }
    cout << sum / 2 ;
    if (sum & 1)cout << ".5";
    else cout << ".0";
    cout << endl;
    return 0;
}

- 20 砂漠のオアシス

  • 問題概要

N*Nのマスがあり,(1,1)からスタートして1マスずつ移動し(N.N)にゴールしたい。
各マスにはコストが書かれてあって、移動したとき移動先のマスのコストを消費する。
回復マスが一つだけあってそこのマスにたどり着いたときコストを消費した後体力を2倍にできる。
体力を枯らさずにゴールできるか判定せよという問題です。

  • 解説

ルートとして2パターン考えられます。
スタート→ゴール
スタート→オアシスで回復→ゴール
どちらかで体力を枯らさずにゴールできればOKです。
スタート→ゴール,スタート→オアシス、オアシス→ゴールの最短距離を求めておけばこれらの判定は可能です。
ダイクストラ法を使えば計算量はO(N^2 \log N^2 )で求められます

#include<iostream>
#include<queue>
#include<algorithm>
#include<functional>
#include<vector>
#include<map>
using namespace std;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
const int d[5] = { 0, 1, 0, -1, 0 };
int cost[201][201];
int dijkstra(PI s, PI t, int n){
    int dist[202][202];
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dist[i][j] = -1;
    for (int i = 0; i <= n + 1; i++)dist[0][i] = dist[i][0] = dist[n + 1][i] = dist[i][n + 1] = 100000;
    priority_queue<V, vector<V>, greater<V> > que;
    que.push(make_pair(0, s));
    while (que.empty() == false){
        PI v = que.top().second;
        int di = que.top().first;
        que.pop();
        if (dist[v.first][v.second] >= 0)continue;
        dist[v.first][v.second] = di;
        for (int i = 0; i<4; i++){

            PI p = v;
            
            p.first += d[i];
            p.second += d[i + 1];
            if (dist[p.first][p.second] >= 0)continue;
            que.push(make_pair(di + cost[p.first][p.second], p));
        }

    }
    return dist[t.first][t.second];
}

int main(){
    int N;
    int V;
    PI O;
    cin >> N >> V >> O.second >> O.first;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> cost[i][j];
    auto st = make_pair(1, 1);
    auto ed = make_pair(N, N);
    if (dijkstra(st, ed, N)<V){
        cout << "YES" << endl;
    }
    else {
        int U = (V - dijkstra(st, O, N)) * 2;
        if ((O.first != 0 || O.second != 0) && U>0 && U - dijkstra(O, ed, N)>0)
            cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}