2019-01-14

Double Landscape -AtCoder KEYENCE Programming Contest 2019 / キーエンスプログラミングコンテスト 2019 D-

解説

500点です。
問題リンクを貼っておきます。
D - Double Landscape

簡潔な解説は公式のものがわかりやすいので、ここには冗長な思考過程を書いていこうと思います。

考察の流れ

テストケースがややこしいやつと貧弱なやつしかないので、手元で手頃なやつを生成します。
f:id:hewla:20190113235812j:plain
とりあえず手元で考えてみようということで、こんな図を描きました。
丸で囲まれた数字は、そのマスにこの数字が入ることが確定していることを表します。
細長い丸とその脇に書かれた小さい数字は、この数字の入るマスの候補はこの範囲だということを示しています。

もしかして、この細長い丸はお互いに重複することがないのではないか？と考えます。
ここで落ち着いて、細長い丸を描くときのルールを考えてみます。
上側に並んでいる数字をa[i]、左側に並んでいる数字をb[j]とすると、 f:id:hewla:20190114000927j:plain
(i, j)のマスは
a[i] < b[j]の場合は縦に細長い丸に、
a[i] > b[j]の場合は横の細長い丸に入る可能性があるようです。

すると、a[i] < b[j]とa[i] > b[j]は同時に成立しないので、一つのマスは縦横の丸に重複して含まれることがありません。これでだいぶ考えるのが楽になりました。重複していると、その重複しているマスに数字が入る場合/入らない場合についてそれぞれ考えなければいけないので、ややこしくなってしまう気がします。
また、わかりやすいように上と横に並んでいる数字をソートしても答えは変わらないようです。

f:id:hewla:20190114001402j:plain
細長い丸は見にくいので細長い棒になりました。
わかりやすくなってきました。

ややこしかった入出力例4もExcelに突っ込んで図を描いてもらいましょう。
ちょっとだけ線の引き方のルールが変わっちゃてますが気にしないでください。先ほどは位置が確定した行/列には空白のマスがありましたが今回は気にしていません。
f:id:hewla:20190114001723p:plain
こうなると線の引かれ方のルールもかなりわかりやすいですね。
先ほど式で表したルールを考えるとこのようになるのは当然なのですが、僕は図にしないとやっぱりピンとこないなと思いました。

この図を見ながら考えます。
グリッドを1からN*Mの数字で重複がないように埋めていくわけですが、この数字は3つのグループに分けることができます。

縦横どちらにも数字が載っているので、入るマスが決まるもの
縦横のどちらかに数字が載っているので、入る行/列が決まるもの
縦横のどちらにも数字が載っていないので、各行/列の最大値を超えない範囲でどこにも入れるもの

です。

大きい数字は入るマスが決まりやすそうなので、大きい数字から順番に考えていきます。
答えを格納する変数ansを1で初期化して用意しておきます。

182や179などはグループ1に属します。これらは位置が確定しているので、ansの値は変わりません。

177はグループ2です。入る行が確定しています。
f:id:hewla:20190114002705p:plain
この写真で青く囲った部分です。この場合はansに5をかけます。

174はこの図にはいません。グループ3です。ということは、各行/列の最大値を超えない範囲ではどこにでも入れます。
f:id:hewla:20190114002938p:plain
この青く囲った範囲に入ることができます。
この場合はansに $7*8$ を掛ければいいと思いそうになりますが、そうではありません。
この範囲にはすでに175から182が入っているからです。
これらの数字を入れた上で174が入れるマスはいくつあるか、ということを考えなければならないので、ansには $7*8 - (182 - 175 + 1)$ を掛けます。

これで、各数字についてどういう操作をすれば答えが求まるかを考えることができました。

実装について

簡単に述べます。僕の実装は $O(NM(logN + logM))$ です。解説には $O(NM)$ とあったので改善できるのだと思いますが僕にはわかりませんでしたorz

ある数字が上/左に存在しているかどうかを素早く確認できる
ある数字以上の数字のうち、最小のものが何番目かを素早く確認できる

という特性を備えたデータ構造が望ましいような気がします。
僕はstd::set<pair<int, int> >を使いました。firstには並んでいる数字の値、secondにはその数字が何番目のものなのかを保管しておきます。
その上でlower_boundを使うと上記の操作が行えます。

僕のレベルではこれが精一杯でした
僕は#define int longをしているので、このコードをそのまま貼り付けるとintのせいで通らないことがありえます。

▶ソースコードを開く

const int MOD = 1000000007;

typedef std::pair<int, int> P;

int n, m;
int a[1000];
int b[1000];
int ans = 1;
std::set<P> ast, bst;

signed main(){
	scanf("%ld %ld", &n, &m);
	for(int i = 0; i < n; i++){
		scanf("%ld", &a[i]);
	}
	for(int i = 0; i < m; i++){
		scanf("%ld", &b[i]);
	}
	
	std::sort(a, a+n, std::greater<int>());
	std::sort(b, b+m, std::greater<int>());
	
	for(int i = 0; i < n; i++){
		ast.insert(P(a[i], i));
	}
	for(int i = 0; i < m; i++){
		bst.insert(P(b[i], i));
	}
	
	for(int i = n*m; i > 0; i--){
		auto ita = ast.lower_bound(P(i, 0));
		auto itb = bst.lower_bound(P(i, 0));
		int product;
		if(ita == ast.end() || itb == bst.end()){
			product = 0;
		}else if(i == ita -> first && i == itb -> first){
			product = 1;
		}else if(ita -> first == i){
			if(itb == bst.end()){
				product = 0;
			}else{
				product = itb -> second + 1;
			}
		}else if(itb -> first == i){
			if(ita == ast.end()){
				product = 0;
			}else{
				product = ita -> second + 1;
			}
		}else{
			product = (ita -> second + 1) * (itb -> second + 1) - (n*m - i);
		}
		ans *= (product % MOD);
		ans %= MOD;
	}
	printf("%ld\n", ans);
	return 0;
}

lower_boundがend()を返す場合についての処理が抜けていて、1WAを生んでしまいました。setを扱うのは僕には難しいです。慣れたいですね。

誤りの指摘や質問等あれば僕のTwitterやコメントまでよろしくお願いします。

2019-01-13

参加記 -KEYENCE Programming Contest 2019 / キーエンスプログラミングコンテスト 2019-

コンテスト参加記

参加記ですので真面目な解説は含まれていません。

A - Beginning

cnt[10]みたいなのを用意して数字のでてきた回数を数えます。setでもよさそう。

B - KEYENCE String

なんだか無限に難しくないですか。手元でテストケースを作って試したところ"keyencea"が通らないことに気がついてこれだけ特別扱いでYESを出力するようにしてあげました。あんまりよくないけどコンテスト中なので速度が最優先です。
ちなみに今書き直してみたのですが謎のバグが増えて困っていますなんやこれ

C - Exam and Wizard

これは割といい感じの時間でできたと思います。
こういうのも貪欲法っていうのですかね。
もっとスマートに実装できた気もするので、後で人のコードも読んでおこうと思います。

D - Double Landscape

このタイトル、グリッドに書き込まれた数字を山の標高として縦横から見た風景が与えられるということをイメージしているんですかね。
手元で図を書いたらうまくいくタイプの問題なので、僕にとっては嬉しい部類です。Excelにおこしてみると割と自明になって、あとはそれをどう実装するか考えてやるだけで良かったです。時間はかかりました。

Double Landscape -AtCoder KEYENCE Programming Contest 2019 / キーエンスプログラミングコンテスト 2019 D- - Hewlaの競プロ記
解説を書きました。

結果

f:id:hewla:20190113234828p:plain
Rank: 413(rated)
Perf: 1740
Rating: 1557(+23)
でした。久しぶりにレートがいい感じに上がってくれました。嬉しいです。
特に500点が解けたのが久しぶりすぎて、とてもとてもホクホクしていました。
次回もレート上げていきたいです。

2018-12-22

参加記 -CADDi 2018-

コンテスト参加記

序盤のやらかし痛すぎる、、、
CADDi 2018 - AtCoder

C - Product and GCD

積の素因数をN個で分ける訳ですね。たったこれだけのことなんですけど、焦ってlongであるべきところにintをつかう(1TLE)、焦って嘘を書く(1WA)をしてしまいました。というか、テストケース4があるのに気付いたのが1回目の提出の後でした。
24:16(2)でACです。
Submission #3841794 - CADDi 2018

D - Harlequin

めっちゃ面白い問題でした。結論はとてもすっきりしているんですが、こういうことを一発で思いつくにはどうしたらいいかわかりません。a[] =
{2, 2, .........}の時に必ずsecondであることが出発点になるんですかね。僕はそうでした。これにたどり着くまでにかなりの時間をかけたのであまりよくありませんが、CのACから40分程度で通せたのでまだよかったかなって感じです。
68:12でACです。
Submission #3846256 - CADDi 2018

E - Negative Doubling

正負の分け目をまず決めればあとは正の単調増加列・単調減少列の問題に帰着できそうだ、ということはパッと見て分かりました。
まず先週の気持ちになって「正負の分け目はにぶたんできるかな〜」とか言いましたが単調性が皆無なので無理です。
そうすると、正負の分け目は前からO(N)かけて見ていくとして、この分け目を固定した時に何回の操作が必要か高速に求められるといい訳です。正の単調増加列・単調減少列にするために必要な操作の回数の累積和を取っておいてあとは足したり引いたりしたら答えが出そうだなと思ったのですが、累積和を引く時に「-n回操作する」ような結論が出得るため、こりゃダメだなと思ってそこからひたすら椅子を温めていました。
考えたことを整理し直して、それ以降の考察を進めやすくしたいです。

ｹｯｶﾊｯﾋﾟｮｵｵｵｫｫｫｫｫｫｫｫ!!!!!!!!!!!!!!!!（高音）

78:12で2完
順位 514位　perf:1374 rating:1532(-16)
単調減少が止まりません。
今回は本当にC問題について反省することがたくさんです。でもDをACしたときはかなり気持ちよかったです。これだから競プロはやめられない
f:id:hewla:20181222233304p:plain

2018-12-16

Irreversible operation -AtCoder AGC029 A-

解説

問題概要

一列にオセロの石が並んでいます。これに対し、次の操作をします。

「黒白」と並んでいるものを裏返し、「白黒」にする

この操作は最大何回できますか
問題リンク: A - Irreversible operation

解説

「黒白」と並んでいるものを裏返して「白黒」にするのは、黒と白を入れ替えて黒を一つ右に動かすことと変わりません。
この操作は黒が全部右に寄り、白が全部左に寄るまで可能です（そうなっていない場合、「黒白」と鳴っている部分が必ず存在するので）。
したがって、各'B'につき、右にいくつ動かせばいいかを数えればそれが答えとなります。また、各'W'につき左にいくつ動かせばいいかの和を答えても良いです。今は後者でいきます。

以下詳細です

答えをansとします。
'W'に出くわしたら、その左にあったBの数をansに加算します。
printf("%ld\n", ans);

僕はBの移動距離をこのように数えました。
文字列の長さをN, その中に含まれる'B'の数をcntとしたとき、s[i]がk番目の'B'のなら、この'B’が移動する距離はN - (cnt - k) + iです。例を図に描いて数えると納得できると思います。

▶ソースコードを開く

long n;
std::string s;

int main(){
	std::cin >> s;
	n = s.length();
	long cnt = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == 'B'){
			cnt++;
		}
	}
	long ans = 0;
	int k = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == 'B'){
			ans += n-(cnt-k) - i;
			k++;
		}
	}
	printf("%ld\n", ans);
	return 0;
}

僕の迷走/反省

AGC029 A: 「黒を1つ右に動かす」のことをやたら複雑に書いて惑わしてきます、こういう問題はジャンル「国語」と呼びたい。
— えびま (@evima0) 2018年12月15日

初っ端から「僕の」ではない感想が入りましたが、僕はジャンル「国語」ができなかったので手元に入出力例の図を描いてみてはじめて「黒を右に動かすだけか」と気づきました。僕は頭の中で考察するのが苦手なので、いつも図にするようにしています。
それと、スッキリした実装ができなかったのがて痛かったです。これで数分は差がつきそうです。

黒の移動する距離の式には様々な考え方があると思います。A問題を1分30秒とかでACしてる人のソースコードはすんごいスマートです。
こういう「いくつ移動するか」とか「間にいくつあるか」とかは割と数をこなすと慣れる面もあると思います。僕は最近精進をしていないので図を描かないとわかりませんでした...

2018-12-16

参加記 -AGC029-

コンテスト参加記

これは参加記なので、内容は主にコンテストの反省です。

A - Irreversible operation

実験しないと本質に気づきませんでした。黒を右に動かしていくだけです。
これを3分ぐらいで通せないのもレート低下の大きな原因だと思うので早く受験終わらせて精進していきたいですね
09:12でACです
解説はこちら:Irreversible operation -AGC029 A- - Hewla's blog
提出ソース:https://beta.atcoder.jp/contests/agc029/tasks/agc029_a

B - Powers of two

ペアの和となる数は数がそんなに多くないのでこれを使って半分全列挙的なやつでできるかな、と考えて嘘貪欲を書きました。
最大の数とペアになる数は一つしか存在しない、というのを解説放送で聞いて理解しました。そしてコードを書いたのですが、multisetをバグらせてしまったのか謎のTLEを連発してしまいました。setでeraseするとイテレータの指す位置が変わっちゃうので気をつけないといけませんね。

C - Lexicographic constraints

Bの嘘貪欲で萎えてしまったので1時間ぐらいこれを考えていました。しかし僕はこちらでも嘘思考で1時間を虚無に費やしたので、結局今日の160分のコンテスト時間は90%以上椅子を温めていただけでしたね、うーん
こちらはちょっと今日通す気力がないのでまた精進した時に通そうと思います

どうでもいいけどLexicographicってめっちゃかっこよくないですか

まとめ

f:id:hewla:20181216014902p:plain
1完300点9分12秒で948位、perf: 1315でRating: 1548(-23)でした。がんばりますーー

2018-11-24

Sum AND Subarrays (AtCoder Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 - D)

解説

散々なことをやりまくって時間を溶かしてしまいました

概要

長さNの数列の部分列からK個を選び、それぞれの部分列の和のANDを取ったものの最大値を求める問題。
B - Sum AND Subarrays

解説

ANDをとるので、選んだK個全てで立っているBITのみが残る

ANDの最大値をとるので、最高ビットを残すことが最優先

すべての部分列を列挙( $O(N^2)$ )
上のビットから順番に見ていって、そのビットが立っているような部分列がK個以上あればそのビットを残すことに決める
そして、そのビットが立っている部分列のみをK個の候補に残し、下位のビットに移る

一種の貪欲といえるのかな

部分和の最大値は $10^{12} \simeq 2^{40}$ なので、longを使います
計算量は、部分列が $O(N^2)$ 個、見るビットの数が $O(log(aN))$ 個、僕はsetを使ったのでここに $O(log(N))$ が加わって、 $O(N^2log(aN)log(N))$ でした。
実装を上手くやると $O(N^2log(aN))$ までおちると思います。2桁msで通してる人のコードを読むと大体わかります

ソースコード

▶ソースコードを開く

long n, m;
long a[1005];
long sum[1005];//累積和
long psum[2000000];//部分和
long bitflag = 1;


int main(){
	scanf("%ld%ld", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%ld", &a[i]);
		sum[i] = sum[i-1] + a[i];
	}
	long pcnt = 0;
	for(int i = 0; i <= n; i++){
		for(int j = i+1; j <= n; j++){
			psum[pcnt] = sum[j] - sum[i];
			pcnt++;
		}
	}
	long upmost = 0;
	for(long bitflag = 1; bitflag < 35184372088832; (bitflag <<= 1)){
		int cnt = 0;
		for(int i = 0; i < pcnt; i++){
			if(bitflag & psum[i]){
				cnt++;
			}
		}
		if(cnt >= m){
			upmost = bitflag;
		}
	}
	if(upmost == 0){
		printf("0\n");
		return 0;
	}
	std::set<int> st;
	for(int i = 0; i < pcnt; i++){
		st.insert(i);
	}
	while(upmost > 0){
		int cnt = 0;
		for(auto i = st.begin(); i != st.end(); i++){
			if(psum[*i] & upmost){
				cnt++;
			}
		}
		std::set<int> st2;
		if(cnt >= m){
			for(auto i = st.begin(); i != st.end(); i++){
				if(psum[*i] & upmost){
					st2.insert(*i);
				}
			}
			st = st2;
			st2.clear();
		}
		upmost >>= 1;
	}
	long ans = psum[*st.begin()];
	for(auto i = st.begin(); i != st.end(); i++){
		ans = (ans & psum[*i]);
	}
	printf("%ld\n", ans);
}

感想/反省

ANDをORと勘違いしたり、setの要素をeraseしようとして散々バグらせたり、自作のビジュアライズ関数がバグってたり、散々なことになってしまいました。問題を解き続けることが必要だなと感じました。次はレートあげたいぞ〜

2018-10-14

AtCoder AGC028 A - Two Abbreviations (300点)

解説

ちょっとだけ迷走した。
AtCoder Grand Contest 028のA。

概要

問題URL
A - Two Abbreviations

二つの文字列 $S$ (長さ $N$ ), $T$ (長さ $M$ )が与えられる。
文字列 $X$ (長さ $L$ )について、

$L$ は $N, M$ のどちらでも割り切れる
$X$ の $1, \frac L N+1, 2\times {\frac L N}+1, ..., (N-1)\times\frac L N+1$ 番目だけ抽出してくるとSと同じ
$X$ の $1, \frac L M+1, 2\times {\frac L M}+1, ..., (N-1)\times\frac L M+1$ 番目だけ抽出してくるとTと同じ

となる文字列 $X$ が存在するならばそのうちで最短のものの長さを、存在しないならば-1を出力せよ。

制約

$1\leq N, M\leq10^5$

解説

$S$ と $T$ を両方ともいい感じに同じ長さに引き伸ばして、場所がかぶったところの文字が全部同じになったらOKという感じです。 $2\times {\frac L N}+1$ とか言っていてわかりづらいですが、0-basedで考えると $\frac L N$ の整数倍というだけなので簡単です。
f:id:hewla:20181014000304p:plain
入出力例3の様子を画像にしてみました。見づらくてすみません>_<
かぶっているところが赤く塗られていますが、その部分が上の文字列 $S$ としたの文字列 $T$ で同じです。このように、場所のかぶったところが同じならその長さは条件を満たします。

まず、 $L$ は $N, M$ のどちらでも割り切れるので、 $L$ は一番小さくて $N, M$ の最小公倍数 $(LCM(N, M))$ で、必ず $LCM(N, M)$ の倍数です。この時場所がかぶっている文字は、 $N, M$ の最大公約数を $g = GCD(N, M)$ とすると、

文字列SではS[ $\frac {iN} g$ ], 文字列TではT[ $\frac {iM} g$ ] $(i = 0, 1, 2, ..., g-1)$

です。
さらに考えると、こうしてできた文字列で場所がかぶっている文字は、この文字列をいくら引きのばしても場所がかぶったままです。よって、 $L = LCM(N, M)$ でうまくいかない場合は、これを満たす文字列は存在しないということになります。

したがって、 $i = 0, 1, 2, ..., g-1$ について、S[ $\frac {iN} g$ ]　== T[ $\frac {iM} g$ ] を確かめるだけでよいことになります。

最大公約数についてはユークリッドの互除法が高速で便利です。コピペで使うライブラリを作ったので、リンクを貼っておきます。一応実装したことない人は一度やってみることをお勧めします。GitHubの扱いは不慣れですので何か間違ってたらごめんなさい。
Cpp_ComProLib/gcd at master · hewlae/Cpp_ComProLib · GitHub
最小公倍数は最大公約数ともとの2数N, Mから簡単に求められ、その値は $LCM(N, M) = \frac {NM}{GCD(N, M)}$ です。

▶ソースコードを開く

long gcd(long num1, long num2){
	if(num2 > num1){
		std::swap(num1, num2);
	}
	if(num2 == 0){
		return num1;
	}else{
		return gcd(num2, num1 % num2);
	}
}

long lcm(long num1, long num2){
	return num1 * num2 / gcd(num1, num2);
}

std::string s, t;
long n, m;

int main(){
	scanf("%ld%ld", &n, &m);
	std::cin >> s >> t;
	long g = gcd(n, m);
	for(int i = 0; i < g; i++){
		if(s[i*n/g] != t[i*m/g]){
			printf("-1\n");
			return 0;
		}
	}
	printf("%ld\n", lcm(n, m));
	return 0;
}

なにか間違っている点や質問などがあったらTwitterやコメントなどで教えてください。

感想

GCDやLCMにはすぐにたどり着きました(そこはいつも得意)が、いくら引きのばしても場所がかぶるやつはかぶるということに気づくまでにちょっとかかり、迷走してしまいました。13分で解けたのはラッキー