競プロ典型90問 018(★3) 三角関数
問題
平面 x = 0 上に、高さ L の T 分で一周する観覧車がある。
xy 平面が水平で z が垂直。
- 0 分後の座標は
分後の座標は
分後の座標は
銅像が にある。
以下の形式の質問が Q 個与えられるので順に求める。
- i 個目の質問では、
分後における、銅像の俯角を求める。
解法
三角関数を色々使う。
sin, cosを使うときはラジアンでの角度が引数になっている。
そのため a 度における sin の値を求めたい場合、 にする必要がある。
銅像と観覧車の水平距離を A, 観覧車の高さを B とする。
求める俯角は となる。
観覧車の座標を とするとき、
水平距離は、
高さは、 となる。
所感
数学ちっくな問題は、苦手なので勉強しなければ。。
三角関数など、あまり使う機会がないので面白かったけど難しいー。
コード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<int, int>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; const int INF = (int)1e9; const ll INFL = (ll)1e18; const int MOD = 1e9 + 7; const double EPS = 1e-10; int dx[]={0, 0, -1, 1}; int dy[]={1, -1, 0, 0}; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } const double PI = acos(-1); double t, l, x, y, e, q; double solve(double d) { double cx, cy, cz, d1, d2, fukaku; cx = 0; // x座標 cy = -(l / 2.0) * sin(d / t * 2.0 * PI); // y座標 cz = (l / 2.0) - (l / 2.0) * cos(d / t * 2.0 * PI); // z座標 d1 = sqrt(pow((cx - x),2) + pow((cy - y), 2)); // 水平距離 d2 = cz; // 観覧車の高さ fukaku = atan2(d2, d1); return fukaku * 180.0L / PI; } int main() { cin >> t; cin >> l >> x >> y; cin >> q; rep(i,q) { cin >> e; cout << solve(e) << endl; } return 0; }
競プロ典型90問 016(★3) 全探索
問題
A円、B円、C円と硬貨が3種類ある。
それぞれ0枚以上使ってちょうどN円を支払うとき、使う硬貨の枚数の最小値を求める。
解法
そのまま全探索すると になり、TLEする。
そのためループを3重から2重へと減らす必要がある。
xとyの値が決まれば で定まるので
へ落とせる。
所感
制約にもよるが、3重ループはTLEになる場合が多い。
ちょっとした工夫で大幅に計算量が減らせる事もあるので、いろんな視点で考えるようにしたい。
コード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<int, int>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; const int INF = (int)1e9; const ll INFL = (ll)1e18; const int MOD = 1e9 + 7; const double EPS = 1e-10; int dx[]={0, 0, -1, 1}; int dy[]={1, -1, 0, 0}; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int main() { ll n, a, b, c; cin >> n; cin >> a >> b >> c; ll ans = INFL; for (ll i = 0; i <= 9999; i++) { for (ll j = 0; j <= 9999 - i; j++) { ll tmp = n - (a * i) - (b * j); if (tmp < 0) continue; if (tmp % c == 0) // ここで余りを求めて判定することで、ループを削減する。 { ll cnt = i + j + tmp / c; chmin(ans, cnt); } } } cout << ans << endl; return 0; }
競プロ典型90問 014(★3) 貪欲法
014 - We Used to Sing a Song Together（★3）
問題
N人。家は にある。
学校は N校あり、 にある。
- 全員別の学校に通わせる。
- 学生 i の家から学校までの距離
である。
- 位置 u から位置 vまでの距離は
不便さの最小値を求める。
解法
A,B ともにソートして、前から差の絶対値を足していくだけ。
全体計算量は で求められる。
所感
内容がシンプルだったのでそのままって感じだった。
コードもシンプルに書けた。
コード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<int, int>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; const int INF = (int)1e9; const ll INFL = (ll)1e18; const int MOD = 1e9 + 7; const double EPS = 1e-10; int dx[]={0, 0, -1, 1}; int dy[]={1, -1, 0, 0}; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int n; int a[100100], b[100100]; ll ans; int main() { cin >> n; rep(i,n) cin >> a[i]; rep(i,n) cin >> b[i]; sort(a, a + n); sort(b, b + n); rep(i,n) ans += abs(a[i] - b[i]); cout << ans << endl; return 0; }
競プロ典型90問 007(★3) 二分探索
問題
N個のクラス、Q人の生徒。
クラスのレーティングは , 生徒のレーティングは
と表す。
不満度は対象レーティングと自分のレーティングの差の絶対値。
各生徒の不満度の最小値を求める。
解法
Aをソートして 以上と未満の値の2つを比べる。
そのどちらかが不満度の最小値となる。
lower_bound を用いることで で求められる。
配列のソートとQ回の二分探索を行うので全体計算量はとなる。
所感
要素数に合わせて配列を宣言すると、入力部分がごちゃついてしまう。
制約に合わせて上限値で配列を確保しておいたほうが楽かもしれない。
その代わり、begin(), end()といったイテレータが使えないのでsort(a, a+n) みたいに書くことを注意したい。
コード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<int, int>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; const int INF = (int)1e9; const ll INFL = (ll)1e18; const int MOD = 1e9 + 7; const double EPS = 1e-10; int dx[]={0, 0, -1, 1}; int dy[]={1, -1, 0, 0}; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int main() { int n, q; cin >> n; vector<int> a(n); rep(i,n) cin >> a[i]; cin >> q; vector<int> b(q); rep(i,q) cin >> b[i]; sort(a.begin(), a.end()); rep(i,q) { auto it = lower_bound(a.begin(), a.end(), b[i]); int over = abs(b[i] - *it); if (it != a.begin()) it--; int under = abs(b[i] - *it); cout << min(over, under) << endl; } return 0; }
競プロ典型90問 002(★3) next_permutation
002 - Encyclopedia of Parentheses（★3）
問題
長さNの正しいカッコ列を出力する。
条件
()は正しい。- Sが正しいとき、
(+ S +)は正しい。 - S,Tが正しいとき、文字列 S + T は正しい。
(の方が)よりも辞書順で早いものとする。
解法
まず奇数の場合は何も出力しない。
Nの半分ずつを ( と) で埋めた文字列を作る。
左から順に見ていって ( の数より ) の数が多くなったら条件を満たさない。
後は逐一 () の確認をしながら next_permutation で辞書順に出力していく。
(())() # OK ())(() # NG
所感
辞書順に出力するという条件から next_permutation を使用したが、bit全探索でも求められるみたい。
むしろそっちが本筋だったと思うので、気が向いたときに解き直してみたい。
コード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; using P = pair<int, int>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; const int INF = (int)1e9; const ll INFL = (ll)1e18; const int MOD = 1e9 + 7; const double EPS = 1e-10; int dx[]={0, 0, -1, 1}; int dy[]={1, -1, 0, 0}; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int main() { int n; cin >> n; if (n % 2 == 1) return 0; string s; rep(i,n / 2) s.push_back('('); rep(i,n / 2) s.push_back(')'); do { int cnt = 0; rep(i,n) { if (s[i] == '(') cnt++; if (s[i] == ')') cnt--; if (cnt == -1) break; } if (cnt == -1) continue; cout << s << endl; } while (next_permutation(s.begin(), s.end())); return 0; }
第2章 情報の表現と操作
2章について
この章では、コンピュータ上における数値の扱い方について詳しく書かれていました。
IEEE浮動小数点や、整数型の演算、算術シフトにおける注意点など、幅広く扱っています。
以下まとめです。
データ･サイズ
ワード･サイズがあり、仮想アドレスはこのワードによってエンコードされる。近年ワードサイズは、32から64ビット移行が進んでいる。
典型的なサイズやコンパイラの設定に依存するのを避けるため、固定のデータ･サイズ持つ型もある。
- int32_t : 厳密に4バイト
- int64_t : 厳密に8バイト
ちなみにポインタはプログラムの1ワード･サイズを使う。
エンディアンとは？
2バイト以上で表現される数値の、メモリへの格納方式のこと。
リトル･エンディアン : 下から上にバイトを格納する。
ビッグ･エンディアン : 上から下にバイトを格納する。
バイ･エンディアン : リトル･エンディアン、ビッグ･エンディアンを切り替えられる。
エンディアンが違うマシンでのやりとりにおける注意点
- バイトの順序が逆になる。
- キャストした場合に異なる結果が出る。
論理処理とシフト演算
論理演算
- OR(||), AND(&&), NOT(!)
- 引数が0以外ならTRUE、0ならFALSEを表している。
- 結果がTRUEなら1、FALSEであれば0を返す。
式 結果 !0x42 -> 0x00 !0x00 -> 0x01 !!0x42 -> 0x01 0x42 && 0x24 -> 0x01 0x42 || 0x24 -> 0x01
シフト演算
コンピュータは2進数を扱っているため、2の累乗の乗算と除算は、ビットをずらすことで計算できる。
[01100011] x << 4 [00110000] x >> 4 [00000110] (論理シフト) x >> 4 [11111110] (算術シフト)
注意点は、負数の右シフトで、算術シフトが行われるかどうかは処理系定義であること。
そのため、左シフトを使って演算するなどの工夫があると良さそう。
#include <stdio.h> int main() { int x = -1024; int y = x >> 1; // 算術シフトが行われるかは処理系定義 int z = x / (1<<1); // 左シフトを使うことで安全に演算できる printf("y = %d, z = %d\n", y, z); return 0; }
符号付きと符号なしキャスト
Cでは異なる数値データ型をキャストする事ができる。
あくまでビットの解釈を変えるだけで、ビット値自体は同じ。
#include <stdio.h> int main() { int i = -1; unsigned int ui = (unsigned int)i; int j = (int)ui; // i = -1, ui = 4294967295, j = -1 printf("i = %d, ui = %u, j = %d\n", i, ui, j); return 0; }
そもそも全部符号付き整数型にしておけば良さそう？と思ったが、符号なしが便利になる場合もあるらしい。
例としては、数字をビットの集まりとして考えたい場合やアドレスを扱う場合などがある。
加算
符号なし加算
x + y が 2w - 1 より大きい場合、和はオーバーフローする。(w = ワードサイズ)
4ビットで表現される場合(2^4-1=15) x = 9 [1001] y = 12[1100] x + y = 21[10101]([1111]=15よりも大きい) 上位ビットを破棄して5[0101]になる。 これは 21 mod 16 = 5 と一致する。
二の補数の加算
ワードサイズが4の場合(-8 ≤ x < 8) の範囲が扱える
4ビットで表現される場合 x = -8[1000] y = -5[1011] x + y = -13[10011] 上位ビットを破棄して3[0011]になる。 x = 5[0101] y = 5[0101] x + y = 10[01010] 上位ビットを破棄して-6[1010]になる。
これにより、INT_MAX([1111...] 31ビット全て立っている状態)に 1 を加算すると
INT_MIN([1000...] 32ビット目(符号ビット)だけが立っている状態) になるということが分かりますね。
乗算と除算
定数の乗算 - 定数の乗算をシフトと加算の組合わせに置き換えることで命令数が減らせる。
乗算の置き換え 11[1011]<<2 = 44[101100] (11*4 = 44 と同じ) 14 = 2^4 - 2^1 x * 14 = (x<<4) - (x<<1) # 置き換えることで最適化できる。
二の累乗による除算
除算は乗算よりも遅いので、同じくシフト演算を使うことで最適化を図る。
符号なし数 k >> k (二進数） (12340/2^k) 0 [0011000000110100] = 12340 12340.0 1 [0001100000011010] = 6170 6170.0 4 [0000001100000011] = 771 771.25 8 [0000000000110000] = 48 48.203125
浮動小数点
非常に大きい数や0に非常に近い数を伴う計算を行ったり、実数の算術を近似できる。
現在は、IEEE浮動小数点が一般的に扱われている。
各桁の重み付けは小数点記号('.')との相対位置で定まる。
は
と表される 。
- 2進数
は
と表される。
IEEE浮動小数点表現
x と y を用いて の形式の数で表す。
IEEEの標準規格は数を、 の形式で表す。
- 符号 s は、正負を表す(正なら 0、負なら 1)。
- 仮数 M は、 0 以上で基数より小さい数の範囲。
- 指数 Eは、基数の何乗かを表す。
- 基数は、n進数のnに当たる部分(2または10)。
浮動小数点数のビット表現をこれらの値をエンコードするために三つの部分に分ける。
(例)
123.456 78 を、仮数部が整数の十進浮動小数点数で表すと、仮数は 12345678、指数は −5 となる。
式で表すと
正規化
expが全て0または 1(単精度で255、倍精度で2047)のどちらでもない場合。
ケチ表現
二進法で正規化をすると、最上位ビットは常に 1 になるので、これを表さず常に 1 があるものとみなす省略が可能。
この省略した表現をケチ表現と言う。
省略することで、仮数部に割り当てたビット数が n であれば、有効桁数は n+1となる。
非正規化
- 指数フィールドが全て
0の場合、表される数は非正規化値である。 - 指数部が
である。
- 数値0、また0.0に非常に近い数を表す。
特殊な値
また特殊な値として、浮動小数点には特殊な値として、inf や NaN も表現できる。
- 小数フィールドが全て0の場合、
なら
の、
なら
を表す。
- 少数フィールドが非ゼロの場合、
NaNを表す。
丸め
表現の範囲と精度が限られているため、実数の算術を近似するにすぎない。
そのため、4種類の丸め演算を使い、値に対して表せる最も近い値を見つける。
- 偶数丸め、0への丸め、切り下げ、切り上げの4種類
ちなみにデフォルトでは偶数丸めが使われている(最も近い整数の値となる)
Cにおける浮動小数点
C言語ではfloat(単精度) と double(倍精度) がある。
偶数丸めが使われており、丸めモードを変更したり、 のような特殊な値を得る標準的な方法はない。
また、キャストする際には、丸めにより望んだ結果が得られない場合があるため注意する。
浮動小数点演算
算術演算の結果として丸めを適用した値が返される。
IEEEの強みは、演算結果がハードウェアやソフトウェアに依存しないという点にある。
重要な特性として、浮動小数点演算は結合的ではない( (a+b)+c=a+(b+c) が成り立たない場合があるということ)
例)
となり
が丸みによって消える。
となる。
このように浮動小数点数の演算においては、順番を気をつける必要がある。
感想
そもそもコンピュータが情報をビットで表現しているということから始まり、浮動小数点についてまで順を追って学ぶことができました。
正直難しいなーと思うこともありましたが、図や表で視覚的に説明されてあり、なんとか読み進める事ができました。
また、これまではビットの扱いが苦手でしたが、今後は必要に応じて使っていこうと思います。
なんとなく知っているけど、詳細はよく知らないな。というものが、あーそういうことだったのね。という体験がたくさんできるので、興味ある方はぜひ読んでみてください。
第1章 コンピュータ･システム･ツアー
- そもそもCSAPPとは？
- コンピュータ･システムとは？
- .cファイルからa.outを作成する
- システムのハードウェア構成
- キャッシュの重要性
- オペレーティング・システム
- 平行性と並列性
- 抽象化って？
- 感想
そもそもCSAPPとは？
コンパイラやリンカ、メモリの仕組みからネットワーク･プログラミングなど、幅広く多様な側面から学べる1冊です。
コンピュータ・サイエンスで有名なカーネギー･メロン大学で教科書としても扱われています。
1000ページ近くあり、内容も盛りだくさんです。
今後、各章ごとに軽いまとめと感想を書いていきます。
今後購入を検討している方の参考になれば幸いです。
1章について
この章では、プログラムの基本である｢hello world!｣はどのように実行されているのか。
抽象化や、メモリの仕組み、並行性など、今後の章で学んでいくことについての軽い説明がされていました。
以下まとめです。
コンピュータ･システムとは？
ハードウェアとシステム･ソフトウェアが連携してアプリケーション･プログラムを走らせるように構成されたもの。
.cファイルからa.outを作成する
プリプロセッサ(cpp)→コンパイラ(cc1)→アセンブラ(as)→リンカ(ld)の順に処理される。
プリプロセス : 文字'#'で始まる(#includeなど)情報を解釈する。
コンパイル : テキストファイルをアセンブリ言語に翻訳する。
アセンブリ : マシン語に翻訳してオブジェクト･ファイルへ格納する。
リンク : オブジェクトファイルの結合を行う。
システムのハードウェア構成
バス : 各構成要素の間で情報を行き来させる。
I/Oデバイス : キーボード、マウス、ディスプレイなど。
メインメモリ : 一時的な記憶デバイス。DRAMチップの集合体。
プロセッサ : CPUのこと。命令を実行するエンジン。
キャッシュの重要性
キャッシュを利用し、頻繁にアクセスするデータを保持させることで、高速なアクセスを可能にさせる。
L1~L3キャッシュはSRAMで実装されている。L1が最も高速だが容量が小さい。
オペレーティング・システム
以下の2つの目的がある。
1. アプリケーションの間違った使用からハードウェアを守る。
2. ハードウェア･デバイスを操作するための仕組みをアプリケーションに提供する。
プロセス、仮想メモリ、ファイルという抽象化を利用している。
プロセス : 実行中のプログラムを抽象化したもの。
スレッド : プロセスはスレッドと呼ばれる複数の実行単位から成り立っている。
仮想メモリ : メインメモリを独占的に使っているように各プロセスに見せる仕組み。
ファイル : 一連のバイトのこと。
平行性と並列性
平行性 : 複数処理を同時に行うシステムという概念のこと。
並列性 : システムを速く走らせるために並行性を利用すること。
並行性は3つの階層に分けられる。
スレッドレベル : (抽象化レベル: 上)
スレッドを使うことで、一つのプロセス内で複数の制御フローを実行できる。
一台のウェブサーバから複数のユーザが同時にやり取りすることを可能にする。
命令レベル : (抽象化レベル: 中)
複数の命令を同時に実行することができること。
最近プロセッサは同時に100もの命令処理ができる。
SIMDレベル : (抽象化レベル: 下)
プロセッサが一つの命令で複数の演算を並列に行うハードウェアを持っていること
SIMD命令は主に、画像や音声、動画データの処理の高速化に役立っている。
抽象化って？
内部の働きを知らなくても扱えるようにすること。
抽象化により、技術的な複雑さが軽減され、効率的な設計と実装が可能になる。
例)API、Cのプロトタイプ宣言、Javaのクラス宣言、仮想マシンなど
感想
実際には図や練習問題もあり、楽しみながら学べています。
また、C言語はどのようにして生まれたか。UNIXとPOSIXの起源といったコラムもあり、飽きずに取り組めそうです。
まだ一章で先は長いですが、引き続き読み進めていきます。
