C++のお勉強（３） - ポインタ/スマートポインタ
やりたいこと
ポインタの考え方(特にC++11)を理解し、使いこなせるようにする
ブラウザでのコード実行方法
C++ Shell がおススメ
ポインタ
型* 変数名 = オブジェクトのアドレス
&は変数のアドレスの取得
*は指定したアドレスのデータにアクセス
例1 : アドレスを利用した値の書き換え
#include <iostream> #include <string> using namespace std; int main (){ string name = "doraemon"; string *name_address; name_address = &name; *name_address = "dramichan"; cout << name << endl; // dramichan cout << *name_address << endl; // dramichan return 0; }
例2 : ポインタのポインタ
#include <iostream> using namespace std; int main(){ string name = "atom"; string* name_address = &name; string** name_address_adress = &name_address; *name_address = "uran"; // uran cout << name <<endl; // uran cout << **name_address_adress <<endl; }
スマートポインタ
スマートポインタで管理されるオブジェクトは明示的にdeleteしなくても、使われなくなったら自動的に破棄される
unique_ptr
あるメモリの所有権を持つ unique_ptr
使い方
#include
で使える。 ポインタの保持するメモリにアクセスするには、operator*()や operator->()が使用可能。
unique_ptr
は、コピーは禁止だが、ムーブは可能。 deleterの指定可能。
ポイント
unique_ptrで良いところにshared_ptrは使わない
shared_ptr
同一のメモリの所有権を複数で共有できるようにしたスマートポインタが、shared_ptr
使い方
#include
で使える。 ポインタの保持するメモリにアクセスするには、operator*()や operator->()が使用可能。
コピーもムーブも可能。
deleterの指定可能。
ポイント
shared_ptrの初期化にmake_sharedを使うこと
unique_pointに比べて遅い
循環参照に気をつけて！以下のような状況を指す。
#include <iostream> #include <memory> class Robot { public: Robot() {} ~Robot() {} std::shared_ptr<Robot> hand_ptr; }; int main() { std::shared_ptr<Robot> r1 = std::make_shared<Robot>(); std::shared_ptr<Robot> r2 = std::make_shared<Robot>(); r1->hand_ptr = r2; r2->hand_ptr = r1; return 0; } // pointaが解放されない！
- 循環参照はstd::weak_ptrで解決できる
weak_ptr
循環参照によって生じる問題を防ぐために導入されたスマートポインタで所有権をもたない
使い方例
#include <iostream> #include <memory> class Robot { public: Robot() {} ~Robot() {} std::weak_ptr<Robot> hand_ptr; }; int main() { std::shared_ptr<Robot> r1 = std::make_shared<Robot>(); { std::shared_ptr<Robot> r2 = std::make_shared<Robot>(); r1->hand_ptr = r2; r2->hand_ptr = r1; } // ここでr2が解放 return 0; } // ここでr1が解放
ポイント
- ダグリングポインタ（無効なメモリ領域を指すポインタ）に気をつけること！以下に例を示す。
std::shared_ptr<Robot> robot = std::make_shared<Robot>();
std::weak_ptr<Robot> weak_robot = robot;
// この間に、robotの寿命が切れるとweak_robotはダグリングポインタになってしまう
- ここで監視しているshared_ptrオブジェクトを取得するlock関数を用いることでダグリングポインタの問題に対処できる。例えば以下のようにして不正アクセスを防ぐことができる。
if (auto r = weak_robot.lock()) { // こうすることで不正アクセスを防いだうえで*r に対して処理をかける }
参考 : weak_ptr::lock - cpprefjp C++日本語リファレンス
使い分け
使用頻度としてはunique_ptr > shared_ptr > weak_ptrが理想的
まず unique_ptr
の利用を検討する。 複数で共有する必要のある場合、shared_ptr
を利用する。 循環参照になっていないか確認し、なっている場合weak_ptr
を利用する。
所感
次は右辺値・左辺値・ムーブについて理解したい。
全体参考
Sim2Real論文まとめ（１） - SimGAN
やりたいこと
センサノイズをシミュレータで再現したい。
そのために有用そうなSimGANを理解する。
論文について
CVPR2017でBest Award
珍しいAppleの論文
評価
☆☆☆☆☆(5/5)
めちゃくちゃコスパ良いアプローチ。素晴らしい。
内容まとめ
Abstract
教師あり学習の難点として、たくさんのラベル付きデータが必要になる。
シミュレータでデータを作ることが期待されているが、シミュレータと実世界の乖離が問題で上手く行かないことが多い。
本論文はその溝を埋める手法を提案する。
方法としてはラベル付きのシミュレーションのデータとラベルなしの実データを用いて、Genertive Adversarial Networks(GANs)によりシミュレーションデータを実データに近づける(S+U Learning with SimGAN)。
以下の三点がキーポイント。
a "self-regularization" term
a local adversarial loss
updating the discriminator using history of refined images
これらによってリアリスティックな画像を生成することができる。
Introduction
シミュレータをリアルに近づけるアプローチも盛んだが、良いレンダリングアルゴリズムのものを使ったとして、実世界を完全に再現できているわけでなく、これを用いて学習した場合、過学習することもある。
この論文の目標はラベリングなしの実データとシミュレータを用いてリアルな画像を生成すること。
そのために、refinerというネットワークを考案した。下図参照。
これはシミュレータが作った生成画像をrefineする。
実データに近づけるため、refinerはadversarial lossを用いて訓練する。
これはGANsに似たアプローチをとっていて、実データとの区別がつかないように更新するdiscriminative networkを用いている。
ここで、生成データのアノテーション情報を保つため、生成データとrefineされたデータの差にペナルティを与えるようなself-regularization lossをadversarial lossに追加している。
そして、ピクセルレベルでのfully CNNを用いることで、大域的な構造を保つ。
GANsのアプローチは対立する２つのネットワークを訓練するため、不安定になりがち。これに対して、discriminatorの受容野を画像全体ではなく複数の局所的な領域に制限する。
さらに安定に訓練を行うため、過去のrefineされた画像を用いてdiscriminatorの更新を行う。
Contributions
ラベルなしの実データを用いて合成データをrefineする(S+U learning)
adversarial lossとself-regularization lossを用いてrefiner networkを訓練する
refiner networkを安定して訓練するためのGANsに対するいくつかの大事な修正を行う
定性的な実験結果とSOTAな結果を示す
S+U Learning with SimGAN
ゴールはアノテーション情報を保持しつつ生成画像をリアルに近づけるrefinerを訓練すること。
以下の２つの損失関数によって、関数パラメータθを学習によって最適化する。
第一項は実データに近づける作用、第二項はアノテーション情報を保つ作用がある。
詳細はこれから説明。
Adversarial Loss with Self-Regularization
- GANsに似ている提案手法は同様に２つのネットワークのminmax gameであり、refiner networkとdiscriminator nerworkを交互に更新する。
Discriminator
- discriminator networkは以下の損失関数を最小化することによってΦを更新する。
この式は交差エントロピー誤差で~xiが生成データ、yiが実データである。
Dはrefineされた画像である確率を出力する層を最終層に持つConvNetとして実装。つまり、refineであれば1、実データであれば0が理想。
確率的勾配降下法によって更新する。
Refiner
- (1)式のlrealは訓練済みのdiscriminatorを用いて以下のようにかける。
このロス関数が小さくできれば、discriminatorをより騙すようなrefinerに近づく。
さらに、生成されたリアルな画像はシミュレータで付与されたアノテーション情報も保ってほしい。
これを実現するため、生成データとrefineされたデータのピクセルレベルでの違いを小さくするようself-regularization lossを用いる。
そうすると、(1)の式は以下にような表現になる。こおｋでψは恒等関数。||はL1ノルム。
- ここでRはピクセルレベルでrefineするためプーリングなどがないfully convolutinal neural netで実装。
更新則
以下の通りでR(θ)を更新する間はΦを固定、D(Φ)を更新する間はθを固定。
交互に繰り返してLr(θ)とLd(Φ)を最小化する。
Local Adversarial Loss
refinerがとても強いdiscriminatorを訓練した時、refinerが過度に特徴を強調する方向へ働くことがある。
ここで、局所的な状態もrefinerはリアルに近づけるべきで、同様にdiscriminatorも局所的な情報で判断できるべき。
上記を踏まえ下図のように discriminatorのネットワーク出力をw x hの確率マップにし、refinerのadversarial loss関数を局所パッチのcross entropy lossesで表す。
Updating Discriminator using a History of Refined Images
discriminatorが最新のrefined imagesにのみ正しく区別できる傾向に陥ることがある。
これは本来すべてのrefined imagesを正しく区別したいため良くない。
なので、discriminatorの更新時に過去のrefined imagesも使用することで、安定性を向上させる。
下図のようにmini-batchの半分を最新の画像、もう半分をバッファにためていた画像を用いる。
以上がSimGANのロジックの部分。
Experiments
ここからは画像ベースでSimGANを使った向上例をペタペタ貼り付けます。かなり汎用性がありあそう。
視線方向はたもちつつ、リアルな画像へrefine↓
- より詳細↓
- 手の姿勢推定のためのDepth画像への適応例↓
- 過去の画像を使ってdiscriminatorを更新したことの効果↓
- Local adversarial loss の効果↓
所感
実機でデータセットを作るのはホント大変なので、生成データとアノテーションなしの実データでSimlationとRealのGapを埋めれるのは素晴らしい。
特にセンサのノイズは個体によって異なるし、表現しにくいので、このアプローチはほんとに興味深い。
AtCoderチャレンジまとめ（6） - AtCoder Beginner Contest 119
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
変数名が適当なのはご愛嬌
A問題: Still TBD
文字列 S が入力されます。これは、西暦 2019 年の実在する日付を yyyy/mm/dd の形式で表したものです。(例えば、2019 年 4 月 30日は 2019/04/30 と表されます。)
Sが表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力するプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { std::string s; cin >> s; char cary[10]; s.copy(cary, 10); std::string sn(""); for (int i=0;i<10;i++){ if (i != 4) { if (i != 7){ sn += cary[i]; } } } int num = atoi(sn.c_str()); if(num>20190430){ cout << "TBD" << endl; } else { cout << "Heisei" << endl; } return 0; }
B問題:
高橋くんは N人の親戚からお年玉をもらいました。
N個の値 x1,x2,...,xN と N 個の文字列 u1,u2,...,uN が入力されます。各文字列 ui は JPY または BTC であり、xi と ui が i人目の親戚からのお年玉の内容を表します。
例えば、x1=10000, u1= JPY であれば 1 人目の親戚からのお年玉は 10000 円であり、x2= 0.10000000, u2= BTC であれば 2 人目の親戚からのお年玉は 0.1ビットコインです。
ビットコインを 1.0BTC あたり 380000.0 円として換算すると、高橋くんがもらったお年玉は合計で何円に相当するでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N
x1 u1
x2 u2
:
xN uN
出力
高橋くんが受け取ったお年玉が合計で Y 円に相当するとき、値 Y(整数とは限らない) を出力せよ。
出力は、ジャッジの出力との絶対誤差または相対誤差が 10−5以下のとき正解と判定される。
自分の回答
#include <iostream> using namespace std; int main() { int n; cin >> n; double x; std::string u; std::string str="JPY"; double ans; for (int i; i<n;i++){ cin >> x >> u; if (std::string(u)==str){ ans += x; } else { ans += x * 380000.0; } } cout << ans << endl; return 0; }
C問題: Synthetic Kadomatsu
あなたは N 本の竹を持っています。これらの長さはそれぞれ l1,l2,...,lNです (単位: センチメートル)。
あなたの目的は、これらの竹のうち何本か (全部でもよい) を使い、長さが A,B,Cであるような 3本の竹を得ることです。そのために、以下の三種類の魔法を任意の順に何度でも使うことができます。
延長魔法: 1 MP (マジックポイント) を消費し、1 本の竹を選んでその長さを 1増やす。 短縮魔法: 1 MP を消費し、1 本の長さ 2 以上の竹を選んでその長さを 1減らす。 合成魔法: 10 MP を消費し、2 本の竹を選んで接続し 1 本の竹とする。この新たな竹の長さは接続した 2本の竹の長さの合計に等しい。(以後、この竹に対してさらに魔法を使用することもできる。)目的を達成するには、最小でいくつの MP が必要でしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N A B C
l1
l2
:
lN
出力
目的の達成に必要な MP の最小量を出力せよ。
自分の回答
時間以内に解けなかった...Cが解けないのは辛い。
全探索大事。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int N; int A,B,C; long long brute_force_search(int cnt, int a, int b, int c, int L[]) { long long INF = std::pow(10, 9.0); if (cnt==N) { if ((a!=0)&&(b!=0)&&(c!=0)){ return std::abs(a-A)+std::abs(b-B)+std::abs(c-C)-30; } else { return INF; } } vector<long long> ansc(4); ansc[0] = brute_force_search(cnt+1, a, b, c, L); ansc[1] = brute_force_search(cnt+1, a+L[cnt], b, c, L)+10; ansc[2] = brute_force_search(cnt+1, a, b+L[cnt], c, L)+10; ansc[3] = brute_force_search(cnt+1, a, b, c+L[cnt], L)+10; int min = *std::min_element(ansc.begin(), ansc.end()); return min; } int main() { cin >> N >> A >> B >> C; int len[N]; for (int i; i<N;i++){ cin >> len[i]; } long long ans; ans = brute_force_search(0, 0, 0, 0, len); cout << ans << endl; return 0; }
ちょっとだけ解説
a,b,c=0の状態から始まり初期の１本追加するときに10を足しているので、
最後にABC3本分の30を引いているのと、
一本も追加しない場合は成り立たないのでINFとしてる。
D問題: Lazy Faith
東西方向に伸びる道路に沿って A 社の神社と B 軒の寺が建っています。 西から i 社目の神社は道路の西端から si メートルの地点に、西から i 軒目の寺は道路の西端から tiメートルの地点にあります。
以下の Q個の問いに答えてください。
問 i (1≤i≤Q): 道路の西端から xi メートルの地点から出発して道路上を自由に移動するとき、神社一社と寺一軒を訪れるのに必要な最小の移動距離は何メートルか？ (必要数を超えた数の寺社を通過してもよい。)
入力
入力は以下の形式で標準入力から与えられる。
A B Q
s1
:
sA
t1
:
tB
x1
:
xQ
出力
Q 行出力せよ。i 行目に問 i への答えを出力すること。
自分の回答
これも時間以内にとけなかった。二分探索がポイント。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { int A,B,Q; cin >> A >> B >> Q; vector<long long> jin(A+2); vector<long long> tera(B+2); long long INF = std::pow(10, 18); jin[0] = -INF; jin[A+1] = INF; tera[0] = -INF; tera[B+1] = INF; for (int i=1; i<A+1;i++){ cin >> jin[i]; } for (int i=1; i<B+1;i++){ cin >> tera[i]; } long long q; for (int i; i<Q;i++){ cin >> q; long long b = upper_bound(jin.begin(), jin.end(), q) - jin.begin(); long long d = upper_bound(tera.begin(), tera.end(), q) - tera.begin(); long long ans = INF; vector<long long> jinv{jin[b-1],jin[b]}; vector<long long> terav{tera[d-1],tera[d]}; vector<long long> dv(3); for (auto j: jinv) { for (auto t: terav){ dv[0] = std::abs(j-q)+std::abs(t-j); dv[1] = std::abs(t-q)+std::abs(j-t); dv[2] = ans; ans = *std::min_element(dv.begin(), dv.end()); } } cout << ans << endl; } return 0; }
二分探索参考
所感
Cが解けずに時間が経過すると、めっちゃ焦る。。。冷静に解決のための手段を一個ずつ洗い出せるようにしないと。
まずいろんなアルゴリズムの知識を網羅的につけて正しく選択できるところを目指そう。
AtCoderチャレンジまとめ（5） - AtCoder Beginner Contest 118
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
変数名が適当なのはご愛嬌
A : A - B +/- A
正整数 A,Bが与えられます。
Aが B の約数なら A+B を、そうでなければ B−A を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
A が B の約数なら A+B を、そうでなければ B−A を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { int a,b; cin >> a >> b; if(b%a==0){ cout << a+b <<endl; } else { cout << b-a<< endl; } return 0; }
B : Foods Loved by Everyone
カツサンドくんはオムライスが好きです。
他にも明太子や寿司、クリームブリュレやテンダーロインステーキなどが好きで、これらの食べ物は全て、誰もが好きだと信じています。
その仮説を証明するために、N人の人に M種類の食べ物について好きか嫌いかの調査を行いました。
調査の結果、i番目の人は Ai1 番目, Ai2 番目, ..., AiKi番目の食べ物だけ好きだと答えました。
N人全ての人が好きだと答えた食べ物の種類数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N M
K1 A11 A12 ... A1K1
K2 A21 A22 ... A2K2
:
KN AN1 AN2 ... ANKN
出力
N 人全ての人が好きだと答えた食べ物の種類数を出力せよ。
自分の回答
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n,m; cin >> n >> m; vector<int> v; for(int i=0;i<n;i++){ int a; cin >> a; for (int j=0;j<a;j++){ int b; cin >> b; v.push_back(b); } } int ans=0; for(int i=1;i<m+1;i++){ int n_count = std::count(v.begin(), v.end(), i); if (n_count==n){ ans += 1; } } cout << ans << endl; return 0; }
C : Monsters Battle Royale
N 体のモンスターが居て、それぞれ 1,2,...,Nと番号付けられています。
はじめ、モンスター iの体力は Aiです。
以降、体力が 1以上のモンスターを生きているモンスターと呼びます。
生きているモンスターが 1体になるまで以下を繰り返します。
- ランダムに 1体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。
- その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。
最後に生き残ったモンスターの最終的な体力の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N
A1 A2 ... AN
出力
最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。
自分の回答
基本的に体力の小さい２つのみに着目して解けることに気づいた。
体力の小さい順にソートして、 2番目に1番小さいもので割り切れれば、最小体力は1番目のままなので、2番目を削除。
割り切れない場合は、2番目 = 2番目-1番目とし、2番目を更新する。そして、2番目が1番目を下回ったら再度sort。
以降これらの繰り返しで最後の一つが残るまで繰り返す。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { long long n; cin >> n; vector<long long> a(n); for(long long i;i<n;i++){ cin >> a[i]; } std::sort(a.begin(),a.end()); while(true){ if(a.size()==1){ break; } if (a[1]%a[0]==0){ a.erase(a.begin()+1); } else { a[1] = a[1] - a[0]; if(a[1]<a[0]){ std::sort(a.begin(),a.end()); } } } cout << a[0] << endl; return 0; }
D : Match Matching
ちょうど N本のマッチ棒を使って作れる整数の中で最大のものを求めてください。
ただし、以下の条件を満たさなければなりません。
作る整数の各桁は、1から 9 までの数字のうち A1,A2,...,AM(1≤Ai≤9)のいずれかでなければならない。
数字 1,2,3,4,5,6,7,8,9を 1 つ作るには、それぞれちょうど 2,5,5,4,5,6,3,7,6 本のマッチ棒を使う。
入力
入力は以下の形式で標準入力から与えられる。
N M
A1 A2... AM
出力
問題文の条件下でちょうど N本のマッチ棒を使って作れる整数の最大値を出力せよ。
けんちょんさんの回答の写経
いつもありがとうございます!!! そして、またしてもDが解けない。。。
教科書: AtCoder ABC 118 D - Match Matching (400 点) - けんちょんの競プロ精進記録
以下のかんたんな例を用いて動的計画法の内容を理解。
入力例:
8 2
3 7
3を作るのにマッチ5本、7を作るのにマッチ3本。なので、73が答えだとわかる。
これをけんちょんさんのDP（iはマッチの本数で dpは作れる数字が入る）で考えると
i = 0の時 dp[5] = 3, dp[3] = 7 i =1,2の時は作れる数字がないのでスキップ i = 3の時 dp[3+5] = 73, dp[3+3] = 77 i = 4の時は作れる数字がないのでスキップ i = 5の時 dp[5+5] = 33, dp[5+3] = 73 (*) ここで前のdp[8]に73が入っているので、37と比較して大きい73を入れる i = 6の時 dp[6+5] = 773, dp[6+3] = 777 i = 7の時は作れる数字がないのでスキップ i = 8の時 dp[8+5] = 733, dp[8+3] = 737
よってdp[8]=73より73が答えだとわかる。8本与えられたときに作れる最大の数。
以下写経コード。
#include <iostream> #include <string> #include <vector> using namespace std; const string MINUS_INF = "-"; void update_char_max(string &a, string b){ if (a == MINUS_INF){ a = b; } else if (a.size() < b.size()) { a = b; // stringの比較のため、まず桁違いのものは更新 } else if (a.size() == b.size()) { if (a < b) { a = b; // 同じ桁のstringは純粋に値の比較 } } } long long match_map[10] = {2,5,5,4,5,6,3,7,6}; string dp[100000]; int main() { int n, m; cin >> n >> m; vector<int> a(m); for (int i=0; i<m; ++i) { cin >> a[i]; } // 初期化 for (int i=0; i<100000; ++i) { dp[i] = MINUS_INF; } // 初期条件 dp[0] = ""; // DP ループ for (int i = 0; i <= n; ++i) { if (dp[i] == MINUS_INF) continue; for (auto ae : a) { update_char_max(dp[i+match_map[ae-1]], dp[i]+(char)('0'+ae)); } } cout << dp[n] << endl; }
所感
autoが便利だし、どんどん使っていこう。
動的計画法を使いこなせるようになったら、Dの解ける問題が増える気がする。DP頑張る。
あとはちょっとした初期化の書き方だったり、読みやすくて、短いコードを意識して書いていきたい。
AtCoderチャレンジまとめ（4） - みんなのプロコン 2019
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
Yahoo Programming Contest 2019 - AtCoder
変数名が適当なのはご愛嬌
問題A: Anti-Adjacency
1 以上 N 以下の異なる整数を、差が 1 の整数をともに選ばないように K 個選ぶことができるか判定してください。
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
整数を K 個選ぶことができるなら YES を、そうでないなら NO を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { int n,k; cin >> n >> k; int ans; ans = (n+1)/2; if(ans>=k){ cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }
問題B: Path
4 つの街があり、順に 1,2,3,4 と番号が付いています。 道が 3 本あり、i 本目の道は異なる街 ai,bi を双方向に結んでいます。 同じ街の対の間を結ぶ道が複数あることはありません。
街同士を行き来する手段は、道以外にはありません。 どの2つの街の間も、道を何本か通ることで行き来することができます。
すべての道をちょうど 1回ずつ通ることですべての街を訪れることが可能かどうか判定してください。
入力
入力は以下の形式で標準入力から与えられる。
a1 b1
a2 b2
a3 b3
出力
すべての道をちょうど 1 回ずつ通ることですべての街を訪れることが可能なら YES を、そうでないなら NO を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { int a1,b1; cin >> a1 >> b1; int a2,b2; cin >> a2 >> b2; int a3,b3; cin >> a3 >> b3; if (a1==a2 || a1==b2) { if(a1==a3 || a1 ==b3){ cout << "NO" << endl; return 0; } } if (b1==a2 || b1==b2) { if(b1==a3 || b1 ==b3){ cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0; }
解説
問題の構成から、異なる街を選ぶこと、同じ道は作らないことから、計3セットのa,bの中で同じ数字が3つない場合にすべて訪れることを発見。
つまり、3セットのすべてに同じ数が含んでいるものを除く。
問題C: When I hit my pocket...
すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K回行います。
・持っているビスケットを叩き、1枚増やす
・ビスケット A枚を 1円に交換する
・1円をビスケット B 枚に交換する
K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { long long k,a,b; cin >> k >> a >> b; long long ans1; ans1 = (k-a+1) / 2; ans1 = (ans1-1) * (b-a); ans1 = ans1 + b + (k-a+1)%2; long long ans2; ans2 = k+1; if(ans1 > ans2){ cout << ans1 << endl; } else { cout << ans2 << endl; } return 0; }
解説
A+2 < Bのときは、お金に交換→ビスケット生成がより増やせる。
そうでないときは、交換せずにビスケットを叩きまくる。
A+2 < Bのときは、基本的に最初の一回交換するまでは叩いて増やす必要があるが、その後は
・ ビスケット A枚を 1円に交換する
・ 1円をビスケット B 枚に交換する
というように2回で(B-A)個を増やすことができる。
D: Ears
数直線上にすぬけ君がいます。すぬけ君は L個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。
・座標 0未満の点や座標が Lより大きい点を通ることはない ・整数座標の点で散歩を開始し、整数座標の点で散歩を終了する ・整数座標の点でのみ、進む方向を変えることができるすぬけ君は、座標が整数 iを用いて i−0.5 と表される点を通るたびに、i 番目の耳に石を 1個入れます。
すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、 各 iに対しすぬけ君の i 番目の耳には Ai個の石が入っているようにしたいです。
・すぬけ君の耳をひとつ選び、石を 1個入れる ・石が 1個以上入っているすぬけ君の耳をひとつ選び、石を 1個取り出すすぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
L
A1
:
AL
出力
必要な操作の回数の最小値を出力せよ。
入力例
4
1
0
2
3
出力例
1
自分の回答
これは時間以内に解けなかったので、解説を見て検討しました。
#include <iostream> #include <vector> #include <algorithm> using namespace std; long long cost(long long* A, const long long& index, const long long& area){ if (area==0 || area==4) { return A[index]; } else if (area==1 || area==3) { if (A[index]==0) { return 2; } else if(A[index]%2==0) { return 0; } else { return 1; } } else if (area==2){ if (A[index]%2==0){ return 1; } else { return 0; } } } int main() { long long n; cin >> n; long long A[n]; for(long long i=0;i<n;i++){ cin >> A[i]; } vector< vector<long long> > dp; dp.resize(n); for(long long i=0; i<n; i++){ dp[i].resize(5); } for(int j=0;j<5;j++){ dp[0][j] = cost(A,0,j); } for(long long i=1;i<n;i++){ dp[i][0] = dp[i-1][0]+cost(A,i,0); for(int j=1;j<5;j++){ long long mindp = *std::min_element(dp[i-1].begin(), dp[i-1].begin()+j+1); dp[i][j] = min(mindp+cost(A,i,j), dp[i][j-1]); } } long long ans = *std::min_element(dp[n-1].begin(), dp[n-1].end()); cout << ans << endl; return 0; }
解説
以下の5つにわけて、下図にあるような考え方、動的計画法（DP）で解きました。
まず、すぬけくんのスタート、ゴール位置をS,Tとし、散歩中の最小・最大位置をD,Uとします。
i <= DのときはXi=0なので、この範囲のコストはAiそのまま。りんごさんはAi回操作必要。
D < i <= Sのときは、Xiは0でない偶数であればコスト0。0であれば行って戻ってこないといけないのでコスト2。奇数の場合コスト1。
S < i < Tのときは、Xiが奇数ならばコスト0。偶数ならばコスト1。
T < i <= Uのときも2.と同様。Xiは0でない偶数であればコスト0。0であれば行って戻ってこないといけないのでコスト2。奇数の場合コスト1。
U < iのときも1.と同様。この範囲のコストはAiそのまま。
このコストの考え方を用いて、入力例を用いて示すと
のようなコストマップがかけ、緑☆のように左列と上ブロックの情報を用いてすべてのブロックが計算できる。
最後に最終列の最小値を求めればそれが答え。
問題E: Odd Subrectangles
問題F: Pass
所感
すぬけくんがバケモノ過ぎて問題解くときに焦った笑
メモ時の大量の耳がある、すぬけくん↓↓↓
Eigen事始め
やりたいこと
C++で行列計算を高速に行いたい！
ので、行列計算ライブラリEigenを学ぶ。
教科書
インストール
Eigen からダウンロードする。
もしくはROSが入っている場合、
/usr/include/eigen3/Eigen
にEigenがインストールされている。
コンパイル方法
g++ -I /path/to/eigen/ my_program.cpp -o my_program
Getting Started
#include <iostream> #include <Eigen/Dense> int main() { // 2行2列の行列作成 Eigen::Matrix2d m(2,2); m(0,0) = 3; m(1,0) = 2.5; m(0,1) = -1; m(1,1) = m(1,0) + m(0,1); std::cout << m << std::endl; // 1行2列のベクトル作成 Eigen::Vector2d v(1,2); std::cout << v << std::endl; // 上記行列とベクトルの積 std::cout << "m * v =" << std::endl << m * v << std::endl; }
出力
3 -1 2.5 1.5 1 2 m * v = 1 5.5
Dynamicに生成
以下のように記述することで行列サイズを動的に決めることができる
Eigen::MatrixXd m = MatrixXd::Random(3,3);
コンマで初期化
Matrix3f m; m << 1, 2, 3, 4, 5, 6, 7, 8, 9; std::cout << m;
便利機能まとめ
配列からEigenに変換
配列からEigenに変換するのに便利なEigen::Map
int array[8]; for(int i = 0; i < 8; ++i) array[i] = i; cout << "Column-major:\n" << Map<Matrix<int,2,4> >(array) << endl; cout << "Row-major:\n" << Map<Matrix<int,2,4,RowMajor> >(array) << endl;
出力
Column-major: 0 2 4 6 1 3 5 7 Row-major: 0 1 2 3 4 5 6 7
クオータニオン計算
参考なるブログ
所感
これは便利 ！ 使いやすいし、多機能
背中がITAI...
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問題を解けるように頑張る!
