sshでリモートマシンへログインする際にやったこと
ログインするだけなのに時間がかかった。
mac -> VMware CentOS7
- opensshのインストール
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
その後、ログインできた。
とりあえずログインはできたので、次はセキュリティについて試す。
典型探索問題を解く
問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。
パラメータそれぞれに注目して解けるか考える。
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が大きければ、貪欲にグループを作れば良い。
→総和の最大値を全通り試してグループができるか調べればよい。
→二分探索でいけそう。
→できた。
POJ1990 MooFest
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を使った解法
- 聴力の値で入力をソートする。これでどちらの聴力が大きいかを考える必要がなくなる。
- i番目の牛に注目し、座標の差の合計を求める。
- ans += 聴力 * 座標の差の合計
- BITに値を加算する
- 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の実装です。
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) になる。