完全メモ, 非厳密, 無益です。

カーネル・シェル・ターミナル・コンソールとは

歴史的に厳密にはニュアンスの違い等があるらしいが, 現代ではカーネルを除いて殆ど同じ意味で使われているし, 違いを明確に知る必要もないらしい。また, OS文化圏によっても定義のされ方が異なるらしいし, ネットで調べてもきちんと理解できないので諦めました。ということで全部cmd.exeみたいなやつだと思っています。

カーネル:

OSの中’核’。CPU, メモリ, マウス・キーボード等の入出力デバイスを管理し, 実際に操る。OSに内包される。

シェル:

カーネルとユーザの橋渡し役, ユーザーはシェルを通してカーネルに命令を送る。ユーザーが直接カーネルを触れないようにするための’殻’的なイメージ。抽象化が行われてユーザが扱いやすくなる。
ex. sh, bash(shの進化系, 多くのLinuxのデフォルト), zsh(現代的), cmd.exe, windows powershell

ターミナル

ユーザがコンピュータへ入出力する際に使うハードウェア。例えば入力: キーボード, 出力: ディスプレイ。現代ではハードウェアとしてのターミナルは使われず, ターミナルをソフトとして実装したターミナルエミュレータ・仮想ターミナルの意味で使われる事が多い。

コンソール

よく分かりません。

シェルスクリプトとは

シェルを操作するためのスクリプト言語。シェルでの操作を組み合わせて自動化できる。
以下, Windows PowerShellを用いる。
現状Windowsしか使わないので, これが良さそう。
スクリプトに関するドキュメント: (https://docs.microsoft.com/ja-jp/powershell/scripting/samples/sample-scripts-for-administration?view=powershell-7.1)

やりたいこと

特定言語での操作はある程度できるようになったので, 異なるプログラミング言語同士を連携させたい。
例えば, “Heuristic系のプログラミングコンテストで複数のテストをC++に実行させて, 出た解を採点, 点数の総和 or 平均をとる”ようなことをやりたい。
今回はこれを目標にする。手順は次のとおりである。

1. C++のソースをコンパイルする
2. 実行させる
3. (ループ毎に異なる)入力を与える
4. 結果を受け取る
5. (もし採点が別に必要な場合は採点する)
6. 2~5を繰り返す
7. 点数の総和 or 平均を出力

順にやっていく。

1. C++のソースをコンパイルする

g++ A.cpp -o B -W -std=c++17
AというC++のソースをB.exeという実行ファイルにコンパイルする。-o Bは実行ファイル名の指定, -Wは警告の許可, -std=c++17はバージョンの指定。
2. 実行させる
3. (ループ毎に異なる)入力を与える
cat C.txt | .\B.exe
C.txtを標準入力としてB.exeを実行する。実行ファイルを指定する場合.\を付けて現在のディレクトリだと指定する必要がある。’|’は左側の出力を右側のコマンドの入力とするみたい。
4. 結果を受け取る(今回はB.exeの出力がスコアであるとする)
$score += cat C.txt | .\B.exe
5. (もし採点が別に必要な場合は採点する)
今回は省略。
6. 2~5を繰り返す
for ($i = 0; $i -lt 上限; $i++){処理}
通常のforループ, <が-ltになるので注意。
foreach ($変数 in $変数){処理}
範囲for
7. 点数の総和 or 平均を出力
echo $score
で出力ができる。

以上を用いて作成したコード

1
2
3
4
5
6
7
8
9

$score = 0
g++ A.cpp -o B -W -std=c++17
$tests = Get-ChildItem ".\TestCase\*"
$num = 0
foreach ($test in $tests){
    $score += cat $test | .\B.exe
    $num += 1
}
echo ($score/$num)

これを適当な名前.ps1(Powershellのスクリプトの拡張子)というテキストファイルに突っ込んで, ソースと同じディレクトリに配置, テストケースを.txtで.\TestCaseに配置して実行するとできます！
実は↑のコードはAHC002(https://atcoder.jp/contests/ahc002/tasks/ahc002_a)用に書いたのですが, うまくいきました！別のコンテストでも簡単にできそうです。

今後の課題

1. 採点用のコードがrust等で配布された場合にそのコンパイル・実行もやる
2. ヒューリスティックコンテストでは制限時間指定をするため(2s等), シングルスレッド？でやるとかなり時間がかかる。マルチスレッド対応？させると良さそう。

ふわふわが解消されつつあるがはっきりとは分からない。
気をつけたい点を中心に軽くメモ。

推定

得られた標本(sample)を元に母集団の母数(平均や分散等の母集団を特徴づける値)を推定する。
・値を推定:点推定
・何%の確率でどの範囲にいるのか推定:区間推定
以下全て母集団が正規分布に従うとする。
標本数:
標本平均:
不偏分散:

区間推定

1. 母平均の区間推定(は未知)
   確率変数を
   
   とすると, は自由度の分布に従う。
2. 母平均の区間推定(は既知)
   確率変数を
   
   とすると, は標準正規分布に従う。
3. 母分散の区間推定(は未知)
   確率変数を
   
   とすると, は自由度の分布に従う。

@疑問点
・に関して推定する訳だからなぜなのか, 符号的にが適切ではないか。
有意水準を定めて

とする訳なので両者は同値。もし, の推定をするとなったら面倒くさいことになるが基本的に無い? また, 検定における検定統計量を定めることを考えると↑の定め方でないと面倒くさいことになる。

・が未知な状態と既知な状態で持っている情報量に差があるわけだからの信頼区間は狭くなるのか
確かめたい。

検定

手順

1. 母数に関する仮説を立てる。
2. 検定統計量を定める。(推定の確率変数と同じ)
   例えば, 仮説がだとすると,
   
   とする。
3. 検定統計量が従う分布から棄却域を定める。
4. 検定統計量の実現値(実際に標本平均をに代入した値)を求める。
5. ならば仮説は棄却される。
   ならば仮説は棄却されない。

@注意&疑問
・先の推定では母数であるやについて考えたが, 今回では逆でが果たして仮説を棄却するかを確かめている。その意味では適切。
・検定では有意水準を低くとる。その意味で棄却を前提としており, 棄却されない採用とはいかない。
・ある仮説を採用したいとき, 例えばを採用したいとなれば, この仮説の否定を右側検定する(すなわち, が有意水準の確率で以上であるとき, (=棄却される)かどうかを推定する)。このとき, を帰無仮説, を対立仮説という。(棄却する=対立仮説を採用する前提の元立てる仮説なので帰無仮説, 帰無仮説と対するものなので対立仮説。)
・示したいことを背理法で示す的な目的でこの理解し難い面倒なシステムが構築されたらしい。また, 帰無仮説が棄却されたにも関わらず対立仮説が誤りであることを”第◯の誤り”と呼んだりするらしい。
・シンプルにを保証したいなら保証率みたいな形でを定めてとなる確率が以上となるを出せばいいのにと思うのだが, (コンピュータで近似値が出せるはず)分布表に汎用性が無くなるからなのか等考えています。

物理系ではないので使わないが, 微分作用素の取り扱いに慣れる目的でメモ。
しかし, お気持ちは全く理解できていない。

をで表す。
初めによりをで表す。
より

より

連鎖律(チェインルール)

手持ちの微積の教科書等には

こう記してあるが, その記法だとがに作用しそうで怖い。
関数をいれて次のように書くと馴染みがあるかもしれない。

ここで,




より




ここから2乗にしていく。



としたくなるが, そうはいかない。正しくは



つまり, 積の微分になる。


同様にについても辛い計算を行う。




以上より


終わり。

非常に苦手。ブラックボックスは良くないので雑に勉強。内容は無益です。

合同式

1. のとき(cとmが互いに素)
   
2. のとき
   

特に

[証明]


不定方程式に変形ができて

1. のとき(cとmが互いに素)
   左辺は整数よりは整数であるから
   
2. のとき
   と変形できて上の1.に帰着される。
   

モジュラ逆数 が存在する必要十分条件

aとmが互いに素であること。
このときならばはのモジュラ逆数である。

ユークリッドの互除法

２つの自然数a, bの最大公約数を求めるアルゴリズム。
とするととかける。
このとき



よって余りであるrはaとbの最大公約数Gを約数とするので, bとrについて同様にして余りとなるまで計算を行えばよい。

ex.1 : 1071と1029の最大公約数を求める。
として

このとき42はgcd(a, b)を約数とする。


よって42と21の最大公約数は21である。
21が1071と1029の最大公約数である。

拡張ユークリッドの互除法

不定方程式を満たす整数解(x, y)が存在する。
また, 整数解(a, b)は計算できる。←”拡張”部分

ex.2 : 2元1次不定方程式 の一般解を求める
↓の定理より↑の不定方程式が解を持つ-5がgcd(27, 11)の倍数であるから, 解を持つと仮定すると27a - 11b = gcd(27, 11)の両辺を-5/gcd(27, 11)倍してやれば解が求まる。よってまずgcd(27, 11)と27x - 11y = gcd(27, 11)の解を求める。ユークリッドの互除法→拡張ユークリッドの互除法をやる。



よってgcd(27, 11) = 1がわかる。上の式を変形して




↑をに引いて


x - 10とy - 25がそれぞれ11と25を約数に持つことがわかり, 一般解は

定理1: 不定方程式が整数解(x, y)を持つcがgcd(a, b)の倍数である。
[十分条件の証明]
整数解(x, y)が存在すると仮定すると
よりcはGの倍数である。
また, aとbが互いに素である任意の整数がax + byの形で表せる=必要条件

定理2: 不定方程式が整数解(x, y)を持つaとbが互いに素である。
[証明]定理1よりc = 1がgcd(a, b)の倍数であれば良い。すなわちgcd(a, b) = 1であり, aとbが互いに素であれば良い。

1次合同式

1. のとき(cとmが互いに素)
   1つの解をもつ。
2. のとき
   Gがbの約数であるときのみd個の解をもつ。
   (1次合同式は不定方程式を解くことと同値である。)

中国余剰定理(CRT: Chinese Remainder Therorem)

整数が次の連立合同式を満たすとする。

がどの2つも互いに素であるならば, は の範囲に一意に存在する。よって, の一般解は次のように表される。

なお, は で計算できる。→(https://atcoder.github.io/ac-library/production/document_ja/math.html)

中国余剰定理の一般化(法が互いに素でない場合への拡張)

整数が次の連立合同式を満たすとする。

上の連立合同式の一般解が存在する必要十分条件は
「任意のiとjに対してが成り立つ」

詳しく→(https://manabitimes.jp/math/838)

フェルマーの小定理

素数について整数がの倍数でなければ

本日3月6日のABC194にてhighestパフォ2296でAtCoder青色になりました! 良い区切り目だと思うので記念記事を書きました。

自己紹介

現在横浜国立大学理工学部に所属する学部2年生です。 主にAtCoderとCodeforcesのコンテストに参加します。 学部1年生の夏から競技プログラミングを始めたのでここまでに1年と6ヶ月を要しました。 特徴としては競プロを通してプログラミングを始めたこと, 正直数学が得意でも好きでもないこと等があると思います。(最近は数学頑張っているつもりですですが…)

初期スペック

地方県立高校から横浜国立大学に入学しました。
センター試験の数学が平均90点とれるくらいの数学力でした。

初参加

「プログラミング勉強したい」という意識高い系のノリで2019/07/07にABC133
に初めて参加しました。成績はA1完でパフォ139でした。また, 初参加から5回の平均パフォーマンスは260でした。思った以上に奮わず, 化け物だらけの魔界に入ってしまったかのような気分でしたが, ここから沼にはまっていきます。

競技プログラミング部への入部

せっかくあるなら入ろうとの考えで2020年1月に横浜国立大学競技プログラミング部に入部しました。優秀な先輩ばかりで本当に刺激になります。丁度本日もアルゴリズム講習会→コンテストで最大フロー, 最小カットを学びました。
・毎週2度のコンテスト→先輩による解説
・質問を投げるとすぐにだれかが答えてくれる
・ICPCへの参加 etc…

100問精進

2020年2月頃から100問精進を始め, 春休みを通して2ヶ月程度で一通り終わらせました。これを通じて体系的に水色程度の知識を得ることができた気がします。

PythonからC++への転向

2020年4月頃に先輩からの助言を受け, PythonからC++へ転向しました。
以下のようなメリットとデメリットを感じました。

メリット

• 多数派の恩恵
  解説記事等の充実度の大きな差があります。
• 連想配列map
  解説でmapを使っている問題に出会うとかなり苦痛でした。
• 理論上正答できない問題が無くなる
  時間制約上, 通すことの難しい問題はあります。 意味の無い定数倍高速化に時間を費やしたり, 時間をかけてそれ以上の高速化ができずに正答できないときは苦しいです。
• 他のコンテストサイトに出れる
  CodeforcesではC++でも時間制約の厳しい問題が割とあったと記憶しています。

デメリット

• パフォーマンスはあまり変わらない
  たまにC++でのみズルができますが, そのようなケースは少ないです。
• 定数倍を重ねた雑なアルゴリズム設計をしがちに

水色になる

2020年7月のエイシングプログラミングコンテストでAtCoder水色になりました。

青色になる

本日3月6日, AtCoder青色になりました。
ようやく簡単な典型知識が体に染み込んできた感覚があり, 今までに解けなかった水diff程度の問題に対しても明らかにアプローチの仕方が変わっていると感じることがあります。現在までの解いた問題の数は以下のとおりです。

Solved By KY2001
Topcoder: 0
Codeforces: 108
AtCoder: 1012
AOJ: 89
yukicoder: 12
library-checker: 13
Sum: 1234 https://t.co/AJBwX3O8Tn

— ky (@ky2001_cpc) March 6, 2021

今後

現段階では黄色は目指していませんが, 現段階では青タッチに過ぎないので青安定までは行きたいです。競プロはあくまで趣味なので適度にしつつ, 数学もやりたいと考えています。最近は4月の数検1級に向けた勉強と教習所・バイトに追われています。

反省

実は今日のコンテスト, Eを解き終わってからFのAC数の少なさからベットでゴロゴロしていました。。。流石に良くないということで, 戻ってくる訳ですが, 普通のdpですね。。。こういうのは本当に良くないです。

現在の考え

早解き

水色になるまでは早解きはあまり好きではなく, 他人より一問多く解くことを意識していました.しかし, そもそも早解きしないと後ろの問題に多くの時間を割けないことや, そもそも早解き力は上げようとしてもなかなか上げられないこと等から今では早解きは必要なスキルだと考えています。

土台の大切さ

適正diff未満の問題を如何に高速に解けるかが非常に大切だと思います。 基礎部分を疎かにすると中々上に上がれないと痛感します。

才能

自分より強い人ほど自分よりたくさん解いているので, 気にしていません。個人的には才能というよりは, 人生で触れてきた数学的な教養が大切だと感じます。

楽しむ

Nosub防止目当てで提出したり, コンテストに寝坊した結果残り10分でABCに参加したりして非常に低パフォをとったことがあります。 結果レートが-100され, 取り戻すのにも苦労しました。 当たり前ですが, 著しくモチベーションが下がるので良くないです. 自分に優しく楽しみたいです。

精進の仕方

○分経ったら解説を読むというようなルールは無いです。 こうじゃないかというアイデアが尽きない限りは考え続けるようにしています。
ただ一問に数時間かけるのは時間的効率は悪いので他人には薦められませんが。
また, 実装を少し変えるだけ等の場合を除いて基本的に解説ACはしていません。これは実装よりアイデアが本質であるという考えと単に作業じみて面倒くさいという怠惰さに基づいています。

ハフマン符号化

情報源記号を符号化する際に, 平均符号長を最小にするような符号化の方法の１つをハフマン符号化という.

m元ハフマン符号化のアルゴリズム

1. 各情報源記号に対応する葉をつくる.
2. 今ある中で確率の最も小さいm個の葉を子とする新たな葉をつくる.
3. 葉の数がm個未満になるまで1, 2を繰り返す.
4. m個未満の今ある全ての葉を子とする根をつくる.
5. 根から部分木の確率の総和が小さい順に0…m-1を割り当てる.
6. 根から情報源記号にあたる葉まで降りながら割り当てられた数を拾っていく.

例えばについて, , であるとき
Sの2次拡大情報源を3元ハフマン符号化すると次の図のようになる.

左の赤い数字がハフマン符号にあたる. このハフマン符号の平均長さ(平均符号長)を最小化することでデータが最小限に圧縮できる.
平均符号長は情報源記号の確率を, ハフマン符号の長さをとすると次式で定義される.

つまり, よく出てくる情報源ほど小さい符号長を割り当てたいということである.

エントロピー

Sのエントロピーは情報源iの確率をとして次のように定義される.

Sのエントロピーは平均符号長の下界となる.

実装概要

情報源の数が小さいうちは上図のように手で符号を割り当てられるが, あまりに多いと大変なので計算機に計算させる.
方針としては

1. 無記憶情報源Sとn次拡大情報源のn, m元ハフマン符号化のmを入力する.
2. 頂点(葉)にあたる構造体を自作する. (部分木の確率の総和と子のリストをもつ.)
3. 優先度付きキューを用いて, 確率の小さいm個をとってその親をいれるを繰り返す.
4. 根ができれば, 根から深さ優先探索の要領でハフマン符号を取り出していく.

C++による実装例.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <bits/stdc++.h>
using namespace std;

double length = 0; //平均符号長

struct node {         //頂点にあたる構造体
  double val = 0;     //部分木の確率の総和
  vector<node> child; // 子のリスト
};

bool operator<(const node &a, const node &b) { //nodeに関する比較演算子を定義する.
  return a.val < b.val;
};
bool operator>(const node &a, const node &b) { //nodeに関する比較演算子を定義する.
  return a.val > b.val;
};

void restore(node &a, string &now, vector<string> &ans) { //深さ優先探索でハフマン符号を取り出す.
  if (a.child.empty()) {                                  //子がいない場合
    ans.emplace_back(now);                                //ハフマン符号を答えに追加
    length += now.size() * a.val;                         //平均符号長に長さ*確率を足す.
    return;
  }
  for (int i = 0; i < a.child.size(); i++) { //子がいる場合
    now += to_string(i);                     // 0..m-1を割り当てる
    restore(a.child[i], now, ans);           //深さ優先探索
    now.pop_back();                          //割り当てを戻す
  }
}

int main() {
  int S_size, n, m; //Sの大きさ, n次拡大, m元ハフマン化
  cin >> S_size >> n >> m;
  vector<double> S;
  for (int i = 0; i < S_size; i++) {
    double u, l; //Sの各情報源は有理数u/lの状態で入力
    cin >> u >> l;
    S.emplace_back(u / l);
  }
  vector<double> SE = S; //Sのn次拡大情報源
  for (int i = 0; i < n - 1; i++) {
    vector<double> temp; //現在のSEとSの直積
    for (auto &j: SE)
      for (auto &k: S) temp.emplace_back(j * k);
    SE = temp;
  }
  priority_queue<node, vector<node>, greater<>> tree; //優先度付きキュー, 値の小さいものほど先にでるようにしている.
  for (auto &i: SE) {                                 //Sのn次拡大情報源を葉としてtreeに追加.
    node temp;
    temp.val = i;
    tree.push(temp);
  }
  while (1) {               //葉がたくさんあるうちは繰り返し
    if (tree.size() == 1) { //葉が根のみになった場合終わり
      break;
    } else if (tree.size() < m) { //葉が2以上m未満→それを繋げた根を作る.
      m = tree.size();
    }
    node temp;
    for (int _ = 0; _ < m; _++) {
      temp.val += tree.top().val;          //子の確率の総和を持つ.
      temp.child.emplace_back(tree.top()); //子のリストを持つ.
      tree.pop();
    }
    sort(begin(temp.child), end(temp.child)); //子のリストはsortしておく.
    tree.push(temp);
  }
  vector<string> ans; //答えとなるハフマン符号のリスト
  string now;
  node root = tree.top(); //木の根
  restore(root, now, ans);
  vector<vector<string>> display(100); //可視性のためサイズが大きいほど遅く出力されるようにする. ここではサイズは100までとする.
  for (auto &i: ans) display[i.size()].emplace_back(i);
  for (int i = 0; i < 100; i++) {
    sort(begin(display[i]), end(display[i]));
    for (auto &j: display[i]) cout << j << endl;
  }
  cout << length << endl; //平均符号長を出力.
}

チェック

実装にバグがないか確かめる.
これに先のについて, , についてハフマン符号化していく.

1. Sの2次拡大情報源を3元ハフマン符号化.

エントロピーは



平均符号長は

入力

1
2
3
4

3 2 3
1 2
1 3
1 6

出力

1
2
3
4
5
6
7
8
9
10

0
10
11
12
21
22
200
201
202
1.88889(平均符号長)

見事に手計算した先の図とハフマン符号は完全に一致している.

2. Sの3次拡大情報源を2元ハフマン符号化.

平均符号長は

入力

1
2
3
4

3 3 2
1 2
1 3
1 6

出力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

000
100
0011
0101
0110
1110
1111
00100
00101
01000
01001
01110
10100
10110
11001
11010
11011
011110
101010
101011
101110
101111
110000
0111110
0111111
1100010
1100011
4.41204(平均符号長)

3. Sの3次拡大情報源を4元ハフマン符号化.

入力

1
2
3
4

3 3 4
1 2
1 3
1 6

出力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

00
01
02
03
11
12
13
22
100
101
102
103
200
201
202
203
210
211
212
213
231
232
233
2300
2301
2302
2303
2.44907(平均符号長)

離散畳み込み

関数, の畳み込みは次のように定義される。

関数の値をN点でサンプリングすると

これを離散畳込みという。 素直に計算すると, N回積をとってN-1回その項の総和を取るので計算量はとなる。
また, これを0…N-1全てのnについてを求めるとになる。
高速フーリエ変換(FFT)を用いるとこれがで計算できる。

離散畳み込みの応用例

1. 多項式乗算の高速化
   n次のxに関する多項式, についてその積をとする。
   このとき, , の次の係数をそれぞれ, , として次が成り立つ。
   
   これは畳み込みそのものである。

2. 相関関数の計算
   信号, に対しての相関関数は
   
   離散化して
   

DFT(離散フーリエ変換)

離散的信号に対して, 離散フーリエ変換は次の式で定義される。

ここで表記を簡単にするために回転因子を用いると