noyのブログ

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

sshでリモートマシンへログインする際にやったこと

ログインするだけなのに時間がかかった。
mac -> VMware CentOS7

yum install openssh-server
  • sshdサービスの起動
systemctl start sshd-service

ここでエラーが出て実行できなかった。SELinuxが原因な気がしたので、

setenforce permissive

で設定を変更した。
すると実行できた。

systemctl status sshd.service

で起動できているかを確認した。

その後sshで通信しようとするも、TLE。

firewall-cmd --list-all

これでファイアウォールsshを見逃してくれているかを確認。sshがservicesにあれば大丈夫っぽい。しかしログインできず。

自分はsshのポート番号を変更していたので、それもファイアウォールに示した。

firewall-cmd --permanent --add-port=<ポート番号>/tcp

その後、ログインできた。

とりあえずログインはできたので、次はセキュリティについて試す。

グラフ メモ

  • 連結

任意の2点間に辺がある。
連結グラフは、グラフ上の任意の2点間に辺があるグラフのこと。

  • 関節点

削除すると部分グラフが非連結になる点。

削除すると部分グラフが非連結になる辺。

  • 強連結

任意の2点間に有向路がある、という条件を満たしている有向グラフの頂点の部分集合を強連結であるという。

  • 強連結成分

強連結な集合Sに、どのような頂点集合を付け足しても強連結にならないとき、Sを強連結成分という。

典型探索問題を解く

問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。

パラメータそれぞれに注目して解けるか考える。
DPなら、テーブルに何を持つかを全通り考えてみる。

AOJ ALDS1_4-D Search - Allocation

問題概要

数字がn個与えられる。それをk個のグループに分ける。
グループの数字の総和の最大値が最小となるように分ける。

なんか二分探索っぽいキーワードが。

制約

1 ≤ n ≤ 100,000
1 ≤ k ≤ 100,000
1 ≤ w_i ≤ 10,000

考え方
  • nに注目

i番目までの荷物をいれたときの最大値を求めていく、と考えて無理そうなので諦める。
これだと、どの数字をどのグループに入れたかも保持しないとできない。その上遷移もできなさそう。

  • kに注目

グループの数変えても仕方ない。

  • 総和の最大値に注目

総和の最大値がi以下のとき、グループにできる数字の個数、と考える。
iが大きければ、貪欲にグループを作れば良い。
→総和の最大値を全通り試してグループができるか調べればよい。
 →二分探索でいけそう。
  →できた。

Binary Indexed Tree(BIT)を学ぶ(1)

BITとはなんぞや

参考:蟻本159頁

列a_1, a_2, ... , a_nがある。

  • iが与えられたとき、a_1からa_iまでの和を求める。
  • (iとjが与えられたとき、a_iからa_jまでの和を求める。)
  • iとxが与えられたとき、 a_i += x する。


要はある区間の和をO(log n)で求めることができるデータ構造。

POJ1990 MooFest

問題概要は省略。

解法

i番目の牛とj番目の牛の座標の差 * max(i番目の牛の聴力, j番目の牛の聴力)
全てのi、jの組み合わせについて上記の式を計算し、総和を求める。

・愚直解
二重ループで全てのi, jの組み合わせを計算する。O(n^2)。
n <= 20000 なのでTLE。

・BITを使った解法

  1. 聴力の値で入力をソートする。これでどちらの聴力が大きいかを考える必要がなくなる。
  2. i番目の牛に注目し、座標の差の合計を求める。
  3. ans += 聴力 * 座標の差の合計
  4. BITに値を加算する
  5. i++、 2に戻る。

聴力を降順にし順番に処理することで、maxを考えなくてよくなる。

聴力の合計は、以下のようにして求めている。
距離の差の総和 = 区間0~x−1にいる牛の数 * x - 区間0~x−1にいる牛の座標の総和 + 区間x~MAX_Xにいる牛の座標の総和 - 区間x~MAX_Xにいる牛の数 * x

コード

先駆者様のコードをほぼ写経。

<省略>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 100000000;
using namespace std;

const int MAX_N = 20010;
const int MAX_X = 20010;

pair<int, int> pr[MAX_N];
int N;
long long dists[MAX_X], cnts[MAX_X]; //BIT

long long sum(int i, long long bit[MAX_X]){
    int s = 0;
    while(i > 0){
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

long long sum(int first, int last, long long bit[MAX_X]){ //first-last間の和
    return sum(last, bit) - sum(first, bit);
}

void add(int i, int x, long long bit[MAX_X]){
    while(i <= MAX_X){
        bit[i] += x;
        i += i & -i;
    }
}


long long solve(){
    sort(pr, pr+ N); //1. 聴力の値でソート
    long long ans = 0;
    rep(i,N){
        int v = pr[i].first, x = pr[i].second;
        long long c1 = sum(0, x - 1, cnts), c2 = sum(x,MAX_X - 1, cnts);

        //2. 座標の差の総和を求める 3. ans += 聴力 * 座標の差の合計
        ans += v * ( (c1 * x - sum(0, x - 1, dists)) + (sum(x, MAX_X - 1, dists) - c2 * x) );
 
        //4. BITに値を加算する
        add(x, 1, cnts); 
        add(x, x, dists);
    }
    return ans;
}

int main(){
    cin >> N;
    rep(i,N){
        int x, v;
        cin >> v >> x;
        pr[i] = make_pair(v, x);
    }
    printf("%lld\n", solve());
    return 0;
}

long long sum(int i, long long bit[MAX_X]){
long long sum(int first, int last, long long bit[MAX_X]){
void add(int i, int x, long long bit[MAX_X]){
上記の関数はBITの実装です。

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

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

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

細かく関数化する

できるだけ処理を分けて考えること。見やすいし、後になって直しやすい。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の計算を見直すも変わらず。

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

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