AtCoderチャレンジまとめ(2) - AtCoder Beginner Contest 116
やりたいこと
そんなわけでAtCoderにチャレンジ !
チェレンジコンテスト
AtCoder Beginner Contest 116 - AtCoder
変数名適当でごめんなさい。。。初めてのAtCoder。
問題A : Right Triangle
直角三角形 ABC があります。∠ABC=90°
です。
三角形 ABC の三辺の長さである |AB|,|BC|,|CA| が与えられるので、直角三角形 ABC
の面積を求めて下さい。
ただし、三角形 ABC の面積は整数となることが保証されています。
自分の回答
#include<iostream> using namespace std; int main(){ int a,b,c; cin>>a>>b>>c; int ans; ans = a*b/2; cout << ans << endl; return 0; }
問題B : Collatz Problem
数列 a={a1,a2,a3,......}
は、以下のようにして定まります。
初項 s
は入力で与えられる。
関数 f(n) を以下のように定める: n が偶数なら f(n)=n/2、n が奇数なら f(n)=3n+1。
i=1のとき ai=s、i>1 のとき ai=f(ai−1)である。
このとき、次の条件を満たす最小の整数 m
を求めてください。
am=an(m>n)
を満たす整数 n が存在する。
自分の回答
#include<iostream> #include <set> using namespace std; int main(){ int a; cin>>a; set<int> values; int ans = a; for(int i=0; i < 100000000; ++i){ values.insert(ans); if(ans%2==0){ ans = ans / 2; }else{ ans = 3 * ans + 1; } if (values.size()!=i+1){ break; } } cout << values.size() + 1 << endl; return 0; }
先生の回答
#include<iostream> #include <set> using namespace std; int main(){ int a; cin>>a; set<int> values; int ans = a; while(values.count(ans) == 0){ values.insert(ans); if(ans%2==0){ ans = ans / 2; }else{ ans = 3 * ans + 1; } } cout << values.size() + 1 << endl; return 0; }
- setのcountを使って重複があるかどうかを調べている(values.count(ans) == 0)。こっちのほうがイイね!
問題C : Grand Garden
花壇に N 本の花が咲いており、それぞれ 1,2,......,N と番号が振られています。最初、全ての花の高さは 0 です。 数列 h={h1,h2,h3,......} が入力として与えられます。以下の「水やり」操作を繰り返すことで、すべての k(1≦k≦N) に対して花 k の高さを hk
にしたいです。
整数 l,r
を指定する。l≦x≦r を満たすすべての x に対して、花 x の高さを 1 高くする。
条件を満たすための最小の「水やり」操作の回数を求めてください。
先生の回答
#include<iostream> using namespace std; int main(){ int n; cin>>n; int a[n]; for(int i=0; i < n; i++){ cin>>a[i]; } int ans = 0; int active = 0; for(int i;i<n;i++){ if(active>=a[i]){ active = a[i]; }else{ ans += a[i]-active; active = a[i]; } } cout << ans << endl; return 0; }
とてもシンプル!素晴らしい。
問題D : Various Sushi
N 個の寿司があり、それぞれの寿司には「ネタ」ti と「おいしさ」di のパラメータが設定されています。 あなたはこの N 個の寿司の中から K 個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。 「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。 「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。 「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を x としたとき、x∗x である。 あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。
回答
TBD 時間あるとき追記します〜
所感
D問題解けるようになりたい。
AtCoderチャレンジまとめ(1)
やりたいこと
そんなわけでAtCoderにチャレンジ ! の前の準備笑
教科書
けんちょんさんわかりやすい記事ありがとうございます!
計算オーダー
名言 : 標準ライブラリがあっても、中身の計算量を意識しよう! ex: list (Python) からの検索処理は遅い
計算回数の目安: 1秒間で処理できる for 文ループの回数は、100,000,000 回程度(10の8乗)
計算時間の比較: logn < n < nlogn < n2 < n3 < 2n < n!
- 実用的なレベルとして、n3あたりが限界
全探索
幅優先探索 : グラフ を始点から近い順に1つずつ調べていく探索法
- 深い階層まで一本道で探索する場合は幅優先探索が有用。 ex: 迷路でスタートからゴールにたどり着きたいケース
深さ優先探索 : ある状態から始めて、遷移できなくなるまで状態遷移を続け、遷移できなくなったら一つ前の状態に戻って・・・を繰り返すことで、 グラフ の全頂点を漏れなく調べる探索法
- 1つの階層に大量のノードが存在する場合は深さ優先探索が有用。 ex: 辞書順で最初の解を求めるケース
があり、どちらを選択するかは問題に依る。
ソート
既存のライブラリの性能が高い。 ex: C++ の std::sort() はクイックソートをベースとしながらも最悪時の計算量も O(nlogn)O(nlogn) になっている
安定ソート : 同等なデータのソート前の順序が、ソート後も保存されるもの
ソート種類
- 挿入ソート : 基本的にはそんなに速くない安定ソート。
- マージソート : 高速な安定ソート。
- クイックソート : 安定ソートでないが高速。C++ の std::sort() もクイックソートがベース。
- ヒープソート : 最小値や最大値を常に取り出せるようなアルゴリズムで、安定ソートではない。
参考: ソートを極める! 〜 なぜソートを学ぶのか 〜 - Qiita
bit演算
45をbitで表すと? : 0b00101101(0bは二進数を表す)
AND : int a,b; cout << a&b << endl;
OR : int a,b; cout << a|b << endl;
& ビットごとの AND | ビットごとの OR ^ ビットごとの XOR ~ ビットごとの反転(1 の補数) << 左シフト >> 右シフト
bitsetsで出力 : int a,b; cout << bitset<8>(a&b) << endl; // 00001001のように表示される
a ,b ,c 番目のフラグが立っている状態 : (1<<a) | (1<<b) | (1<<c)
マスク演算 : bit & mask ; // mask で表された部分の情報のみを取り出したもの
所感
次は練習問題をいろいろ解いてみよう。 D問題普通に難しい。。。
今後の勉強予定
AtCoderチャレンジまとめ(0)
やりたいこと
そんなわけでAtCoderにチャレンジ ! の前の準備笑
教科書
けんちょんさんわかりやすい記事ありがとうございますm( )m
A問題の学び
問題分をよく読んで出力形式には注意すること。ex: cout << a << " " << b << endl;の" "を書き忘れる etc ...。
(プロコンの場合)変数名はシンプル。タイピング速度重視。
一行でかけるときはまとめる。 ex: if (c % 2 == 0) cout << "Even" << endl;
stringを受けて文字にアクセスするときはこう↓
string s; cin >> s; int counter = 0; if (s[0] == '1') ++counter;
++iとi++について↓
・ ++i の作用は式の値として、i + 1 の値を返す事、副作用は i に i + 1 の結果が代入される。
・ i++ の作用は式の値として、i の値を返す事、副作用はその後 i に i + 1 の結果が代入される。
B問題の学び
boolの真偽は小文字でtrue, false。大文字で書いちゃダメ。
計算量が少なく、考える時間を短縮したいときはfor分での全探索が有効なケースあり。
n進数の考え方やbit演算ができると良い。
sort大事。
#include <algorithm> int N; int a[100]; // a[0:N] を大きい順にソート sort(a, a + N, greater<int>());
バケット法よく使う。
setが便利。
#include <set> ... set<int> values; // insert するときに重複を取り除いてくれます for (int i = 0; i < N; ++i) { values.insert(d[i]); // 挿入します }
- 最大最小もよく使う。
const int lower = max(A,C); const int upper = min(B,D);
計算の工夫として、N!のSで割った余りを求めたい時は、オーバーフローを防ぐため、N! % Sより、(N%S) * ((N-1)%S)* ・・・としたりする。
a以上b以下の整数のうち条件を満たすものの個数を求める問題ではf(n) := 0以上n以下の整数のうち条件を満たすものの個数のように関数定義するとf(b)-f(a-1)で求めることができる。
C問題の学び
計算量オーダーの考え方が大事。
解き始める前にどのように解くかを計算量やタイプ量、便利関数などを加味してしっかり考えることが大事。ex: 後ろからGreedyした方が簡単 etc...
探索方法大事。
パリティ(「偶数」と「奇数」に関する性質)の考え方大事。
グリッドの作り方例: char c[55][55]; string board[50];
上下左右斜め移動の表し方例 ↓
const int dx[8]={1,0,-1,0,1,-1,-1,1}; const int dy[8]={0,1,0,-1,1,1,-1,-1};
感想
めっちゃ楽しい :D
今後の勉強予定
温湿度・気圧センサモジュールを動かしてみる
やりたいこと
BOSCH BME280センサを動かしてみる
購入先
教科書
準備
ブレッドボード
ジャンパピン
プルアップ用抵抗(10kΩ)x 2
Arduino Nano (Uno)
BME280
配線の仕方
- VCC(3.3Vへ)
- GND(GNDへ)
- SCL(SCK) <- プルアップ抵抗10kΩをはさむ
- SDA(SDI) <- プルアップ抵抗10kΩをはさむ
- CSB(3.3Vへ)
- SDO(GNDへ)
書き込むコード
BME280 – スイッチサイエンスに記載のコードBME280_I2C.inoをそのまま使用
結果
所感
だいたいあってる。安いし、そこそこの値をとるにはバッチリだと思う。
さすがBOSCH :)
参考
ブログ
温度・湿度・気圧センサモジュールの実験 ←わかりやすい
ライブラリ
サーモカメラOWLIFTを動かしてみる
やりたいこと
事前の環境設定
python3
python3のライブラリのみなので、python3環境を用意しておく
既存環境を汚したくない場合、例えばvirtualenvを利用する
$ sudo apt-get install virtualenv $ virtualenv -p python3 "my_env" $ source my_env/bin/activate
抜けたいときは
$ deactivate
参考: venv: Python 仮想環境管理 - Qiita
opencv
$ pip install opencv-python
OWLIFTライブラリのインストール
python library
以下からwhlファイルをダウンロード
以下コマンドでインストール
$ pip3 install owlift-xxx.whl
その他
参考: インフィニテグラ株式会社 | 小型サーマルカメラ OWLIFT
APIドキュメント
サンプルコード
以下からダウンロード
実行結果
USBでカメラをPCを繋いで以下を実行
$ python preview_basic.py
暖房を入れた時のエアコンの吹き出し口が熱を持っていることがわかる↓
蛍光灯に向けるとこんな感じ↓
所感
デバイスやセンサごとに特性があって面白い♪
WideResNetのお勉強
やりたいこと
Wideなネットワークについて理解を深めたい
内容理解
教科書: Residual Network(ResNet)の理解とチューニングのベストプラクティス - DeepAge
スキップコネクションでDeepなネットワークの学習が可能に。
BatchNormは下図の左を用いるとよい。
activationの位置に関して下図の右の方が良い結果に。
WideResNetはこのResNetのフィルタ数を増やすことで、GPUを活用し、浅いネットワークで同等の表現力を持つように改良したもの。kが広さの係数。
Dropoutの入れ方。
実装参考
わかりやすいブログや資料
Global Average Pooling (GAP)
教科書: Global Average Pooling(GAP)を理解してみる - Qiita
通常の全結合
GAP
実装参考
参考ブログ
所感
計算資源や学習対象によって適切なネットワークを選択できるようになりたい!
MobileNetV2のお勉強
やりたいこと
計算処理が軽いDNNの構築。低スペックのPCでもガンガン認識を回したい。
論文
MobileNetsの理解
通常のCNNではチャンネル間の特徴・チャンネル内の特徴(画像内の特徴)をフィルターによってまとめて考えるのに対し、MobileNetsではそれらをdepthwiseとpointwiseの畳み込みに分離し、表現しパラメータを削減している。
また、処理速度と精度を調整するためのwidth multiplierとresolution multiplierというパラメータもうまく設計されている。
参考: MobileNets: CNNのサイズ・計算コストの削減手法_翻訳・要約 - MUSCLE PROGRAMMER's BLOG
通常のCNN
Depthwise Separable Convolution
実装(TBD)
書き次第掲載予定。Tensorflowで書いてみようかな。
V2の理解(TBD)
参考スライド
参考ブログ
深層学習の計算コスト削減、MobileNetの設計思想 | Accel Brain Good Blog !!!
MobileNets: CNNのサイズ・計算コストの削減手法_翻訳・要約 - MUSCLE PROGRAMMER's BLOG
[Survey] MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications - Qiita
参考実装
Tensorflow
mobilenet-v2-tensorflow/models.py at master · timctho/mobilenet-v2-tensorflow · GitHub
models/research/slim/nets/mobilenet at master · tensorflow/models · GitHub
Pytorch
GitHub - kuangliu/pytorch-cifar: 95.16% on CIFAR10 with PyTorch
GitHub - MG2033/MobileNet-V2: A Complete and Simple Implementation of MobileNet-V2 in PyTorch
pytorch-mobilenet/main.py at master · marvis/pytorch-mobilenet · GitHub
GitHub - ericsun99/MobileNet-V2-Pytorch: Model shared. Top1:71.806/Top5:90.410
所感
軽量なDNNの工夫おもしろい。
低スペックPCで認識を回すために引き続きキャッチアップしよう。