ABC167復習

ABC167

ABC167の復習です。解説動画見ながらやっていました。

今回もC問題で躓きました。やりながら「経験値が足りねえ～～」ってなっていたので、頑張って経験値を貯めます。

1.A問題

よゆーと思ってたら30秒ぐらいフリーズした問題です。こういうところが経験値が足りない所以。

やることは単純で、２つの文字列を取って1文字目から比較するだけ。if分とfor文が書ければ解ける。

私は一瞬「find())使うのか？」となりました。substr()も使わなきゃ・・・。

2.B問題

if文が書ければ解けますが、max()を使えばもっと楽に解けたらしい。

3.C問題

私がつまずいた問題です。

ぱっと見てナップサック問題と思った私が悪かった。もっと単純。多分中学生で場合の数やった子なら方針立てれるんじゃないかなってぐらい単純。実装はちょっと工夫がいるようです。

まず、 $N$ と $M$ が高々12というところで違和感を感じます。つまり、全部の通りを計算させたとしても5000通りにも満たないわけです。なので、全部列挙して最小の値採用でよくね？って考えました。ここまではよかった。

次に、"可能な場合は最小値を出力"を見て、なにか有名なアルゴリズムを使うなと思いました。これがいけなかった。

そういうことで私自身の反省終わり。

方針

こういう問題は数が少ないパターンなら中学校でやったはずです。少し応用問題で、10円玉、100円玉、500円玉を使ってどうこう・・・みたいな問題のほうが近い気がします。

何が言いたいかというと、樹形図が書けるということです。使うなら○、使わないなら☓で最初からバーっと書くと樹形図が完成します。あとは、その樹形図の枝ごとに目標に達成できるか判定し、できるなら金額を算出します。

最後に、それぞれの枝から算出された金額の最小値を出せば解けます。

コード

	#include <algorithm>
	#include <iostream>
	#include <vector>
	#define rep(i, n) for (int i = 0; i < (n); i++)
	using namespace std;
	using ll = long long;
	const int INF = 1001001001;

	int a[12][12];

	int main(int argc, char const *argv[]) {
	//入力
	int n, m, x;
	cin >> n >> m >> x;
	vector<int> c(n);
	rep(i, n) {
	cin >> c[i];
	rep(j, m) cin >> a[i][j];
	}

	int ans = INF; //最小値を求めるので、答えを最大化する
	rep(s, 1 << n) { // s=0...0~1...1まで(2進数表示)
	int cost = 0; //各パターンにおけるコスト
	vector<int> d(m); //各パターンにおけるそれぞれの理解度
	rep(i, n) {
	if (s >> i &1) { //ビットが立っているか判定。iビットシフトし1とANDをすると、最下位ビットに1が立ってるかわかる。
	cost += c[i];
	rep(j, m) d[j] += a[i][j];
	}
	}
	//全て目標値に達しているかと答えの更新
	bool flag = true;
	rep(j, m) if (d[j] < x) flag = false; //達していない時flagをfalseにする
	if (flag)
	ans = min(ans, cost); //達している時ansとcostを比較しansを更新する
	}
	//出力
	if (ans == INF)
	cout << -1 << endl;
	else
	cout << ans << endl;
	return 0;
	}

view raw ABC167c.cpp hosted with

by GitHub

コードはABC167解説動画を見ながら書きました。

新しく知ったことなど

1.repマクロは便利

今までrepマクロは使ったことがなかったのですが、解説動画見てると便利そうなので今度から使おうかなと思ったり。それと、なぜnに括弧がついてるの？と思いましたが、結合順位でバグる可能性があるかららしいです。

競プロのrepマクロで、括弧が使われている理由

2.ビット演算

    rep(s, 1 << n) {  // s=0...0~1...1まで(2進数表示)
Copy

これは樹形図でいう、使う場合を1、使わない場合を0としたときの状態を全数列挙する部分です。

repマクロは、n=3ならば000から111までを列挙してくれます。

f (s >> i & 1)
Copy

sの最下位ビットに1が立っているか確認する部分です。これで確認できる理由は次のとおりです。

sをiビット右シフトさせると、知りたいbitを最下位ビットに持ってくることができる
そこに1(0x01)をANDする(ANDはお互いのbitが1なら1、それ以外なら0になる)
最下位bitが1ならばANDされて1になる。そうじゃないならば0になる

聞けばなるほどなってなりますが・・・一応暗号系の研究室所属なのに、bit演算できないは流石にやばい気がしてる。

忘れていたこと

最小値や最大値を出す時、暫定的な答えと計算してきた答えを比較して、逐次更新するという方法。昔は何もせずに書けてたのに、今は・・・。

余談

bti演算を調べていたらbitsetにたどり着きました。その中のcountでなるほどなとなったのが、「値が2の乗数か判定する」ということです。bitsetのcountはその名の通り立ってるbitをカウントするものですが、値を2進数に変換して、全てのbitが立っていれば2の乗数であることがわかる。なるほどなとなりました。

bit演算を知らなければ、for文で値を2で割り続け、割れなくなった時に余りが0ならOK、それ以外ならダメって実装しそうですが、ビット列を扱えればもっと簡単にできるようです。

4.D問題

テレポーターでテレポートし続け、最終的な場所を出力せよという問題。移動回数が $10^{18}$ 回なのでまともにやると、おねえさんロボになります。

解説では２つの解法を説明してくれていました。

1.周期を考える

制約条件を見ると $N$ が高々 $2 \times 10^5$ なのに対し、移動回数 $X$ は最高で $10^{18}$ です。これからわかることは、道筋は多分ループしているところがあるだろうということ。( $N \leq X$ の場合はない場合がありますが)

そういうことで、その周期を求めてやればいいだろうということです。

コード

	#include <iostream>
	#include <vector>
	#define rep(i, n) for (int i = 0; i < n; i++)
	using namespace std;
	using ll = long long;

	int main(int argc, char const *argv[]) {
	//入力
	int n;
	ll k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i, n) cin >> a[i];

	//道筋と訪問済み
	vector<int> s; //道筋作成
	vector<int> o(n + 1, -1); //訪問済みかどうか。最初は全て-1で初期化
	int c = 1, l = 0; // cは周期の長さ、lは周期外の長さ

	// solver
	int v = 1; //現在訪問しているノード
	while (o[v] == -1) { //-1以外になったら訪問済み
	o[v] = s.size(); //一度訪問したノードにsのサイズを入れる
	s.push_back(v); //訪問順に入れていく
	v = a[v - 1]; //次訪問するノードを代入
	}
	c = s.size() - o[v]; //周期長を計算
	l = o[v]; //周期外の長さ

	//出力
	if (k < l)
	cout << s[k] << endl;
	else {
	k -= l;
	k %= c;
	cout << s[l + k] << endl;
	}
	return 0;
	}

view raw ABC167d.cpp hosted with

by GitHub

新しく知ったこと

vectorの初期化

vector<int> o(n + 1, -1);
Copy

このように書くと、全て-1で初期化されるらしい。

2.ダブリング

別解として紹介された手法。うまいこと作った表を使って最終的な場所を割り出す方法です。

例えば、1→4→2→3→5→2→・・・(2→3→5はループしてる)となる道筋があったとします。ここから、ある場所を始点としてn回辿った先を記述する表を作ります。また、辿った回数は上の数の2倍になるようにします。

辿った回数\始点	1	2	3	4	5
1	4	3	5	2	2
2	2	5	2	3	3
4	5	3	5	2	2

この表は一つ上の段を見ると下の段が書けるようになっています。例えば1から4回辿った場合、1→(2回辿る)→2→(2回辿る)→5というふうに出せます。これを必要な分だけ作ります。

あともう一つ必要なのが、 $X$ を2進数にします。そうすると、表の辿った回数と対応させることができるからです。例えば、 $X=5$ だと、 $101_{(2)}$ となります。これにより、 $X=2^2+2^0$ ということがわかるので、1が最初の位置だとすれば表より、1→(4回辿る)→5→(1回辿る)→2というように最後の場所が割り出せます。

ダブリング自体はいろいろな場所で使えるらしいので覚えておこうとおもいました。

コード

	#include <iostream>
	#include <vector>
	#define rep(i, n) for (int i = 0; i < n; i++)
	using namespace std;
	using ll = long long;

	const int D = 60;
	const int MAX_N = 200005; //頂点番号
	int to[D][MAX_N];

	int main(int argc, char const *argv[]) {
	//入力
	int n;
	ll k;
	cin >> n >> k;
	rep(i, n) {
	cin >> to[0][i];
	to[0][i]--;
	}

	rep(i, D - 1) rep(j, n) to[i + 1][j] = to[i][to[i][j]]; //表の作成

	int v = 0;
	for (int i = D - 1; i >= 0; i--) {
	ll l = 1ll << i; // llはオーバーフロー対策。つけないとintで計算される。
	if (l <= k) {
	v = to[i][v];
	k -= l;
	}
	}
	cout << v + 1 << endl;
	return 0;
	}

view raw ABC167d_2.cpp hosted with

by GitHub

to[i][j]ですが、これはjから $2^i$ 先のノードを表します。これによって表ができていきます。一つ上の段を見れば次の段が書けるというのは、

to[i + 1][j] = to[i][to[i][j]]
Copy

で表されています。

5.E問題

数学の問題です。5つとかで実験してみると、各 $K$ に対するパターンというのは一つの数式であらわせることがわかります。色の割り当て方は $M \times (M-1)^{N-X-1}$ 通り、グループの分け方は ${}_{n-1} {C}_x$ 通りになります。

コード

	#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>;

	// auto mod int
	// https://youtu.be/L8grWxBlIZ4?t=9858
	// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
	// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
	const int mod = 998244353;
	struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) : x((x % mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint &operator+=(const mint a) {
	if ((x += a.x) >= mod) x -= mod;
	return *this;
	}
	mint &operator-=(const mint a) {
	if ((x += mod - a.x) >= mod) x -= mod;
	return *this;
	}
	mint &operator*=(const mint a) {
	(x *= a.x) %= mod;
	return *this;
	}
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator(const mint a) const { return mint(this) *= a; }
	mint pow(ll t) const {
	if (!t) return 1;
	mint a = pow(t >> 1);
	a *= a;
	if (t & 1) a = this;
	return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint &operator/=(const mint a) { return this = a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
	};
	istream &operator>>(istream &is, const mint &a) {
	return is >> a.x;
	}
	ostream &operator<<(ostream &os, const mint &a) {
	return os << a.x;
	}

	// combination mod prime
	// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
	struct combination {
	vector<mint> fact, ifact;
	combination(int n) : fact(n + 1), ifact(n + 1) {
	assert(n < mod);
	fact[0] = 1;
	for (int i = 1; i <= n; ++i)
	fact[i] = fact[i - 1] * i;
	ifact[n] = fact[n].inv();
	for (int i = n; i >= 1; --i)
	ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
	if (k < 0 \|\| k > n) return 0;
	return fact[n] * ifact[k] * ifact[n - k];
	}
	} c(200005);

	int main(int argc, char const *argv[]) {
	int n, m, k;
	cin >> n >> m >> k;

	mint ans = 0;
	mint col = m;
	for (int x = n - 1; x >= 0; --x) {
	mint now = col;
	now *= c(n - 1, x);
	if (x <= k) ans += now;
	col *= m - 1;
	}
	cout << ans << endl;
	return 0;
	}

view raw ABC167e.cpp hosted with

by GitHub

なんか難しいこと書いてありますが、Atcoderのライブラリを使っています。すごいねこれ。

新しく知ったこと

1.mod 素数

mod = 998244353の値を出力せよと言われています。FFT(高速フーリエ変換)というアルゴリズムを使うらしい。

$\frac{a}{b}$ というのがあったとき、 $a\times \frac{1}{b}$ として計算するといいらしい。この時、フェルマーの小定理 $x^{p-1}\equiv 1 \pmod{p}$ と

いうものを利用します。両辺を $x$ で割って $\frac{x^{p-1}}{x}\equiv\frac{1}{x}\pmod{p}$ より、 $x^{p-2}\equiv\frac{1}{x} \pmod{p}$ となります。これを利用して逆元を求めると早いらしい。

2.繰り返し二乗法

$x^{13}$ を求めると、 $x$ を13回掛けることになります。これを $x^{13}={x^6}^2\cdot x$ 、 $x^6={x^3}^2$ というようにやれば計算回数を抑えられます。

6.F問題

括弧列というよくある問題らしいです。このような問題のときは折れ線にするといいらしい。

方針

'('を+1、')'を-1とします。そして各断片をいくつ下るかと増減という2つの情報にします。

解説で挙げてた具体例を使うと、"( ( )"、") ( ( ("、") ) ( ) )"という断片が与えられたとします。これはこの順番に並べると正しい括弧列になるのですが、それぞれを+1と-1にして折れ線にすると次のようになります。

そして、次のように2つの情報を定義します。

2つの情報を(いくつ下る,増減)というように表せば、先程の断片は(0,1)、(-1,2)、(-3,-3)となります。

次にこの情報を用いて断片を2種類に分けます。どうするかと言うと、増減は高ければ高いほどいいので、増減が正か負かで分類します。

そうすると、断片の結合順番は先に増減が正のものを繋げ、後で増減が負になるものを繋げばいいことがわかります。

ところで、正しい括弧列の条件は

0で終わる(増減の総和が0)
どの部分も0未満にならない

というものです。

さて、先に増減が正のものを繋げますが、正しい括弧列の条件の2番目から、変に繋げると正しくなりません。

そのため、

増減が正にものはすぐに繋げて良い
最下点(いくつ下るか)が高い順に繋げると良い

ということが言えます。

次に、増減が負のものについて考えますが、これは右側から繋げていくと考えやすくなるらしいです。

つまり、増減が負のものに関しては、右側から見た時の、(いくつ下る,増減)を出すと、増減が正の場合と同じように考えることができます。

コード

	#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>;

	bool check(vector<P> s) {
	int h = 0;
	for (P p : s) {
	int b = h + p.first; //断片の最後の点の高さを出す
	h += p.second; //増減は加算していくだけ
	if (b < 0) return false; //最下点が0を下回ったらfalse
	}
	return true;
	}

	int main(int argc, char const *argv[]) {
	int n;
	cin >> n;
	vector<P> ls, rs; //増減+はls、増減-はrsに入れる
	int total = 0; //和が0にならないとダメなので、その確認用
	rep(i, n) {
	//入力
	string s;
	cin >> s;
	//最下点と増減を計算
	int h = 0, b = 0;
	for (char c : s) {
	if (c == '(')
	++h;
	else
	--h;
	b = min(b, h);
	}
	//増減の正負で分類
	if (h > 0)
	ls.emplace_back(b, h);
	else
	rs.emplace_back(b - h, -h);
	total += h;
	}
	// sort
	sort(ls.rbegin(), ls.rend());
	sort(rs.rbegin(), rs.rend());
	// checkする
	if (check(ls) && check(rs) && total == 0) {
	cout << "Yes" << endl;
	} else {
	cout << "No" << endl;
	}
	return 0;
	}

view raw ABC167f.cpp hosted with

by GitHub

新しく知ったこと

1.<bits/stdc++.h>

競プロだと使っている人が多い印象です。競プロ以外だと使わないほうが良いらしいですが。これなんですが、MinGWで入れたgccならそのまま使えます。

2.emplace_back

ぶっちゃけpush_backみたいなものっぽい？しかしぐぐると、emplace_back vs push_backの記事がいっぱい出てきて、なんじゃこりゃってなっています。パフォーマンス的にはemplace_backのほうが無駄がないっぽいですが・・・。

3.rbegin,rend

今回は大きい順にsortするので使ってるようです。これらは、末尾を指すイテレータが返ってきます。コンテナ内を逆向きに走査するときとかに使うらしい。

そういえば、sortならgreater<Type>()使えば降順sortできたなあと思い出しました。

どっち使ってもいいっぽいですが、コードの書きやすさ的にrbegin,rendを使うほうが良さそう。すでに速さの差もないらしい。

4.範囲for

for (char c : s)
Copy

とか書かれている部分です。

for ( for-range-declaration : for-range-initializer ) statement
Copy
for-range-declarationには変数宣言を書く。ここで宣言した変数に範囲内の要素が先頭から終端まで順番に代入される。 for-range-initializerにはfor文が処理すべき範囲を表す値を書く。

こういう書き方ができるらしい。なんかPythonのfor文みたいですね。

7.おわりに

解説聞くとなるほどなあ～ってなるのですが、コンテスト中はなんじゃこれ！？ってテンパってるクソ雑魚なので、過去問やりつつ勉強したいと思います。

まずはサボってた期間のA,B問題埋めかな。終わったらC問題埋めます。

8.参考文献

AtCoder Beginner Contest 167解説動画

C++日本語リファレンス std::bitset::count

とづんのブログビット演算「特定ビットを判定する

C++日本語リファレンス std::vector::コンストラクタ

atcoder-live/library

C++日本語リファレンス std::vector::emplace_back

とにかくあぶなくないRiskのブログ降順のソート方法

C++日本語リファレンス範囲for文

ABC115C解けた

暇すぎたので久しぶりに問題解いてました。久しぶりにやりすぎたせいで、vectorの宣言とか忘れてて、…

2018年12月31日

atcoder

ABC171振り返り

ABC171参加してました。今回は43分で4完できたのでめっちゃ喜んでいました。パフォーマンスも上が…

2020年6月22日

atcoder

ABC166メモと復習

abc166 とても久しぶりにABCに参加しました。1年ぶりです。そのため、ひっっどいミスをしました…

2020年5月4日

atcoder

1.A問題

2.B問題

3.C問題

方針

コード

新しく知ったことなど

1.repマクロは便利

2.ビット演算

忘れていたこと

余談

4.D問題

1.周期を考える

コード

新しく知ったこと

vectorの初期化

2.ダブリング

コード

5.E問題

コード

新しく知ったこと

1.mod 素数

2.繰り返し二乗法

6.F問題

方針

コード

新しく知ったこと

1.<bits/stdc++.h>

2.emplace_back

3.rbegin,rend

4.範囲for

7.おわりに

8.参考文献

関連記事

ABC115C解けた

ABC171振り返り

ABC166メモと復習

コメントを残すコメントをキャンセル

1.A問題

2.B問題

3.C問題

方針

コード

新しく知ったことなど

1.repマクロは便利

2.ビット演算

忘れていたこと

余談

4.D問題

1.周期を考える

コード

新しく知ったこと

vectorの初期化

2.ダブリング

コード

5.E問題

コード

新しく知ったこと

1.mod 素数

2.繰り返し二乗法

6.F問題

方針

コード

新しく知ったこと

1.<bits/stdc++.h>

2.emplace_back

3.rbegin,rend

4.範囲for

7.おわりに

8.参考文献

関連記事

ABC115C解けた

ABC171振り返り

ABC166メモと復習

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル