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

noyのブログ

プログラミングとかゲームとか

やるだけ問題について メモ

競技プログラミング メモ

やるだけ問題で特に気を付けること

別にやるだけ問題に限ったことではないけれど。

細かく関数化する

できるだけ処理を分けて考えること。見やすいし、後になって直しやすい。main関数だけに書かれたコードを直すのは精神的にとてもつらい。
やるだけ問題をバグらせると直すのが大変なので、できるだけバグを起こさない&直しやすいコードを書く。

変数名を考える

変数名を一文字や意味の薄い単語ではなく、ある程度意味のある単語にする。
関数が細かくなっていればそこまで気にする必要はないが、それでもやっかいな処理でバグらせないために少しは気を付ける。

引数が多いなら、構造体等でまとめる

まとめられる部分はまとめる。上記の変数名を考える、ということに近いのかもしれない。

まとめ

とにかく関数化。二度とつかわないであろう関数だけど、分けることでとても見やすくなる。

C++ 素数を求める2種類の方法

競技プログラミング アルゴリズム
素数を求める方法

ひとつ目は愚直な割り算の繰り返し。ふたつ目はエラトステネスのふるい。

割り算を繰り返せば、どんな素数でも求められる。しかし、多くの数を素数か判定するのには遅すぎる。
エラトステネスさえ覚えれば、多くの素数問題は攻略できる。しかし、悲しいことに大きな素数を求めることはできない。

そこで、2種類の方法を使い分ける必要がある。

愚直に求めるサンプルプログラム
bool primeNumber(int n){
    if(n < 2) return false;
    else{
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}

与えられた値が素数かを判定する。
n - 1までの値で割り続け、割り切れなければ素数である。√nより大きな自然数ではnを割り切ることはできないので、その部分は処理する必要がない。
なので、ループの範囲は i * i <= n と書ける。

1つの値が素数かどうかを判定するこのプログラムの計算量は0(√n)である。
もしもn以下のすべての素数を求めるのであれば、計算量はO(n√n)である。

制約が 1 <= n <= 10^6 だった場合、n以下の素数を全て求めようとするとO(10^6 * 10^3)。TLEする。

エラトステネスのふるい
const int N /*値*/;
void eratosthenes(bool prime[N]){
    rep(i,N) prime[i] = 1;
    prime[0] = prime[1] = 0;
    rep(i,N){
        if(prime[i]){
            for(int j = i + i; j < N; j+=i){
                prime[j] = 0;
            }
        }
    }
}

引数として渡したbool型配列に、素数の情報を詰め込んでくれる。prime[素数] == true。素数ではないとき、値はfalseである。
n以下の素数をすべて求めてくれる。

よくループカウンタを間違える。

計算量はO(n log log n) になる。

どちらを使うのか

10^6までの素数を求めたい→エラトステネス
制約に10^7、10^8とか書いてある→愚直

エラトステネスでは求められないなら、愚直で。
制約の10^8を見て、「エラトステネスじゃ求められない……。他のアルゴリズムあったっけ?」と考える必要はない。(2回もやってる)

ABC021 C 正直者の高橋君

競技プログラミング

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder

状態

AC
AC
AC
WA
AC
.
.
.
AC

_人人人人人人人人人人_
> なぜかACできない <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y ̄

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define itrep(it, a) for(it = (a).begin(); it != (a).end(); it++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;
 
const int kn = 105;
int atlas[kn][kn];
 
int warshallFloyd(int n, int start, int goal){
    rep(k,n){
        rep(i,n){
            rep(j,n){
                atlas[i][j] = min(atlas[i][j], atlas[i][k] + atlas[k][j]);
            }
        }
    }
    return atlas[start][goal];
}
 
long long numberOfDirections(int n, int shortestPath, int start, int goal){
    long long path, retval = 1;
    range(i,1,shortestPath){
        path = 0;
        rep(j,n){
            if(atlas[start][j] == i && atlas[j][goal] == shortestPath - i) path++;
        }
        retval = (retval * path) % 100000007;
    }
    return retval;
} 
 
int main(){
    int n, m, a, b;
    cin >> n >> a >> b >> m;
    //0からに合わせる
    a--; b--;
    rep(i,kn) rep(j,kn) atlas[i][j] = INF;
    rep(i,m){
        int x, y;
        cin >> x >> y;
        x--; y--;
        atlas[x][y] = atlas[y][x] = 1;
    }
    cout << numberOfDirections(n, warshallFloyd(n, a, b), a, b) << endl;
}

トポロジカルソートやメモ化再帰でもないなにか。

出発地点aから目的地bまでの距離を求める。
その後、aからbまでの通る道を数えて積を求めている。

点Aから点Bまでは2通りの道。点Bから点Cまでは5通りの道。
点Aから点Cまでの行き方は、2 * 5の10通り。
こんな計算を意識して書いた。

結果はコーナーケースに阻まれWA。
INFやretvalの計算を見直すも変わらず。

なぜだかわからないまま今日は断念。

今になって思えば、ワ―シャルフロイドじゃなくてダイクストラでも何の問題もなかった。

ABC026 C 高橋君の給料

競技プログラミング

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder


解説に書いてある解法、再帰で解いた。
ただ、なんとなく通してしまったのであまり考えていない。
そこで、ちょっとは頭を使ってみる。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define itrep(it, a) for(it = (a).begin(); it != (a).end(); it++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;
 
int n, inp[30];
 
int solve(int d){
    int high = 0, low = INF;
    rep(i,n){
        if(inp[i] == d){
            int down = solve(i + 1);
            high = max(down, high);
            low = min(down, low);
        }
    }
    if(high == 0 && low == INF) return 1;
    else return high + low + 1;
}
 
int main(){
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> inp[i];
    }
    cout << solve(1) << endl;
}

solve関数で、社員番号dの給料を計算している。

社員番号dの給料は、部下の給料から求められる。inp[i] == d のとき、社員番号iはdの部下である。
社員番号iの給料も上記と同じように求められるので、再帰を使うことができる。
再帰で求めたい社員の部下の給料を求めていく。部下がいない社員は給料が1。なので、それだけを分岐させる。

社員番号が高い社員から順番に給料がわかる。


今回はすんなり解けた感じがあるけれど、そのすんなりは偶然だったような。