はまやんはまやんはまやん

hamayanhamayan's blog

MostFrequentLastDigit [SRM747 Easy]

N要素の以下のルールを満たす配列を構築せよ

  • 全ての要素が異なる
  • 0~10^9の数から成る
  • 10で割り切れる数はダメ
  • 全ての2つの要素を取ってきて和をとったときの最下位の桁を集計したときに、dが最も多くなる(タイはダメ)

n≦200, d≦9

解説

d=5のときを考えてみると、最下位が2と3の数があればいい。
最も2+3となる組み合わせが多いのは、n要素をちょうど2つに分けて、片方を2、もう片方を3とすればいい。
これを10で割り切れないよう、全ての要素が異なるように気をつけて実装する。
以下の実装は丁寧にやりすぎた例かもしれない。
floor(d/2)とceil(d/2)を使うが、d≦1のときは0が出てくるので、そこだけ場合分けする。

struct MostFrequentLastDigit {
    vector <int> generate(int n, int d) {
        vector<int> res;
        
        if (2 <= d) {
            rep(i, 0, n / 2) res.push_back(10 * (i+1) + d / 2);
            rep(i, 0, n - n / 2) res.push_back(10000 * (i+1) + d - d / 2);
            return res;
        }

        if (d == 1) {
            rep(i, 0, n / 2) res.push_back(100 * (i + 1) + 6);
            rep(i, 0, n - n / 2) res.push_back(100000 * (i + 1) + 5);
            return res;
        }

        rep(i, 0, n / 2) res.push_back(100 * (i + 1) + 6);
        rep(i, 0, n - n / 2) res.push_back(100000 * (i + 1) + 4);

        return res;
    }
};

大吉数列 (Array of Fortune) [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 B]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b

解法

https://atcoder.jp/contests/ddcc2019-final/submissions/4045691

構築系にはいくつか考え口がある。
まずは、最大ケースを考えてみる。
すると、降順に並べるのが、最大ケースであると分かる。
昇順に並べれば、最小ケースR=0になる。
ここで「最小~最大の間なら全て作れるのではないか」という推測を立てる。
 
構築の手段として、何らかの操作をして、数を調整していく方法が取れないか考えてみる。
N=7, R=3で考えてみる。
「7 6 5 4 3 2 1」は7と4~1, 6と3~1, 5と2~1, 4と1が対応していて、4+3+2+1=10が最大ケース。
この式を見てみると、1~Mの総和が最大ケースで、その中の一部をある操作で消すことができそうという方針で考える。
R=8を作る場合は、2を消して、4+3+1で8を作っていく。
この例で4を消すには、7をうまく動かせば良さそう。
昇順に近づけるには大きい数を後ろに動かせばいいので、7を末尾に持っていくと4が消える。
この状態で3も消したい場合には、同様に6を後ろに動かす。
後ろでは「5 4 3 2 1 7 6」のようにしてもいいのだが、後ろに動かしたあとに数が増える可能性が出てくる。
なので、後ろの方で数を増やさないために、後ろは昇順にすればいい。
 
つまり、アルゴリズムとしては、
1. 降順にソートする
2. 先頭から順にその数に関係する組の個数cntを計算して、cntがR以下であればそのまま残し、Rより大きいなら後ろに動かす
3. 後ろに動かした数は昇順に置く

int N, K; ll R;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> R;
 
    queue<int> top;
    stack<int> back;
 
    rrep(i, N, 1) {
        int cnt = i - K;
        if (0 < cnt and cnt <= R) {
            R -= cnt;
            top.push(i);
        }
        else back.push(i);
    }
 
    if (0 < R) printf("No Luck\n");
    else {
        while (!top.empty()) {
            printf("%d ", top.front()); top.pop();
        }
        while (!back.empty()) {
            printf("%d ", back.top()); back.pop();
        }
        printf("\n");
    }
}

DISCO! [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 D]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d

前提知識

解説

https://atcoder.jp/contests/ddcc2019-final/submissions/4045056

これはやったことが無いと解くのは難しい。
半環問題というのがある。
(正直自分は半環というのをちゃんと理解してないので、正確な表現ではないかもしれない)
この半環問題を解くためにはDPを行列で更新するということに慣れる必要がある。
それに慣れていない場合は、行列累乗による動的計画法高速化を先に勉強することを勧める。
以下、その知識はある前提で説明する。
 
クエリ無しでまずは考える。
dp[i][lst] := i番目の文字まで見ていて、discoのlst番目までできている部分文字列の組み合わせ
このdpを考える。このdpの更新式は
// 後ろに文字を追加しない
dp[i+1][lst] = dp[i][lst]
// discoのc+1番目とi+1番目の文字が等しい場合。最後にdiscoのc+1番目を追加して部分文字列を作る
dp[i+1][c+1] = dp[i][c]
これは行列で表現することができる。
dp[i]→dp[i+1]への遷移に使う行列をm[i]とする。
すると、dp[0]からdp[i]への遷移は順番にm[0], m[1], ..., m[i-1]を使って遷移させる。
行列は、行列だけ先に計算することができるので、m[0]~m[i-1]を計算して、dp[0]と掛け合わせることでも答えが得られる。
この性質をうまく使って、もともとの問題を解く。
 
セグメントツリーに行列を乗せる。
行列を乗せて、計算を行列の積にすることで任意の区間の行列の積が求められる。
クエリ毎に使う行列の積を取ってきて、dp[0]とかけ合わせれば答えが得られる。
 
注意点がいくつかある。
1. 計算時間が結構厳しいので、mod2^32をうまく使うことで剰余計算をなくそう(剰余計算は重い)
unsigned intを使うことで、オーバーフローがちょうどmod2^32になるので、剰余計算を入れる必要がなくなる。
2. セグメントツリーに行列を乗せるが左右が重要なので注意する
自分の実装では左右逆でマージしている

typedef unsigned int mint;
struct func {
    mint m[6][6];
    func(){
        rep(i, 0, 6) rep(j, 0, 6) m[i][j] = 0;
        rep(i, 0, 6) m[i][i] = 1;
    }
    func(int c) {
        rep(i, 0, 6) rep(j, 0, 6) m[i][j] = 0;
        rep(i, 0, 6) m[i][i] = 1;
        m[c + 1][c] = 1;
    }
};
func operator*(func y, func x) {
    
    func res;
    rep(i, 0, 6) rep(j, 0, 6) res.m[i][j] = 0;
    rep(i, 0, 6) rep(j, 0, 6) rep(k, 0, 6) {
        res.m[i][j] = res.m[i][j] + x.m[i][k] * y.m[k][j];
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct SegTree { // [L,R)
    V comp(V l, V r) { return l * r; };
    vector<V> val; SegTree() { val = vector<V>(NV * 2); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return V(); if (x <= l && r <= y)return val[k]; auto A = get(x, y, l, (l + r) / 2, k * 2);
        auto B = get(x, y, (l + r) / 2, r, k * 2 + 1); return comp(A, B);
    }
    void update(int i, V v) { i += NV; val[i] = v; while (i > 1)i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]); }
};



string S; int Q;
int N;
SegTree<func, 1 << 20> st;
string disco = "DISCO";
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> Q;
    N = S.length();
 
    map<char, int> dic;
    rep(i, 0, 5) dic[disco[i]] = i;
 
    rep(i, 0, N) st.update(i, func(dic[S[i]]));
    rep(q, 0, Q) {
        int L, R; cin >> L >> R; L--;
 
        auto f = st.get(L, R);
 
        mint v[6], vv[6];
        rep(i, 0, 6) v[i] = vv[i] = 0;
        v[0] = 1;
 
        rep(i, 0, 6) rep(j, 0, 6) {
            vv[i] = vv[i] + f.m[i][j] * v[j];
        }
 
        printf("%u\n", vv[5]);
    }
}

レース (Race) [DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 A]

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_a

解説

https://atcoder.jp/contests/ddcc2019-final/submissions/4044638

「Sにおいて、- は必ず別の - と隣接して現れる」という奇妙な条件があるので、ここから考える。
この条件は「>->」となっている部分がないということを示している。
最適な方針を考えると、「なるべく氷を連続させる」という方針がある。
「>->」で途中をつなげて「>>>」とすることで伸ばす方法もあるが、これは条件で排除されているので、
既存の氷群を伸ばすことで最適な答えを得る。
ここで伸ばすべきは最も長さが長いものを更に伸ばすべきである。
 
さて、ここまでわかればあとは実装。
自分はランレングス表現にして、処理した。
runLengthEncoding関数でその処理を行っている。

vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.length();
 
    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    rep(i, 1, n) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }
 
    res.push_back({ pre, cnt });
    return res;
}

 
ランレングスにしたら、'>'で個数が最大のものを探してそれを伸ばして、隣の'-'を1つ減らせばいい。
文字列の先頭と末尾は'-'であるとされているので、隣は必ずある。
もし氷群がなかった場合は、末尾を氷群に変えればいい。
 
あとは、run部分でシミュレーションして、答え。

int N; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
 
    auto v = runLengthEncoding(S);
 
    // change
    int n = v.size();
    int ma = -1, id;
    rep(i, 0, n) if(v[i].first == '>' and ma < v[i].second) {
        ma = v[i].second;
        id = i;
    }
 
    if (ma < 0) {
        v[0].second--;
        v.push_back({ '>', 1 });
    } else {
        v[id].second++;
        v[id + 1].second--;
    }
 
    // run
    double ans = 0;
    fore(p, v) {
        if (p.first == '-') ans += p.second;
        else {
            rep(k, 0, p.second) ans += 1.0 / (k + 2);
        }
    }
    printf("%.10f\n", ans);
}

Exam and Wizard [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 C]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c

解説

https://atcoder.jp/contests/keyence2019/submissions/4015448

貪欲に構成していく。
最初はC[i]=B[i]とする。
この段階でCの和smBがsmAを上回っていれば、構築できないので、-1
 
次にd=smA-smBの分をC[i]に足しながら補っていくが、基本的にはC[i]=A[i]となるようにしたい。
なので、A[i]とB[i]の関係性をまずはカウントしよう。
ng := A=Cにできない添字の個数
up := A=Cにするために必要な差分の配列
same := A=Cである添字の個数
A[i] < B[i]なら、どうやってもA[i]=C[i]にできないので、ng++;
B[i] < A[i]なら、差分A[i] - B[i]だけA=Cとできるので、upに追加
Ai] = B[i]なら、same++
 
あとはdをうまく使って、upをなるべくsameにしていきたいが、必要な差分が小さい方から順番にやっていくのがいい。
upをソートして、順番に処理していこう。
 
dが余った場合はそれをどこかに押し付けるが、ans=0のときは押し付け先が無いため、答えが1つ増える。

int N; 
ll A[101010], B[101010];
ll C[101010];
int vis[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
 
    ll smA = 0;
    rep(i, 0, N) smA += A[i];
 
    int ans = 0;
    rep(i, 0, N) C[i] = B[i];
    
    ll smB = 0;
    rep(i, 0, N) smB += B[i];
 
    if (smA < smB) {
        printf("-1\n");
        return;
    }
 
    ll d = smA - smB;
    vector<pair<int,int>> up;
    int ng = 0;
    int same = 0;
    rep(i, 0, N) {
        if (A[i] < B[i]) ng++;
        else if (B[i] < A[i]) up.push_back({ A[i] - B[i],i });
        else same++;
    }
 
    sort(all(up));
    fore(p, up) {
        if (p.first <= d) {
            d -= p.first;
            C[p.second] = A[p.second];
        }
    }
 
    rep(i, 0, N) if (A[i] != C[i]) ans++;
    if (d) {
        if (ans == 0) ans++;
    }
    
    cout << ans << endl;
}

KEYENCE String [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 B]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_b

解説

https://atcoder.jp/contests/keyence2019/submissions/3999565

取り除く領域を全探索する。
c++であれば、文字列操作はsubstrを使うのがおすすめ。
空の連続部分文字列を取り除く操作が許されている場合があるので、入力が既に"keyence"であった場合に注意。

string S;
string T = "keyence";
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
 
    if (S == T) {
        printf("YES\n");
        return;
    }
 
    rep(a, 0, N) rep(b, a, N) {
        string s = "";
        if (a) s += S.substr(0, a);
        if (b + 1 < N) s += S.substr(b + 1);
        if (s == T) {
            printf("YES\n");
            return;
        }
    }
 
    printf("NO\n");
}

Beginning [KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 A]

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_a

解説

https://atcoder.jp/contests/keyence2019/submissions/3998411

並び替えて1974が作れる数字の列はソートしたときに1479となる数列である。
なので、ソートして見ていけばいい。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 4) cin >> A[i];
    sort(A, A + 4);
    if (A[0] == 1 and A[1] == 4 and A[2] == 7 and A[3] == 9) printf("YES\n");
    else printf("NO\n");
}