6月の学んだこと日記 6/21始動
6月21日
土曜日
応用情報
フォールトレランス・・・故障が発生してもシステム全体として必要な機能を維持させようとする考え方。
フォールアボイダンス・・・故障そのものの発生を防ぐことで、システム全体の信頼性を向上させようとする考え方。
フォールトレランスの実現方法
・フェールソフト
システム全体を停止させずに必要な機能を維持させる
・フェールセーフ
障害の影響範囲を最小限にとどめる
・フェールオーバー
障害が発生したとき処理やデータをほかのシステムに引き継ぎ、切り替え処理を利用者に意識させない。
・フォールトマスキング
障害が発生しても、その影響が外部に出ないようにする。
・フールプルーフ
誤った操作や意図しない使われ方でも、システムに異常が起こらないようにせっけいする。
クラスタシステム
ネットワークに接続した複数のコンピュータを連携し、１つのこんぴゅータシステムとして利用できるようにしたシステム。代表的なのがHAクラスタ
HAクラスタには次の２つの構成がある
・フェールオーバクラスタ構成
アクティブ/スタンバイ方式のクラスタ構成。
・負荷分散クラスタ構成
アクティブ/アクティブ方式。特定のこんぴゅータに処理が集中しないように複数のコンピュータに処理を振り分ける
・シェアードエブリシング
複数のサーバが一つのストレージを共有する。
・シェアードナッシング
サーバごとに１つのストレージを割り当てる。
日常
「足るを知る」は、「身分相応に満足することを知る」という意味であり、
｢足りていることを知り、何事にもありがたみをもつ｣ということです。
自分は平凡で退屈であんまり面白みのない人生だなと感じることがある。早くお金持ちになってこんな平凡な日々から抜け出してやると時々考えている。だが「足るを知る」という言葉あるように自分の今の暮らしに満足することが大事だ。夢を追いかけながら少し退屈に感じる日常を自分なりに楽しむことにする。
6/22 00:34
６月２２日 日曜日
応用情報
RAID 複数の記憶装置をまとめて１つの論理的な装置（ディスクアレイ）として扱い、入出力の高速化や信頼性の向上を実現させる技術。
RAID0・・・データを複数のディスクに分散して配置（ストライピング）
RIDO１・・・複数のディスク装置に同じデータを書き込む方式。ミラーリング
RAID2・・・RAID0に、メインメモリなどで使用させるハミング符号用の複数のディスク装置を追加した方式
RAID3,4・・・RAID0に、パリティと呼ばれるエラー訂正情報を保管するパリティディスクを追加し、いずれかの１台の装置に障害が発生した場合、正常なディスク装置間で復元する方式//あんまりイメージがわかない
RAID３はビット単位 ４はブロック単位
RAID５・・・RAIS４を改良し、データとパリティを分散させることで、パリティディスクへのアクセスの集中を防ぎ。高速化を実現
6月２３日 月曜日 atcoder ・尺取り法 使える条件 長さnの数列a1,a2,a3・・・anにおいて 条件を満たす区間のうち最小の長さを求めよ // 最大の長さ // 数え上げ
例題 長さnの正の整数列a1,a2,a3・・・an と整数xが与えられる。整数列の連続する部分列で、その総和がx以下となるものを数え上げよ (実際の出題は
q個のクエリがあって各クエリごとにxが与えられる)。
例として
n=12
x=25
a={.........}
#include <iostream>
#include <vector>
using namespace std;
int main() {
/* 入力受け取り */
int n, Q;
cin >> n >> Q;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
/* Q 回分のクエリを処理 */
for (int j = 0; j < Q; ++j) {
long long x; cin >> x; // 各クエリ x
/* 合計値 */
long long res = 0;
/* 区間の左端 left で場合分け */
int right = 0; // 毎回 right を使い回すようにする
long long sum = 0; // sum も使い回す
for (int left = 0; left < n; ++left) {
/* sum に a[right] を加えても大丈夫なら right を動かす */
while (right < n && sum + a[right] <= x) {
sum += a[right];
++right;
}
/* break した状態で right は条件を満たす最大 */
res += (right - left);
/* left をインクリメントする準備 */
if (right == left) ++right; // right が left に重なったら right も動かす
else sum -= a[left]; // left のみがインクリメントされるので sum から a[left] を引く
}
cout << res << endl;
}
}
｝
尺取り法はもっと問題を解いたほうがいいな
応用情報
ストレージの接続形態
ストレージの主な接続形態には、DAS、NAS,SANの３種類があります
NAS(Network Attached Storage)・・・LANに直接接続する形式のストレージ。NFSやCIFSなどのファイル共有プロトコルにも対応しているため異なるOSコンピュータ間でもファイルを共有することができる。
SAN(Storange Area Network)・・・サーバとストレージを通常とは別の高速ネットワークで接続した、ストレージ専用ネットワーク
従来のSANの構築にはギガビット級の転送能力をもつファイバチャネル（FC）が多く用いられた。これをFC-SANという。現在では、TCP/IPネットワーク上で送受信するiSCSIを用いたIP-SANもある。
応用情報は全然勉強できてないな,,,
授業（工科系数学）
オイラーグラフ・・・すべて偶数点（一筆書きが可能）
すべての辺を１つずつ通り、始点と終点が同じ
周遊可能小道・・・奇数点が２つ、それ以外が偶数点（一筆書きが可能）
すべての辺を１つずつ通り、始点と終点が異なっていてもよい
6/24 01:03
6月24日
応用情報
ストレージ仮想化技術
ストレージ仮想化とは、複数のストレージデバイスを論理的に結合して、それを１つのストレージとして扱う技術
・シンプロビジョニング
ストレージ資源を仮想化して割り当てることでストレージ物理容量を削減する技術
・ストレージ自動階層化
異なる性能のストレージを複数組み合わせて階層を作り、利用目的や利用頻度といったデータ特性に応じて、格納するストレージを変えるという考え方をストレージ階層化という。
手動でやるのは手間がかかるので階層化の制御を自動化したのがストレージ自動階層化
サーバ仮想化
サーバ仮想化は１台の物理サーバで複数の仮想的なサーバを動作させるための技術です。
・ホスト型仮想化
ホストOSの上に仮想ソフトウェアをインストールし、その上で仮想サーバを稼働させる方式です。
エミュレート・・・別のソフトウェアやハードウェアによって模倣して、代替えとして動作させる仕組み。
・ハイパバイザ型仮想化
仮想サーバ環境を実現するための制御プログラム（ハイパバイザという）をハードウェアの上で直接動かし、そのうえで仮想サーバを稼働させる方式です。
・コンテナ型仮想化
ホストＯＳ情に論理的な区画（コンテナ）を作り、サーバアプリケーションの実行環境を提供する方式です。コンテナにはアプリケーションの動作に必要なライブラリなどがふくまれていて、独立したサーバと同様のふるまいをします。
その他のサーバ仮想化に関連する技術
・ライブマイグレーション
仮想サーバ上で稼働しているOSやアプリケーションを停止させずに、別の物理サーバへ移し処理を継続させる仕組み・
・クラスタソフトウェア
仮想サーバを冗長化したクラスタシステムの高可用性を実現するための仕組みであり、クラスタシステムを管理/制御するソフトウェア。
クラスタシステム・・・ネットワークに接続した複数のコンピュータを連携し、１つのこんぴゅータシステムとして利用できるようにしたシステム。代表的なのがHAクラスタ
HAクラスタには次の２つの構成がある
システムの性能特性と評価
・スループット・・・コンピュータが単位時間当たりに処理できる仕事量
・レスポンスタイム・・・トランザクション処理や会話型処理に用いられる性能指標。コンピュータシステムに対して処理要求をだしてから、最初の処理結果が返ってくるまでの時間。
・ターンアラウンドタイム・・・主にバッチ処理に用いられる性能指標。
ジョブを投入してから出終わるまでの時間
バッチ処理・・・大量のデータや複数の処理をまとめて一括で一定のタイミングで自動的に実行する処理。
トランザクション処理・・・一連の処理を一つの単位として扱い、すべての処理が成功した場合のみ結果を返す処理。
MIPS・・・1秒間に実行可能な命令数を百万単位であらわしたもの
FLOPS・・・１秒間に実行可能な浮動小数演算回数を表したもの。
命令ミックス・・・実行時間とプログラム中における出現頻度を表したもの。
+-------------------------+
| 命令ミックス |
+-------------------------+
| 算術命令：50%（10ns） |
| 論理命令：30%（20ns） |
| 分岐命令：20%（25ns） |
+-------------------------+
| 平均命令実行時間：16ns |
+-------------------------+
ベンチマーク
コンピュータの使用目的に適した、あるいは評価対象となる業務の典型的な処理形態をモデル化した標準プログラムを用いて実行時間などを計測し、その結果からコンピュータ性能の評価を行うこと。
・SPEC
プロセッサの性能を評価するベンチマークテストとして、米国の非営利団体であるシステム性能評価協会が定めたベンチマーク。
・TPC
オンライントランザクション処理システムの性能を評価するベンチマークテストとして、アメリカの非営利団体であるTPCが定めたベンチマーク。
・カーネルプログラム法
計算プログラムなど実行させ、得られたCPU処理速度とほかのコンピュータにおける結果と比較評価する。
・カタログ性能
システムの各構成要素に関するカタログ性能データを収集し、それらのデータからシステム全体の性能を算出する。
・ソフトウェアモニタ
測定用のプログラムを用いて行われる。
・ハードウェアモニタ
測定対象となるCPUや主記憶装置などの資源を使用しないので、測定誤差の少ない厳密なそくていが可能
キャパシティプランニング
システムの新規開発や再構築において、ユーザの業務要件や業務処理量、サービスレベルなどから、システムに求められるリソースを見積り、経済性及び拡張性を踏まえたうえで最適なシステム構成を計画すること
キャパシティ管理
システムの負荷について現状分析と将来予測を行い、システムの安定稼働や性能維持のために、システム資源を適切に管理・調整する管理作業。
6/25 10:08
6月25日
atcoder
尺取り法
問題概要長さ N の正整数列 A=a1,a2,...,aN 整数 K が与えられる。連続部分列（区間）で、その和が K 以上となる区間の個数を求める。
区間の位置が異なれば同じ内容でも別カウント。
アルゴリズムの流れ
左端 l を0から順に動かす。
右端 r を伸ばしながら、区間和が K 以上になるまで進める。
区間和が K 以上になったら、その左端 l に対して右端以降の区間はすべて条件を満たすので N−r+1 個分カウントできる。
左端を1つ進める際、区間和から A[l] を引く。
全ての左端について繰り返す。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long K;
cin >> N >> K;
vector<long long> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
long long ans = 0;
long long sum = 0;
int right = 0;
for (int left = 0; left < N; left++) {
// 右端を条件を満たすまで伸ばす
while (right < N && sum < K) {
sum += A[right];
right++;
}
// 条件を満たさなければ終了
if (sum < K) break;
// 条件を満たす区間の個数を加算
ans += (N - right + 1);
// 左端を進めるので区間和から外す
sum -= A[left];
}
cout << ans << "\n";
return 0;
}
問題
ながさNの正の整数からなる数列a1,a2....anと正の整数ｓが与えられる
この数列の連続する部分列（区間）のうち、その総和が S 以上となるものの中で、最小の長さを求めよ。ないときは０を出力せよ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, S;
cin >> n >> S;
vector<int> a(n);
for(int i = 0; i < n; ++i) cin >> a[i];
int min_length = n + 1; // 最大でもnなのでn+1で初期化
int sum = 0, left = 0;
for(int right = 0; right < n; ++right) {
sum += a[right];
while(sum >= S) {
min_length = min(min_length, right - left + 1);
sum -= a[left];
++left;
}
}
if(min_length == n + 1) cout << 0 << endl;
else cout << min_length << endl;
return 0;
}
昨日今日はあまり勉強ができていない。明日はバイトがあるから夜はあまり勉強ができないと思うので、朝からしっかり勉強していきたい。atcoderでは累積和、二分探索、尺取り法を極めたい。
6/26 0:33
6月26日
atcoder
#https://atcoder.jp/contests/abc005/tasks
おいしいたこ焼きの焼き方
累積和問題
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<vector<int>> D(N, vector<int>(N));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cin >> D[i][j];
// 2次元累積和
vector<vector<int>> S(N+1, vector<int>(N+1, 0));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
S[i+1][j+1] = S[i+1][j] + S[i][j+1] - S[i][j] + D[i][j];
// 面積ごとの最大美味しさ
vector<int> val(N*N+1, 0);
for (int x1 = 0; x1 < N; ++x1) {
for (int x2 = x1+1; x2 <= N; ++x2) {
for (int y1 = 0; y1 < N; ++y1) {
for (int y2 = y1+1; y2 <= N; ++y2) {
int area = (x2 - x1) * (y2 - y1);
int sum = S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1];
val[area] = max(val[area], sum);
}
}
}
}
// 面積s以下の最大値に単調化
for (int s = 1; s <= N*N; ++s)
val[s] = max(val[s], val[s-1]);
int Q;
cin >> Q;
while (Q--) {
int P;
cin >> P;
cout << val[P] << endl;
}
return 0;
}
面積ごとのおいしいさの部分がイメージがつかない
図
ここの範囲を求める場合
. . . . .
. . . . .
. . x x .
. . x x .
. . . . .
以下の計算をまずする
x x x x . x x x x . x x . . .
x x x x . x x x x . x x . . .
x x x x . - . . . . . - x x . . .
x x x x . . . . . . x x . . .
. . . . . . . . . . . . . . .
左上の2*2のエリアが1回余分に引かれているので
x x . . .
x x . . .
. . . . .
. . . . .
. . . . .
を加えれば、答えになる。
事前に左上からの累積を計算すればO(1)で範囲が求められる！
応用情報
サーバの性能向上策
スケールアウト・・・既存のシステムにサーバを追加導入することによって、サーバ群として処理能力や可用性を向上させる。水平スケールともいう。
スケールアップ・・・サーバを構成する各装置により高性能なものに交換したり、あるいはプロセッサの数やメモリを増やすなどして、サーバ当たりの処理能力を向上させる。
システムの動的な拡張性
処理能力を必要に応じて動的に拡張するスケーラビリティを考慮した方策をとる。その1つが、サーバの負荷に応じて自動的にクラウドサーバ数を増減させるオートスケールの構築。
待ち行列理論の適用
トランザクションの到着
単位時間あたりに到着するトランザクション数を平均到着率という
あるトランザクションの到着から次の到着までの平均時間を平均到着間隔という。
サービス時間
単位時間あたりにサービス可能なトランザクション数を平均サービス率
１つのトランザクションがサービスを受ける平均時間を平均サービス時間
利用率
単位時間に窓口を利用してる割合。
例 5分ごとに客が到着し、１人の客に対して３分でサービスをする場合、
平均サービス時間＝３分/人
平均到着間隔＝５分
利用率＝３/5=0.6
待ち行列計算
サービスを受けている時間を含めたものを平均応答時間という
サービスを受けている時間を除いたものを平均待ち時間という
例 平均2件/秒の割合で発生するトランザクションを、1件当たり平均０．３秒で処理するシステムがある。トランザクションの発生及び処理がM/M/1待ち行列モデルに従うものとすると、システムの平均応答時間は何ミリ秒か。
利用率＝平均到着率/平均サービス率＝２÷（1/0.3)=0.6
平均応答時間＝(０．６/(１－０．６）)*0.3+0.3=0.75秒
6/27 15:30
６月２７日 6月28日
応用情報
システムの信頼性評価
コンピュータシステムがどのくらい稼働しているか、あるいは稼働するかを表す指標。
RASIS
信頼性を評価する５つの概念、信頼性、可用性、保守性、保全性、安全性頭文字をとった造語。
バスタブ曲線
ハードウェア機器に対する信頼性管理手法。
時間経過に対するハードウェア機器の故障率の推移を表したグラフ。
故障率曲線とも呼ばれる
ハードウェア機器のライフサイクルは、故障の面
初期故障期間、偶発故障期間、摩耗故障期間に分かれる。
システムの信頼性計算
稼働率
RASISの A:可用性の評価指標である稼働率はアベイラビリティと呼ばれ、システムの信頼性を評価する最も重要な尺度となる。
平均故障間隔（MTBF） 平均修理間隔（MTTR）
１５０時間 １．５時間
稼働率＝150/(150+1.5)=0.99
例 あるコンピュータシステムにおいて、周辺装置のMTBFは2000時間である。処理装置は、１時間に故障する確率が10-8のコンポーネント20万個から構成されている。このシステム全体のMTBFは何時間か。
周辺装置の故障率＝1/2000
処理装置の故障率＝10-8*20万=4/2000
1/2000+4/2000=1/400
複数システムの稼働率
直列接続の稼働率
直列接続では、両方の装置がともに正常であるときのみシステムが稼働するので、システム全体の稼働率はR1＊R2
並列接続
どちらかの装置が稼働していればシステムは稼働します。両方の装置が不稼働となったとき以外は稼働する
１－システムが稼働しない確率
稼働率＝１－（１ーR1）＊（１－R2）
不稼働率から見た稼働率
直列
（１－ｐ１）＊（１ーｐ２）
並列
１－ｐ１＊ｐ２
OSの構成と機能
基本ソフトウェアの構成
基本ソフトウェア（広義のOS）・・・制御プログラム、言語プロセッサ、サービスプログラムでできてる。
制御プログラム
カーネル、デバイスドライバ、ファイルシステムからなる。
カーネル
主記憶装置上に常駐する制御プログラムモジュール群で、スーパバイザプログラムとも呼ばれている。スケジューリング、資源の割振りなど、すべてのプログラムの実行を制御する機能をもち、OSの中核をなす部分といえる。
ジョブ管理
利用者からみた仕事の単位、つまりコンピュータで実行されるひとまとまりの処理をジョブという。ジョブ管理の役割は、ジョブやジョブを構成するジョブステップの実行を監視、制御すること。
JCL（Job control language)を介して、ジョブを連続的かつスムーズに処理させる機能や、低速の入出力処理とプログラムの実行を切り離し、効果的なコンピュータシステムの運用を可能にするスプーリング機能、さらには複数のジョブのスケジューリングを行う機能がある。
タスク管理と記憶管理
タスク管理の役割は、CPUの割り当て単位であるタスクを管理し、同時に実行される複数のタスクに、CPU効率を考慮した適切な順番でCPU時間を与えることです。
記憶管理の役割は、プログラムを実行するアドレス空間を管理、それを有効かつ用すること
デバイスドライバ
入出力装置を直接操作・管理するプログラム
カーネルモードとユーザモード
あるプログラムが誤ってOSを壊してしまうのを避けるため、CPUには２つの異なる実行モードがある。
ユーザプログラムの実行をゆるすユーザモード、もう１つはカーネルだけが実行できる、入出力命令などのようないくつかの特殊命令の実行を許すカーネルモードです。
必要最小限の機能だけカーネルにもたせ、その他の機能はサーバプロセスとして、必要な時に呼び出し利用するというマイクロカーネルアーキテクチャを採用したＯＳをマイクロカーネルＯＳという
これに対して、ＯＳが担うほとんどすべての機能をカーネルにもたせたＯＳをモノしりっくカーネルＯＳという。
タスク管理
タスクはCPUから見た、処理の単位です
タスクの制御方式
実行中のタスクCPU使用権を奪い、実行を一時に中断させる動作のことをプリエンプションという。プリエんぷしょん機能を用いた制御方式をプリエンプティブ方式という。プリエんぷしょん機能を用いない方式をノンプリエンプティブ方式。
タスクの情報保持
タスクに必要な情報は、TCB（タスク制御ブロック）と呼ばれる主記憶内のデータ構造に保持されます。TCBの実装は様々ですが、通常TCBには、タスクの識別子や優先度、現在の状態、ＣＰＵ使用時間、アドレス管理情報、そしてPSW(プログラム状態語）退避領域などが含まれる。
PSWは、タスクの再開をするために必要となる情報を保持する特殊なレジスタ。
コンテキスト切替え
１つのCPUで複数のタスクを実行するためには、CPUが保有する実行中のタスク情報（PSW）及びレジスタ群の内容、そして主記憶アドレス空間を交互に切り替えなければいけません。この切り替え操作をコンテキストスイッチング。
タスク切り替えのタイミング
イベントドリブン方式・・・ますがクリックされたなど環境に変化が生じた際に発生する割り込みによってタスクを切り替える。
タイムスライス方式・・・一定時間ごとにタスクを切り替える。各タスクに割り当てられる時間をタイムクウォンタイムという。
タスクのスケジューリング方式
到着順方式
FCFS（first come first served)方式とも呼ばれるスケジューリング方式
優先順位方式
各タスクに与えた優先度の高い順に実行する方式。タスク優先度をあらかじめ決めた値から変えない方式を静的優先順位方式。この方式では、優先度が固定化されるため優先度の低いタスクにはCPU使用権が与えられず、なかなか実行できないというスタンべーじょんが起こる可能性がある。
これを回避するために、待ち時間が一定時間以上となったタスクの優先度を動的にたかくして、実行できるようにした方式が動的優先度順方式。
優先度を高くして実行の可能性を与えることをエージングという。
ラウンドロビン方式
実行可能待ち行列の先頭のタスクから順にCPU時間（クウォンタム）を割り当て、そのタスクがタイムクウォンタム内に終了しない場合は、実行可能待ち行列の末尾移し、次のタスクにCPUを割り当てる。
実行可能待ち行列にあるタスクを平等に実行できるため、タイムシェアリングシステムのスケジューリングに適している。
タイムシェアリングシステム・・・複数のユーザが1台のコンピュータを、対話型で同時・平等に利用できるようにしたシステム。
フィードバック待ち行列方式
ラウンドロビン方式に優先度を加えたほう式。
処理時間順方式
SPT（shortest processing time first)方式とも呼ばれる。処理時間の短いタスクから順に実行する。
リアルタイム処理・・・即時要求ともいい、処理要求が発生すると即時に処理し、応答時間が一定の範囲内にあることが要求される処理。
同期制御
他のタスクと協調しあいながら処理を進める方ほう。
クリティカルセクションと排他制御
共有資源に対して同時に更新処理を行うと、データ不整合を引き起こすことになる処理部分をクリティカルセクション（危険領域）という。
排他制御は、あるタスクがクリティカルセクションを実行している間は、他のタスクのクリティカルセクションへの進入を防ぐ仕組み。
デッドロック
互いに相手のタスクが専有使用している資源の解放を待ちあって処理が先に進まなくなる状態のこと。
6/29 13:23
６月２９日 一周間の復習
今日はおばあちゃんの家の草刈りをやった。やっぱ体動かすこといいことだ。バイトもあって頭より体を動かした一日だった。すごく大変だけど全然つかれてない。動くことより動かない方が逆に疲れやすくなるかも。明日からまた一週間がはじまる。すごく時間の進みが早いから焦りを感じる。こんな一日一日時間の進みがはやいならまだまだ追い込めるし、時間の使い方をもっと大切にしていきたいとおもう。大学生は時間がいっぱいある。世の中には時間がない人がたくさんいる。親がこんな俺に授業料やたくさんのことにお金をかけてる。勉強できる時間があるってのはとても幸せなことだ。絶対裏切ったりはしないし恩返しするためにお金を稼ぐ。そのためには勉強し続けて無駄な時間をすごさない。たまには遊ぶがメリハリをつけて過ごす。今週新たな学びをたくさんする。めっちゃ語彙力ないし今読み返してもなんかきもい文章笑。でも今こうやって思ってること書いてちょっとでもめげそうになったらこれを読み返す。やっぱ好きな女の子に振られるとめっちゃ頑張れる。悔しいしもっと素晴らしい人間になりたいなって思う。べつに人生に勝ち負けとかないけどまだ自分はガキだし勝つ気持ちでいきたい。おじいちゃんが死ぬ前に言ってた絶対負けるなよの言葉を胸に明日から小さいことを積み重ねて成長していきたい。
6/30 3:04
6月30日
atcoder
#https://atcoder.jp/contests/abc364/tasks/abc364_d
解答
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
int N, Q;
cin >> N >> Q;
vector<ll> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
sort(A.begin(), A.end());
while (Q--) {
ll B, k;
cin >> B >> k;
ll left = 0, right = 1e18;
while (left < right) {
ll mid = (left + right) / 2;
// B から距離 mid 以内の点の数をカウント
auto it1 = lower_bound(A.begin(), A.end(), B - mid)//以上 auto it2 = upper_bound(A.begin(), A.end(), B + mid)//大きい;
ll count = distance(it1, it2);
if (count >= k) right = mid;
else left = mid + 1;
}
cout << left << endl;
}
return 0;
}
ある時点 (例: left=0, right=2)
mid = (0 + 2) / 2 = 1
判定: 距離が 1 の場合、B (2) からの範囲は [2 - 1, 2 + 1] つまり ``。
A = {1, 3, 5} の中でこの範囲にあるのは {1, 3} の 2個。
count = 2 となる。
count (2) >= k (2) なので、条件を満たす。
right = mid = 1。探索範囲は [0, 1) になります。
次の時点 ( left=0, right=1)
mid = (0 + 1) / 2 = 0
判定: 距離が 0 の場合、B (2) からの範囲は [2 - 0, 2 + 0] つまり `。
A = {1, 3, 5} の中に 2 はないので、範囲内の点は 0個。
count = 0 となる。
count (0) >= k (2) ではないので、条件を満たさない。
left = mid + 1 = 1。探索範囲は [1, 1) になります。
ループ終了
left = 1, right = 1 となり、left < right が false になるためループが終了します。
出力
cout << left; が実行され、1 が出力されます。
#https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 100000;
const int MAX_V = 1000000000;
int N;
int X[MAX_N];
int L[MAX_N];
void input(){
scanf("%d", &N);
for(int i = 0; i < N; ++i){
scanf("%d%d", X + i, L + i);
}
}
P ps[MAX_N];
int solve(){
for(int i = 0; i < N; ++i){
2
ps[i] = P(X[i] + L[i], X[i]- L[i]);
}
sort(ps, ps + N);
int cur =-MAX_V;
int ans = 0;
for(int i = 0; i < N; ++i){
if(cur <= ps[i].second){
ans++;
cur = ps[i].first;
}
}
return ans;
}
int main(){
input();
int ans = solve();
printf("%d\n", ans);
return 0;
}
応用情報
プロセスとスレッド
タスクの同義語にプロセスがある。
スレッドはプロセスを細分化した並行処理単位
#https://wa3.i-3-i.info/word12453.html
記憶管理
主記憶装置が作る記憶空間を実アドレス空間という。
実アドレス空間の割り当て方式
・単一連続割り当て方式
主記憶領域を1つのプログラムにだけ割り当てる方式
・固定区画方式
主記憶領域をあらかじめいくつかの固定長の区画に分割し、並行実行するそれぞれのプログラムに、そのプログラムが必要とする大きさを持つ区画を割り当てる方式。固定区画方式では、区画の大きさとそこで実行するプログラムの大きさが一致しなければ、区画内に未使用領域が発生する。これを内部フラグメンテーションという。
・可変区画方式
プログラムの大きさに合わせて主記憶領域を割り当てていく方式。複数のプログラムの実行と終了、つまり記憶領域の割り当てと解放が繰り返し行われると、主記憶上に不連続な未使用領域が発生する。これを外部フラグメンテーションという。未使用領域を１つの連続領域にまとめる操作をメモリコンパクションという。メモリコンパクションによって実行中のプログラムが再配置されることを動的再配置という。
オーバ例方式
主記憶を効率よく使うための方式の１つで、プログラムをあらかじめ、排他的に実行できる複数のセグメントに分割しておき、実行時に必要なセグメントを主記憶に読み込んで実行します。読み込んだセグメントは、不要なセグメントの上に配置される。
メモリプール・・・プログラムからの領域獲得要求に素早く応じられるように、ある程度の大きさの領域をあらかじめ一括で確保した領域のこと。
６月が終わった。まだまだ学ぶことが多すぎてつらい。いや楽しい。７月はもっとたくさんのことを学び、自分を成長させたい。８月になったときにはこの記事をまた読み返して自分の成長を感じたいな。あとただの日記だから記事はものすごく雑。
7/1 0:24