cplusplusonly's memo

Atcoder: https://atcoder.jp/users/cplusplusonly

AtCoder ABC124 参戦記

競技プログラミング プログラミング

AtCoder の ABC124

atcoder.jp

に参戦しました。

水色になってレート対象外になってから最初の ABC。

  • D 問題をへぐらいない
  • 可能な限り早解きする

を目標にしていました。

12 分で C まで完了 -> 37 分で D まで完了と調子よく解けて 233 位でした。前回より早かったものの全体的に簡単だったのか順位は落ちました。パフォーマンス自体は 1600 以上あるので、これなら次回の Tenka1 Programmer Contest 2019 (ARC) で緑色に落ちてもすぐに水色に復帰できそうです。

感想

A 問題

A 問題にしては複雑。最適手順を考えるの面倒だったので大きいほうから得点を取るコードを 2 回書いた。

B 問題

2 重ループで実装。ただし手元でバグを出して若干の時間ロスをした。

C 問題

少し手元で紙に書いてみて "101010..." か "010101..." のどちらかとなるのに気が付いた。あとは実装するのみ。

D 問題

少々の考察ののちに "0...0" のブロックを連続して裏返せば OK ということに気が付く。
あとはどこからどこまでを裏返すかだが、頭から読み込んでしゃくとり法でよいのでその方針で実装した。
対象区間を記録していく (対象外になったところでパージ) しゃくとり法を実装したが、

  • "1...1" の扱い
  • 最後の区間の扱い

あたりで実装に苦労した。

一晩たって

のツイートを見て対象外区間長を記録する方針でしゃくとり法を実装すれば実装が楽になることに気が付いた。

G++ オプション

備忘録 プログラミング

G++ オプションどうしていいかわからなくなりやすいので記録しておく。

Release
  • std=c++11 -O3 -Wall -Wextra -Wpointer-arith -Wcast-align -Woverlength-strings -Wunreachable-code -Wno-missing-field-initializers -Wno-format-zero-length -Werror -DNDEBUG
Debug
  • O0 -g -Wall -Wextra -Wpointer-arith -Wcast-align -Woverlength-strings -Wunreachable-code -Wno-missing-field-initializers -Wno-format-zero-length -Werror -D_DEBUG -fsanitize=address

AtCoder ABC123 参戦記

競技プログラミング

AtCoder の ABC123

atcoder.jp

に参戦しました。

過去にないほどさくさくと解けていき順位は 89 位! パフォーマンス 1600 で水色になりました。
AtCoder 始めるときに「自分はたぶん水色やろうな」と思っていて到達できたのでうれしいです。これからも精進して青色目指します。(次の ARC でへぐって緑色に叩き落されそうですが...)

f:id:y_r:20190406230440p:plain

感想

A 問題

問題文が長い。「隣り合うアンテナが通信できないとき」と誤読していて WA 叩き出しかけた。危ない...

B 問題

sum(xi/10*10) - 10 + min(xi(mod 10)) で楽勝だろ! と思ったら手元で WA 出した。実際は時間が 10 の倍数になっている料理は最後に注文してはいけないのです。危ない...しかし...

C 問題

明らかに律速するのは一番キャパシティーが少ない工程だから max(n/xi)+ 5 で楽勝...と思いきや WA。よく考えると割り切れるときは次の便を出さなくてよい。
これは B 問題で出したバグと同じ原因だった...

D 問題

最初は A, B, C についてソートして大きい数からとっていけばよい？と思っていたが明らかにめんどくさい。というか机上ですらよくわからない。
方針を変更して (A+B+C) を全部用意して大きいほうからとっていくことにする。これは最大 10^9 通りだが、 (A + B) をとったところで大きいほうから K 個以外は捨ててよいので最大計算量は (A + B) : 1000*1000, (A+B+C) : 1000*1000 + 3000*1000 で間に合うはず。
実装中いくらかバグを埋め込んでデバッグに追われたがこの方針で AC。
類題はけんちょんさんの AtCoder 版！蟻本 (初級編) - Qiita 冒頭にあった JOI 本線 C ダーツ。これを解いてなかったら (自力では LTE が取れなかったので解説 AC) 発想できなかったと思う。

解説を見ると解法がいろいろある模様。(自分の解法は一番計算量が多い)。ひとつひとつについて理解しておきたい。

結論

割り算とか、剰余を取るときは割り切れるときがコーナーケースになりやすい。仕事でも何回かこれでバグ出している。

剰余上での割り算は累乗のほうが GCD より 1000 倍ぐらい早い

プログラミング 競技プログラミング

剰余上での割り算

競技プログラミングをやっていると、ときどき剰余上での割り算を行う必要が出てきます。
例えば エクサウィザーズ 2019 E - Black or White では xz=y (mod (10^9+7)) となる z を出力する必要があります。

このとき z は mod (10^9+7) 上で y/x を実行した値となり、この値は inv(x) を mod (10^9+7) 上での x の逆元とすると y*inv(x) (mod (10^9+7)) です。つまり剰余上での割り算を行うには逆元をかける必要があるので、逆元を高速に計算する方法が求められます。

剰余上での逆元の計算手法

剰余上での逆元を求めるには以下の 2 種類の方法があります。それぞれ制限がありますが、競技プログラミングでは素数での剰余以外を考える必要がないはずなので、どちらの方法でも正しく逆元が求まります。

最小公倍数 (GCD) で求める

(a, b) について GCD を計算すると r = ai + bj となる (r, i, j) が得られます。 (p, x) が互いに素であるとき、 x の p の剰余上での逆元を求めるには、GCD を計算して、 r=1 から 1 = pi + xj となり、 pi (mod(p))=0 なので xj(mod(p))=1 で j が求める逆元となります。

コードは以下の通りです。

tuple<int64_t, int64_t, int64_t> gcd(int64_t x, int64_t y)
{
	if (y == 0) return make_tuple(x, 1, 0);

	tuple<int64_t, int64_t, int64_t> ret = gcd(y, x % y);

	return make_tuple(get<0>(ret), get<2>(ret), get<1>(ret) - (x / y)*get<2>(ret));
}

int64_t gcd_remdiv(int64_t val, int64_t rem)
{
	int64_t ret = get<2>(gcd(rem, val));
	while (ret < 0) ret += rem;

	return ret;
}
フェルマーの小定理を使って累乗で求める

フェルマーの小定理より p が素数のとき、すべての x (x < p) について x^{p-1} (mod(p)) = 1 となるので　 x*x^{p-2} (mod(p)) = 1 より x^{p-2} (mod(p)) が逆元になります。これは累乗を O(log(p)) で計算するアルゴリズムより高速に求まります。

コードは以下の通りです。

int64_t pow_rem(int64_t val, int64_t mul, int64_t rem)
{
	if (mul == 1) return val;

	int64_t ret = pow_rem(val, mul / 2, rem);
	ret *= ret;
	ret %= rem;

	if (mul & 1) {
		ret *= val;
		ret %= rem;
	}

	return ret;
}

int64_t pow_remdiv(int64_t val, int64_t rem)
{
	return pow_rem(val, rem - 2, rem);
}

逆元の計算手法の計算時間

ここで問題となるのは GCD と 累乗のどちらが早いかですが、ランダムな値に対して 10^9 + 7 の剰余上での逆元を求める計算を 1000万回繰り返すテストをしてみたところ、計算時間は以下のようになりました。(Visual Studio 2018 にて最適化オプション O4 付きでビルド)
GCD は値によって計算時間がかわるのですが累乗に比べて 1000 倍ぐらい遅く、剰余上での割り算の計算は累乗による計算を使うほうが圧倒的に高速のようです。

GCD 累乗
1500 msec - 2500 msec 2 msec


実験コードは以下になります。

#include <iostream>
#include <tuple>
#include <random>
#include <chrono>
#include <ctime>
#include <cstdint>

using namespace std;

tuple<int64_t, int64_t, int64_t> gcd(int64_t x, int64_t y)
{
	if (y == 0) return make_tuple(x, 1, 0);

	tuple<int64_t, int64_t, int64_t> ret = gcd(y, x % y);

	return make_tuple(get<0>(ret), get<2>(ret), get<1>(ret) - (x / y)*get<2>(ret));
}

int64_t gcd_remdiv(int64_t val, int64_t rem)
{
	int64_t ret = get<2>(gcd(rem, val));
	while (ret < 0) ret += rem;

	return ret;
}

int64_t pow_rem(int64_t val, int64_t mul, int64_t rem)
{
	if (mul == 1) return val;

	int64_t ret = pow_rem(val, mul / 2, rem);
	ret *= ret;
	ret %= rem;

	if (mul & 1) {
		ret *= val;
		ret %= rem;
	}

	return ret;
}

int64_t pow_remdiv(int64_t val, int64_t rem)
{
	return pow_rem(val, rem - 2, rem);
}

int main()
{
	int64_t rem = 1000000007;

	mt19937 mt;
	mt.seed(time(nullptr));

	int64_t ret = 1;

	for (int i = 0; i < 10000; i++) {
		uint32_t val = mt();
		if (rem <= val || val == 0) {
			i--;
			continue;
		}

		if (pow_remdiv(val, rem) * val % rem != 1) {
			cerr << "error" << endl;
		}
		if (gcd_remdiv(val, rem) * val % rem != 1) {
			cerr << "error" << endl;
		}

		auto start = chrono::high_resolution_clock::now();
		
		for (int j = 0; j < 10000000; j++) {
			ret += pow_remdiv(val, rem);
		}

		auto end = chrono::high_resolution_clock::now();
		auto dur_pow = end - start;

		start = chrono::high_resolution_clock::now();

		for (int j = 0; j < 10000000; j++) {
			ret += gcd_remdiv(val, rem);
		}

		end = chrono::high_resolution_clock::now();
		auto dur_gcd = end - start;

		auto pow_msec = chrono::duration_cast<chrono::milliseconds>(dur_pow).count();
		auto gcd_msec = chrono::duration_cast<chrono::milliseconds>(dur_gcd).count();

		cout << "pow msec : " << pow_msec << " gcd msec : " << gcd_msec << endl;
	}

	return ret;
}

AtCoder エクサウィザーズ 2019 参戦記

競技プログラミング

AtCoder の エクサウィザーズ 2019

atcoder.jp


に参戦しました。結果は AB 2 完の パフォーマンス 1035。レーティングもはじめて下がりました。
C-D-E をどれか解く or AB とても早解きで水色でしたがかなわず...次の ABC で水色を狙います。(パフォーマンスほぼ 1600 が必要ですが)

f:id:y_r:20190401234304p:plain

感想

AB 問題

瞬殺したつもりだったが瞬殺度が足りなかったらしい。

C 問題

最適解の 2 分探索は思い浮かばず。後ろからたどればよい？と考えたが左に落ちるのをカウントするときに左に行くやつしか考慮に入れなかったため当然のように WA。
コンテスト後解説 AC した。

D 問題

C 問題から浮気したが残り 30 分ではなにもできず。コンテスト後 2 時間以上かけても解けず、解説 AC した。

E 問題

コンテスト後自力で AC した。mod の計算にちょっと強くなった気がする。

MASKED AtCoder 版！蟻本 (初級編) : 2019/03/16 現在

競技プログラミング

けんちょんさんの AtCoder 版！蟻本

はありがたい記事なのですが、例題を解くには題意が分かる分難易度が下がってしまうので、最初は自力で解いてみたい人間は例題以外を見なかったことにする必要があります。記事を読むと例題のテーマとかキーワードとかは目に入ってしまうので、それを避けるために例題だけのリストを作成しました。
見出しにのっているのが例題、本文に列挙されているが類題となります。回答のヒントになりそうな語句は "XXXXXX" でマスクされています。注意として、元記事へのリンクをマウスオーバーしちゃうと、URI に書いてあるキーワードが見えてしまうので解けるまでリンクをマウスオーバーしないようお願いします。

1.6: ウォーミングアップ

例題 1-6-1

例題 1-6-2: 1852 -- Ants

2. 基礎からスタート！ - 初級編

2-1: XXXXXX

例題 2-1-1: XXXXXX
例題 2-1-2 2386 -- Lake Counting
例題 2-1-3: XXXXXX
例題 2-1-4: XXXXXX

2-2: XXXXXX

例題 2-2-1: XXXXXX
例題 2-2-2: XXXXXX
例題 2-2-3 3617 -- Best Cow Line
例題 2-2-4 3069 -- Saruman's Army
例題 2-2-5 3253 -- Fence Repair

2-3: XXXXXX

例題 2-3-1: XXXXXX
例題 2-3-2: XXXXXX
例題 2-3-3: XXXXXX
例題 2-3-4: XXXXXX
例題 2-3-5: XXXXXX
例題 2-3-6: XXXXXX
例題 2-3-7: XXXXXX
例題 2-3-8: XXXXXX
例題 2-3-9: XXXXXX
例題 2-3-10: XXXXXX
例題 2-3-11: XXXXXX
例題 2-3-12: XXXXXX
例題 2-3-13: XXXXXX
例題 2-3-14: XXXXXX
例題 2-3-15: XXXXXX
例題 2-3-16: XXXXXX
例題 2-3-17: XXXXXX
例題 2-3-18: XXXXXX

2-4: XXXXXX

例題 2-4-1 2431 -- Expedition
例題 2-4-2: XXXXXX
例題 2-4-3 1182 -- 食物链

2-5: XXXXXX

2-5-1: XXXXXX
例題 2-5-2 3255 -- Roadblocks
例題 2-5-3 3723 -- Conscription
例題 2-5-4 3169 -- Layout
例題 2-5-5

2-6: XXXXXX

例題 2-6-1: XXXXXX
例題 2-6-2: XXXXXX
例題 2-6-3: XXXXXX
例題 2-6-4: XXXXXX
例題 2-6-5: XXXXXX
例題 2-6-6 UVa Online Judge