らんこむの数学部屋

数学とプログラミングの勉強をしていきます

ライブラリを自作して良かったところ

こんにちは、前回の投稿からだいぶ日が空いてしまいました。

 

続けて競プロ典型90問は解いているのですが、1つずつ記事に起こしても

あまり中身のない記事になってしまいそうだったのでやめていました。

ただ、解いているうちに面白いと感じたこともあったので

そのうちまとめて上げたいですね。

 

さて、昨日はABC289でした。

atcoder.jp

 

1WA5ACでパフォーマンスは1452となかなか好調、

1WAの内容が改行入れ忘れというミスだったので悔しいところです。

 

典型問題を解いていて「これ別の問題でも使うよな」といった部分をまとめていました。BFSだったり、dijkstra法、mod計算等です。

今回はそれらが非常に役立った。というお話です。

 

当然、この有名どころなプログラム達はググれば沢山出てきますし、

コピペですぐに使えるプログラムも転がっています。

ただ、自分で書いたプログラムというのはやはり自分にとって使いやすいもので、

変数の命名方法、コメントの入れ方、プログラムの書き方などが

自分の癖にあっているので、少し個々の問題用に手を加える。といったことが非常にやりやすかったです。

 

今回、私はD問題をdijkstra法で、E問題をBFSで解いたのですが、

D問題であれば、辺をあらかじめ指定するのではなく、都度構成するのに手を加え、

E問題であれば、到達済みの点を高橋君と青木君の組み合わせで保持するのに手を加えました。

 

恐らく、他の人の書いたプログラムであればソースコードを読むのに数分かかり、

その後に改修することになるのですが、自分の書いたプログラムであればソースコードを読むのに時間はかかりませんでした。ほとんど最初から改修に取り掛かり、スムーズに問題に取り組むことができました。

 

ただ、他人の書いたプログラムを読む能力を身に着けることも重要ですし、

自分で書いたものよりも、他人が書いたものの方が高速に動作する。ということも

よくある話なので、インプットを忘れずにやっていきたいところです。

文字列のソートはどれだけかかる?

こんばんは、らんこむです。

先週末はABC287とARC155に参加していました。

ABC287はそれなりに解けたんですが、ARC155に関しては1問も解けず・・・

2時間問題とにらめっこしているのは中々辛かったですね。

さて、ABC287のE問題では公式解説とは別解としてソートをして解いている人が多かった印象です。

C問題のテストケースが少なかったことで話題になっていましたが、E問題もそれなりに盛り上がっていましたね。

さて、本題のE問題です。

atcoder.jp

与えられた文字列を辞書順にソートすると、LCPの計算は前後の確認だけで済むようになるので、

時間は「ソートの時間」+「前後比較の時間」です。

「前後比較の時間」については総文字数の 5 × 105 で抑えられます。

問題となるのはソートの時間です。

一般的に長さ N の配列のソートは  O(N \log N) の計算量になります。

ただし、これは  O(N \log N) の "比較回数" です。長さ L の文字列の比較には最大で L回の文字比較が必要です。

実際には発生しませんが、簡単に考えられる最悪の状態としては長さ 2.5 × 105 の二つの文字列に対して  O(N \log N) の比較を行うことです。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {

    // 文字列長
    const int L = 250000;
    // 試行回数
    const long long N = 10000000;

    string S(L, 'a');
    string T(L, 'a');
    T[L - 1] = 'b';

    bool ans;
    time_t start = time(nullptr);

    for (long long i = 0; i < N; ++i) {
        ans = (S < T);
    }

    time_t end = time(nullptr);

    cout << difftime(end, start);

    return 0;

}

上記のコードで簡単に比較してみると1分程度かかりました。

まだまだ調べなければ分からないことは多いですが、1/60 程度に時間が抑えられれば良いので 嘘解法というわけではないような気がします。

また何か思いついたら続報を書こうと思いますが、今日はこのあたりで。

競プロ典型90問 [2問目]

こんばんは。競プロ典型90問、2問目やっていきます。

002 - Encyclopedia of Parentheses(★3)

問題文で「正しいカッコ列」なるものが定義されていますが、 普段使用しているカッコ列と変わりありません。

この定義に正直に沿って解いてしまうと、文字列結合で遅くなってしまったり、 重複していないか、など考えることが多くなってしまいます。

そこで、正しいカッコ列というものを

  • 左n文字の部分文字列では「 ( 」の数が「 ) 」の数と同じかそれよりも多い
  • 全体文字列では「 ( 」の数と「 ) 」の数が一致している

と考えました。

左から文字列を形成していき、一つ目の条件を満たさなくなった場合には文字列の形成を中断してしまえば、 生成されるカッコ列に対して線形オーダーで生成することができました。 emplace_string関数では、文字列に対してまだ閉じていないカッコの数を記録しておくことで一つ目の条件を判断しています。

#include <iostream>
#include <string>

using namespace std;

void emplace_string(string S, int N, int cnt) {
    
    if (S.size() == N) {
        if (cnt == 0) {
            cout << S << endl;
        }
        return;
    }
    
    if (cnt == 0) {
        emplace_string(S + "(", N, cnt + 1);
    }
    else {
        emplace_string(S + "(", N, cnt + 1);
        emplace_string(S + ")", N, cnt - 1);
    }

}

int main() {

    int N;
    cin >> N;

    if (N % 2 != 0) {
        // 奇数なら存在しない
        return 0;
    }

    // 偶数の場合
    string S = "";
    emplace_string(S, N, 0);

    return 0;

}

結構綺麗にまとまったと思ったのですが、実行時間はあまり早くはなかったです。

アルゴリズム的にはこれ以上早くなる余地はないかと思うのですが、プログラムの書き方次第でもそれなりに変動するようです。

もっとプログラムとお友達にならないといけませんね。

競プロ典型90問 [1問目]

こんばんは。 数学部屋と言っておいて、競プロばかりやっている気もしますが、 広義の数学ということでお許しください。

毎週末にAtCorderのコンテストに参加してはいるのですが、 新参者の私は知識がなく、毎回一から考えている状態です。 これはこれで面白いのですが、「競技」とついているのですから やはり高順位を目指していきたいものです。

ということで競プロ典型90問を解いていきたいと思います。

atcoder.jp

できれば1日1個のペースで進めていけるといいですね。 あくまで自分の解法を書いていくので、本当に解説を求めている方は公式の解説を参照してくださいね。

さて、前置きはこのぐらいにして1問目です。

001 - Yokan Party(★4)

考えられる解法としては

  1. 切れ目を決めて、何cmのピースが存在するか確認する。
  2. 目標のスコアを決めて、その長さを満たしつつ K個の切れ目が入れられるか確認する。

ですかね。

  1. のパターンで行くと、切れ目を決め方が _n C_k個、 その切り方から最小ピースを探すのには O(K)となります。 切れ目の決め方だけでも最大で _{100000} C_{50000} \risingdotseq 10^{30000}ほどになってしまいます。

  2. のパターンでは、目標のスコアを決めるのに109通り、 その長さを満たしつつ K個の切れ目が入れられるかは O(K)となります。 まだこのままではTLEしてしまう計算量です。

目標のスコアを決めるのに109通りではありますが、最大を求めればよいので 上手く最大値を求めていけばよいです。 この上手く見つけるための手法が二分法と呼ばれるものです。

自分は以下のソースコードで通しました。

#include <iostream>
#include <vector>

using namespace std;

bool can_split(int length, int num, vector<int>& piece) {

    int n = 0;
    int len = 0;
    for (int i = 0; i < piece.size(); ++i) {
        len += piece[i];
        if (len >= length) {
            ++n;
            len = 0;
            if (n == num) {
                for (int j = i + 1; j < piece.size(); ++j) {
                    len += piece[j];
                }
                if (len >= length) {
                    return true;
                }
                else {
                    return false;
                }
            }
        }
    }

    return false;

}

int main() {

    int K, N, L;
    cin >> N >> L;
    cin >> K;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // 各ピースの長さ
    vector<int> piece(N + 1);
    piece[0] = A[0];
    for (int i = 1; i < N; ++i) {
        piece[i] = A[i] - A[i - 1];
    }
    piece[N] = L - A[N - 1];

    int length = L / (2 * K);
    int max = L / K + 1;
    int min = 1;
    while (true) {
        if (can_split(length, K, piece)) {
            min = length;
            length = (max + min + 1) / 2;
        }
        else {
            max = length - 1;
            length = (max + min) / 2;
        }
        if (max == min) {
            cout << min;
            return 0;
        }
    }

    return 0;

}

今見ると、変数名に min, max とかの予約語が使われていて悪いコードですね。 あと、今回は L < 109 なので問題になりませんが max + min がオーバーフローする可能性のある時は、 length = min + (max - min)/2 とするのが正しいですね。

二分法自体の原理自体は難しくないのですが、整数での二分法はオーバーフローや、最小、最大の決め方を気を付けないと 無限ループに陥ることもあるので注意したいところです。

今日はここまで。2問目も既に解いてしまったのですが、また後日書こうと思います。

ランダムってなんだろう?

こんばんは。らんこむです。

 

最近、疑似乱数の生成方法を勉強してます。

疑似乱数がいい感じの乱数であることの定義として、

いくつかの条件があるわけなんですが、そこで一つ思ったことがあります。

 

真の乱数ってなんだろう?

 

定義はほとんどの人が一致するのではないでしょうか。

・全ての数が等しい確率で出る

・前後の出力は確率に一切関係しない

(一様乱数が欲しい場合)

ただし、乱数生成法を決めたとしてどのように上記の性質を満たしていることを確認するのでしょうか?

証明する場合には「このような結果になることが予想できる(導かれる)から、主張が成立する」といった形になります。

しかし、予想できてしまっては真の乱数とはなり得ないのですから、別のアプローチが必要となります。

物理現象を用いて生成する場合には「(今の人類の知識・技術では)予想できない」ことは十分に保障されますが、予想できないのであれば全ての数が等しい確率で出ることは保証できません。

 

少し調べてみると、量子理論を元にして真の乱数を生成する。といったものが出てきました。確かに量子理論は少しは聞いたことはありますが・・・

・予測不可能

・0 か 1 を 50% の確率で出力する

そんなことが可能なのでしょうか。確率だけ分かっているのに、予測できないとは。

前半で私が考えていたことが覆されてしまいました。

全く納得できないのですが、あまりに専門的な内容に踏み込んでしまうため自分には理解することは難しそうです。。

ARC153の感想

こんにちは。らんこむです。

AtCoder Regular Contest 153 に参加したので、 今日は自分が回答できたA問題とB問題について話そうと思います。

まずはざっくりと問題文から。

A - AABCDDEFE

問題文

正整数x美しい整数であるとは, xが9桁の整数であり,
その10進法表記S_1 ... S_9 (S_ixの10進法表記のi文字目)が 以下の条件をすべて満たすことを言います

  • S_1は0ではない
  • S_1 = S_2
  • S_5 = S_6
  • S_7 = S_9

正の整数Nが与えられます. 小さい方から数えてN番目の美しい整数を答えてください.

B - Grid Rotations

問題文

H行, 横W列のグリッドがあります. はじめ, 上からi行目, 左からj列目のマスには英小文字A_{i,j}が書かれています.
このグリッドに対してQ回の操作を行います. i回目の操作では, 1 \leq a_i \leq H-1, 1 \leq b_i \leq W-1を満たす整数a_i, b_iが与えられ, 次を行います.

  • グリッド内の長方形領域R_1,R_2,R_3,R_4を次で定める:
    • 上からa_i行, 左からb_i列の部分をR_1とする.
    • 上からa_i行, 右からW-b_i列の部分をR_2とする.
    • 下からH-a_i行, 左からb_i列の部分をR_3とする.
    • 下からH-a_i行, 右からW-b_i列の部分をR_4とする.

Q回すべての操作を行ったとき, 操作後のグリッドの状態を出力してください.

回答と私の感想

A問題

A問題については、特に悩むこともなく力づくで解いていきました。
Nが106程度で抑えられることは分かるので、一つずつ美しい整数を求めていっても通ります。 ただ、6重ループになってどうも回答が美しくない・・・と思って解説を見ると、なんと定数時間で求まると。 最初に6桁のまま足し算をして9桁に編集しなおせばいいようです。美しい。

解説はPython実装だったので、自分の使用言語である C++ で書いてみました。

#include <iostream>
#include <string>

using namespace std;

int main() {

    int N;
    string S;
    cin >> N;
    
    N += 100000 - 1;
    S = to_string(N);

    cout << S[0] << S[0] << S[1] << S[2] << S[3] << S[3] << S[4] << S[5] << S[4];

    return 0;

}

それなりにまとまったのではないでしょうか。ただ、実行時間は1ms長くなりました・・・
文字列変換に時間がかかるのでしょうか。まあ、1msなら全然許容範囲なのでありです。

B問題

こちらは想像以上に苦戦してしまいました。 出力例2を見てみると、1行目の「atcorder」が2行目に移動していることに気が付きました。
しかし、同じ文字が多いため法則性までは分からず 1~9, a~k を使って試してみると、
行の入れ替えのみならず、順序も正順、逆順が入れ替わることを除けば綺麗に並んだままになっています。
法則に気が付いたときは気持ちがいいですね。すぐに実装しましたが、計算式をなんとなくで書いてしまったため、2回WAを出してしまいました。
以下は最終的なコードです。

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int H, W, Q;
    vector<vector<char>> A;

    cin >> H >> W;
    A = vector<vector<char>>(H, vector<char>(W, 0));

    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            cin >> A[h][w];
        }
    }

    cin >> Q;

    // A[0][0]の位置
    int h0 = 0, w0 = 0;

    for (int q = 0; q < Q; ++q) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        if (h0 <= a) {
            h0 = a - h0;
        }
        else {
            h0 = (H + a) - h0;
        }
        if (w0 <= b) {
            w0 = b - w0;
        }
        else {
            w0 = (W + b) - w0;
        }
    }

    if (Q % 2==0) {
        // 偶数回
        for (int h = 0; h < H; ++h) {
            for (int w = 0; w < W; ++w) {
                int a = (h - h0 + H) % H;
                int b = (w - w0 + W) % W;
                cout << A[a][b];
            }
            cout << endl;
        }
    }
    else {
        // 奇数回
        for (int h = 0; h < H; ++h) {
            for (int w = 0; w < W; ++w) {
                int a = (h0 - h + H) % H;
                int b = (w0 - w + W) % W;
                cout << A[a][b];
            }
            cout << endl;
        }
    }

    return 0;

}

A[0][0]の移動先を h0,w0 として計算をしていきます。 h0 \leq aの時、(h0,w0) は左側で180度回転するので、
移動先の位置をh0'としてh0' と 0 の距離 = h0 と a の距離なので、 h0' = a - h0 です。
a \lt h0の時、(h0,w0) は右側で180度回転するので、
H - h0' = h0 - a で、これを解けば h0' = H - h0 + aです。
自分は右側回転の数式を直感で書いてしまい、2回間違えました・・・

さて、B問題の解説中にある

長さNの1次元配列について, 通常の隣接関係に加えて左端と右端も「隣接している」と考えることにする. このとき, 捜査前に隣接していた2項は操作後にも隣接している.

これは成程となりましたが、ここから正順、逆順をシフトしたものであることをどう示していくか?
という部分がまだ思いついていません。自分の頭で納得出来たらこれも書いてみようと思います。 C~F問題についても、ヒントや解説見ながらおいおい解いていければと思います。

初ブログ投稿

初めまして。らんこむです。

SESとして働いていて大した技術力も磨けないまま数年経過してしまったのですが、

流石にこのままではいけないので、色々勉強していこうと思っています。

 

このブログではその勉強の内容について書いていこうと思います。

メインは

・数学の話

・プログラミングの話

数学は大学生での専門分野だったのですが、ふと参考書を見てみたときに

想像以上に忘れてしまっていたので、少しでも知識を長生きさせられたら・・・

と思っています。

プログラミングはストレートに仕事に活かしたいという気持ちです。

今の仕事は楽しいのですが、仕事内容が大した難易度じゃないので

もう少し技術を磨いて新しい場所に移らせてもらえないかと思っています。

 

一人で勉強してるとサボりがちになってしまうので、こういったブログを書いて意欲を出そうという算段です。

 

他にも何かシェアしたい出来事などがあれば書いていく予定です。