kou6839の日記

c++ 競プロ(特にcsacademy)　linuxについて書きます。普段は自動車屋さんでナビ開発してます。転職先を探しています！！。

c++で違う型を返す

知らなかったんですが、
以下のように、クラスＢ型のコンストラクタにクラスＡ型を受け取るものを作っておくと、クラスB型を返す関数funcの戻り値をクラスA型にすることができます。
どういう目的でそうなったのかはわからないですが・・・。

class A {
public:
	int a;
	A(int a) :a(a) {}
};

class B {
public:
	int b;
	B(int b) : b(b) {}
	B(A AA) { b = AA.a;}
};

B Func() {
	A tmp(100);
	return tmp;
}

int main() {

	B b = Func();

	cout << b.b << endl; //100

	return 0;
}

Strictly Increasing Array

csacademy.com

＜問題＞
長さN( 0 \le N \le 10^6)の配列Vが与えられます。
「V_iを好きな値に書き換える」という操作を考えるとき、
そのような操作を最小で何回行うと、配列Vを単調増加列とすることができるか。

＜解説＞
全ての要素からindexを引き、（つまり{V_i := V_i - i} という操作を行う）
その配列で、最大非減少部分列 の長さを求めます。
そのような配列は元の配列で単調増加となっているので、N-(最大非減少部分列の長さ)で答えを求めることができます。
最大非減少部分列はいつもの、長さに対する末尾の値の最小値を二分探索で更新していきましょう。

＜コード＞

int b[1000005];
int main() {

	int n;
	cin >> n;
	vi a(n);
	rep(i, n)cin >> a[i];
	rep(i, n)a[i] -= i;

	
	rep(i, n)b[i] = INF;
	rep(i, n)*upper_bound(b, b + n, a[i]) = a[i];

	P(n-(find(b, b + n, INF) - b));

	return 0;
}

＜感想＞
解説の最大非減少部分列を求めるところが理解不能です。
このindexを引くテクしらなかったんですが、競プロ勢としては常識なんでしょうか・・・。

C++でのmain関数ラッパー方法

gdbserverを用いてリモートアタッチする際に、ラッパーmain関数内にてsleepを入れておき、
その際にアタッチする必要がありました。（sleepを入れておかないと、break pointより先にプロセスが進んでしまいます）

そこで
・元のmain関数が定義されているmain.cppには修正を加えない
という条件のもとで、そのようなラッパーmain関数を作成してみます。

結論から言うと、2つの方法があります。
（他にも方法があるかもしれません）

1つ目の方法

「main関数　ラッパー」などで検索すると、以下のページが見つかると思います。
qiita.com
マクロとincludeを用いた方法です。
これを実際にやってみます。

以下のようなmain.cppがあるとします。

//main.cpp
#include <stdio.h>

int main(){
  printf("main\n");
  return 0;
}

これをラップするwrapper_main1.cppを作成します。

//wrapper_main1.cpp
#include <stdio.h>

int original_main();

int main(){
  printf("wrapper_main1\n");
  original_main();
}

#define main original_main
#include "main.cpp"

実行すると、

-VirtualBox:~/test$ ./a.out 
wrapper_main1
main

のように、wrapper_main1→mainの順に呼ばれます。
wrapper_main1にsleepを入れておけば、目的が達成できます。

プリプロセッサ実行後をみると、

# 3 "wrapper_main1.cpp"
int original_main();

int main(){
  printf("wrapper_main1\n");
  original_main();
}


# 1 "main.cpp" 1


int original_main(){
  printf("main\n");
  return 0;
}
# 11 "wrapper_main1.cpp" 2

マクロとincludeで上手く元のmain関数をoriginal_mainに書き換え、実行していることがわかります。

2つ目の方法

(今回は主にこちらの方法を紹介する目的で記事を書きました。)
-Wl,--wrapオプションを使うことで、ラッパー関数を呼び出すことができます。

さきほどと同様に以下のmain関数をラップします。

//main.cpp
#include <stdio.h>

int main(){
  printf("main\n");
  return 0;
}

wrapper_main2.cppを作成します。

#include <stdio.h>

extern "C"{
int __real_main();
int __wrap_main(){
  printf("wrapper_main2\n");
  __real_main();

  return 0;
}
}

（手元の環境ではexternしないと_Z**が関数名にはいってしまい、うまくリンクできませんでした）

ビルドします。

-VirtualBox:~/test$ g++ -Wl,-wrap=main -o wrap2  main.cpp wrapper_main2.cpp

実行します。

-VirtualBox:~/test$ ./wrap2 
wrapper_main2
main

この -WL,-wrap=mainがポイントです。
-wrapオプションをリンカに渡すことで、

  • オリジナルのmain関数を呼ぶときは　__real_main()
  • ラッパーしたmain関数を呼ぶときは __wrap_main()

として、呼び出すことができます。
ややこしいですが、普通にmain()と呼ぶと__wrap_main()が、
__real_main()を呼ぶと普通のmain()が呼ばれます。

__wrap_main()内にsleep処理を入れておくことで、目的を達成することができます。




以上２つの方法を紹介しました。
どちらがどう良いか、を語るほどラッパー関数を使用していないのですが、
2つ目のほうが、余計なマクロや複雑なinclude処理をしないので簡単かなと思います。

Minimize Max Diff

＜問題＞
csacademy.com

長さNの非減少数列が与えられる。
このうちK個までの要素を削除することができ、削除後に隣り合う要素の差の最大値を最小にしたい。
そのときの最小値はいくらか。

＜解法＞
可能な値を2分探索します。
ここでxが取りうる値かどうかは、
元の数列のうち、隣り合う要素の差が全てx以下の連続する部分列の最大長をLとすると、
L \geq N-Kとなっているかどうかで判定できます。
単純に、K個取り除いた後に、条件を満たす数列が存在することを確かめればよいです。

＜コード＞

int n, k;
vi a;

bool ok(int mid) {
	int ml = 0;

	rep(i, n) {
		int tl = 0;
		while ( i + tl+1 < n && a[i + tl+1] - a[i + tl] <= mid ) tl++;
		ml = max(ml, tl+1);
		i += tl;
	}
	if (ml >= n - k)return true;
	else return false;
}
int main() {

	cin >> n >> k;
	a.resize(n);
	rep(i, n)cin >> a[i];

	int l = -1, r = 1e9 + 10;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (ok(mid))r = mid;
		else l = mid;
	}
	P(r);
	return 0;
}

＜感想＞
実は、K個削除する際、左からx個　右からK-x個削除することが最適であるとわかります。
（解説にも書いてある通り、数列の真ん中を削除しても、隣り合う数列の差は大きくなるだけです）
これをすべてのxについて試せばおｋなのですが、途中で出てくる候補の管理ができずに１時間半くらい溶かしてしまいました・・・。
その後ググって2分探索解法にたどり着きました。

CCNA取得しました。

正確にはICND2という名称です。

前回 6/16 にICND1 に合格していて、
ICND1(CCENT)に合格しました - kou6839の日記
１と２をとるとCCNA取得となります。
直接CCNAを取ることもできますが、その辺はホームページを見てください。


＜勉強方法＞
ping-t !
３回くらい銅→金を繰り返しました。


＜感想＞
正直落ちたと思っていました。
選択問題がping-tと全然ちがい3割くらいしかわかりませんでした。（合格ライン８割）
ただ、シミュレーション問題が解けたので、そのおかげだと思います。
シミュレーション問題自体は、選択肢に候補が乗っているので、それを確認していくだけでよく、
ospf,eigrpの場合のネイバー接続条件などは覚えていなくても大丈夫な気がしました。

＜次＞
とりあえずネスぺを申し込んだので、９月後半はそれで、
それまではawsソリューションアーキテクトとCCNPの勉強をします。

LPIC 304取得

本日LPIC 304に合格して、無事にLPIC level3取得・目標達成となりました。

前回
kou6839.hatenadiary.jp
level2取得してから２か月以上たってしまいました。
意外とサボっていたのか・・・。

得点一覧
2018/2/19 101 score 750

2018/3/4 102 score 740

2018/4/30 201 score 600

2018/5/13 202 score 680

2018/7/29 304 score 740

です。
ほとんどの問題が解けました。

＜勉強方法＞
黒本
Amazon CAPTCHA

覚えることはまぁまぁ多いですが、level2よりは全体的にコマンド・オプション暗記は少なく、運用のことがメインだった気がします。
試験問題は、黒本のまま・・・。

＜感想＞
LINUXの勉強を統括的にするのはいったん終了で、次は期限切れ（５年後）あたりになると思います。
IPAのエンベデッドシステムスペシャリストもとりましたが、IPAの試験よりは、LPIC CCNAなどのほうが実用的だと思いました。
やはり実務ではコマンド暗記も必要ですからね・・・。

次の目標は８月中にCCNA(ICDN2)をとって、AWS ソリューションアーキテクト→CCNPの順で進もうと思います。

ところで、このブログの真の目的であるCSAはなかなか面白い問題にあたらずに、記事作成がストップしてしまっています。。

CSAcademy Min Races

csacademy.com

＜問題＞
N人でレースを行います。
N人それぞれクラスA_iと全員でレースした際の順位B_i ( 0 \leq i \leq N-1)が与えられます。
何回かレースを行って、N人すべてが最低１回ずつ勝利するようにします。
各レースではN人の中から、出場選手を自由に選ぶことができます。
各レースで、自分より早い人のクラスが、自分のクラスよりも小さければ勝利となります。
( つまり、勝利する選手をiとすると、全てのB_j \lt B_iとなるjについて、A_j \lt A_i　となってればよい )
レース回数を最小にするとき、いくらになるか。

＜解説＞
Aさんが勝利する際は、条件より、自分より早い人のクラスが自分よりちいさければいいです。
また、１度のレースで勝者をできるだけ多くだすためには、(クラス・順位)のペアを昇順にできるだけ多く並べればよいです。

そのためには、順位でソートしたあとに、クラスが狭義単調増加になるように、部分列を最小限に作ればよいです。
これまで作った部分列の最大の値を持っておいて、
①それらよりも小さい場合は、新しい部分列を作る
②そうでない場合は、できるだけ大きいものの後ろにつける
という操作を、部分列の最後の値（最後尾）だけを持って計算します。
部分列の数が答えになります。
(以下のコードで、dequeでなくvectorでやると、①の操作が遅いためTLEしました）

＜コード＞

int main() {

	int n, m;
	cin >> n >> m;
	vector<pii> v;

	rep(i, n) {
		int a, b;
		cin >> a >> b;
		v.pb({ b,a });
	}
	SORT(v);

	deque<int> l;
	rep(i, n) {
		if (i == 0) {
			l.pb(v[i].second);
			continue;
		}
		auto index = lower_bound(ALL(l), v[i].second);
		if (index == l.begin()) {
			l.push_front(v[i].second);
		}
		else {
			l[index-l.begin() - 1] = v[i].second;
		}
	}
	P(l.size());
	return 0;
}

＜感想＞
問題文と解説が難しかった・・・