AtCoderチャレンジまとめ(3) - NIKKEI Programming Contest 2019
やりたいこと
そんなわけでAtCoderにチャレンジ !
チェレンジコンテスト
全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder
問題A : Subscribers
私たちは、新聞の購読に関する調査を行いました。 具体的には、調査の対象者 N 人に対し、それぞれ次の 2つの質問を行いました。
質問 1 : あなたは新聞 X を購読しているか? 質問 2 : あなたは新聞 Y を購読しているか?
その結果、質問 1 に対して「はい」と回答した人の数は A 人、質問 2 に対して「はい」と回答した人の数は B人でした。
このとき、調査の対象者のうち新聞 X, Y の両方を購読している人の数は最大で何人であり、また最小で何人であると考えられるでしょうか?
この問いに答えるプログラムを書いてください。
入力は以下の形式で標準入力から与えられる。
N
A
B
自分の回答
#include<iostream> using namespace std; int main(){ int a,b,c; cin >> a >> b >> c; int amax; int amin; if(a >= b+c){ amin = 0; }else{ amin = b+c - a; } amax = min(b,c); cout << amax << " " << amin << endl; return 0; }
問題B : Touitsu
三つの文字列 A,B,C が与えられます。これらはそれぞれ、英小文字からなる長さ Nの文字列です。
私たちの目標は、これら三つの文字列をすべて等しくすることです。そのために、あなたは次の操作を繰り返し行うことができます。
操作: 文字列 A,B,Cのうち一つを選び、さらに 1 以上 N 以下の整数 i を指定する。そして、選んだ文字列の先頭から i文字目を別の何らかの英小文字に変更する。
目標を達成するためには最小で何回の操作が必要でしょうか?
入力は以下の形式で標準入力から与えられる。
N
A
B
C
自分の回答
#include<iostream> #include <set> using namespace std; int main(){ int n; cin >> n; string s1,s2,s3; cin >> s1 >> s2 >> s3; int ans=0; for(int i=0;i<n;i++){ set<int> values; values.insert(s1[i]); values.insert(s2[i]); values.insert(s3[i]); ans += values.size() - 1; } cout << ans << endl; return 0; }
問題C : Different Strokes
高橋くんと青木さんの前に N 皿の料理が置かれています。 便宜上、これらの料理を料理 1、料理 2、…、料理 Nと呼びます。
高橋くんが料理 iを食べると彼は Ai ポイントの 幸福度 を得ます。 また、青木さんが料理 i を食べると彼女は Biポイントの幸福度を得ます。
彼らは、高橋くんから始めて交互に、料理を 1皿ずつ選んで食べることを料理が尽きるまで続けます。 ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。
このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか?
入力は以下の形式で標準入力から与えられる。
N
A1
B1
:
AN
BN
自分の回答
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n; cin >> n; int a[n],b[n]; for(int i=0;i<n;i++){ cin >> a[i] >> b[i]; } std::vector<int> vec(n); long sumao=0; for (int i = 0; i < n; ++i) { vec[i] = a[i] + b[i]; sumao += b[i]; } std::sort(vec.begin(),vec.end(),std::greater<int>()); //降順ソート long sumta=0; for(int i=0;i<n;i++){ if(i % 2 == 0){ sumta += vec[i]; } } cout << sumta - sumao << endl; return 0; }
longで足りないこともあるから、競プロの人はlong longを使っている人が多い。
問題D : Restore the Tree
N 頂点の根付き木 (注記を参照) があり、その頂点には 1 から N までの番号が振られています。 根以外の各頂点には、その親から一本の有向辺が伸びています。 なお、根は頂点 1とは限りません。
高橋くんは、このグラフに M本の新たな有向辺を書き加えました。 書き足された各辺 u→v は、ある頂点 u からその子孫であるような頂点 vに向かって伸びています。
高橋くんが辺を書き加えたあとの N頂点 N−1+M 辺の有向グラフが与えられます。 より具体的には、N−1+M 組の整数のペア (A1,B1),...,(AN−1+M,BN−1+M) が与えられ、これらは i 番目の辺が頂点 Ai から頂点 Biに向かって伸びていることを表します。
元の根付き木を復元してください。
入力は以下の形式で標準入力から与えられる。
N
M
A1
B1
:
AN−1+M
BN−1+M
自分の回答
TDB 時間ができたら追記します。
参考: 有向非巡回グラフ(DAG)の意味とトポロジカルソート - 具体例で学ぶ数学
所感
やっぱりD問題が難しい。今回はトポロジカルソートを知らないと結構キツい。。。
D問題を解けるように頑張る!
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
実装参考
参考ブログ
所感
計算資源や学習対象によって適切なネットワークを選択できるようになりたい!