元の並び順を覚えたままソート

B - Guidebook
こういう問題が出たときに、

Bみたいなやつのこういうソート方法はもっと知られてもいいと思うの(pairとかでやると後々使うときにfirstとかsecond.secondとかで脳が死ぬので)https://t.co/kM2KVzN0qN pic.twitter.com/a4wh7i8PPh

— てんぷら (@tempura_cpp) May 26, 2019

こういう方法をとれますが（てんぷらさんありがとうございます）、何も頭を使わずに書いてると頻繁にバグらせたので、このソートでなにがどうなるのか備忘録的に書いておきます。

そもそもどういうソート？

　数列をソートするととなりますが、もともとが何番目にあったのかを思い出すことができません。思い出したいときによく考えるのは

というstd::pairの配列を作ってソートすることで、これだと

となって、無事がソート前は0番目だったことを覚えたままソートできています。これが「覚えたまま」の意味です（わかりにくくてすみません）。
　で、これだとfirst.secondやらsecond.firstやら出てきがちで嫌な気分になるので、もっとシンプルにやろうというのが前述のてんぷらさんのツイートにあったソート方法です。

どうなるの？

数列本体は入れ替えず、ordが入れ替わります。

ソート後の数列のi番目はnum[ord[i]]になり、
もともとord[i]番目にいたやつがi番目にやってきたことになります。

複雑にソートやらなんやらかんやらを繰り返すときも、数列そのものは絶対入れ替えない方針で実装するとたぶん見通しが良くなるんだと思います（それはそう）。

おわりに

全然整理できてない雑な備忘録で申し訳ないです。
また、他のところでもこの方法が紹介されていたりとか、もっといいほうがあったりとか、この記事に誤りが含まれていたりとかしたら教えていただけると嬉しいです。

Colorful Subsequence - AtCoder Grand Contest 031 A

AGC031-A, 200点でした。
問題リンク

解説

重要な点として、

• 部分列は全て異なる文字からならねばならない
• 文字列として同一でも、異なる位置から取り出された部分列は区別して数える

ということがあります。
僕は問題文の勘違いもあってかなり迷走しましたが、結局、

• 各アルファベットは1回しか現れられない
• 異なる位置にある同じアルファベットを選んだ文字列同士は区別して数えられる

ので、
例えば'a'が中に回現れたとすると、'a'については

• 部分列に一つも含まれない
• 部分列に番目の'a'が含まれる

ので、'a'の選び方はパターンあるわけです。

各アルファベットについて、(その個数+1の積)-1が答えになります。
(最後に-1する理由ですが、この方法だと全てのアルファベットが一つも部分列に含まれない場合、つまりからの文字列となる場合を1つだけ含むからです。)

▶ソースコードを開く

const long MOD = 1000000007;

long n;
std::string s;
long ans = 1;
long alp[26];
 
int main(){
	scanf("%ld", &n);
	std::cin >> s;
	for(int i = 0; i < n; i++){
		alp[s[i] - 'a']++;
		alp[s[i] - 'a'] %= MOD;
	}
	for(int i = 0; i < 26; i++){
		ans *= (alp[i]+1);
		ans %= MOD;
	}
	printf("%ld\n", ans-1);
	return 0;
}

An Ordinary Game - AtCoder Regular Contest 064 D -

ARC064-D、500点。解き心地の良い問題でした。

問題リンク

考察の流れ

わからないのでとりあえず手を動かしてみます。
話をすっ飛ばして、手を動かした結果わかったことをここに書きます。

• 文字列の両端の文字は消すことができないので、ゲーム開始前とゲーム終了時の文字列で両端の文字は変わりません。
• 終了時の文字列は必ず1種類または2種類の文字から構成されています。(それ以上含むと必ずまだ消せる文字があることは実験するとなんとなくわかると思います)(証明は3種類目の文字周辺の状態を全て列挙することでできると思います)

この二つのことから

• sの両端の文字が同じ → 終了時の文字列の長さは奇数 (abab...aba のようになります)
• sの両端の文字が異なる → 終了時の文字列の長さは偶数 (abab..ab のようになります)

ということが言えます。
これを用いると文字列の長さの減りの偶奇がわかるので、最終状態に至るまでの操作回数の偶奇がわかります。
偶数回の操作をして最終状態に至れば青木君の、奇数回ならば高橋君の勝利となるので、要するに「sの両端の文字」「最初のsの文字数」からどちらが勝つか判定できるわけです。

僕の場合は真面目に頭を使って計算するよりも、入出力例と自分で作ったサンプルケースに前述の考察を当てはめて適当に考える方が早いし楽だったのでそうしました。あんまりよくないかも

結果です。

こういうのってどれぐらい簡潔に書くか、どれぐらい親切に書くかちょっと悩みますよね

ソースコード

bool found[26];
long cnt;
std::string s;

int main(){
    std::cin >> s;
    long same = (s[0] == s[s.length() - 1]);
    long even = s.length() % 2;
    if((same + even) % 2){
        printf("First\n");
    }else{
        printf("Second\n");
    }
    return 0;
}
  

感想

こういう感じの問題はわからなかったらとりあえず手を動かすことにしています。
どちらかというと、サンプルを眺めたり手を動かしたりしながら全てのケースに共通する法則を探してる感じがします。

ところで、2人が別に最適な戦略を取らなくても、どうやっても最終的に勝つ人が決まっているのって面白くないですか。

参加記 「みんなのプロコン 2019」

悪くはなかったけど良くもなかった

A - Anti-Adjacency

adjacent /ədʒéɪs(ə)nt/ (形) 隣接した
A問題最難問かと思ったけど良く読んだらそんなことはなかった 端から1つ飛ばしに選んでいけばいいですね
Submission #4204200 - Yahoo Programming Contest 2019

B - Path

オイラーが証明したやつだーって思いました。木構造っていう制約が付いているので構造は2パターンしかなくて、一本道かウニみたいになってるかのどちらかです。for文の中身をうっかりミスってWAを産みました。5分は大きかったなあ
Submission #4206209 - Yahoo Programming Contest 2019

C - When I hit my pocket...

ポケットを叩くとビスケットがひとつってやつですね。これ砕けるからやろってずっと思ってました。Cookie Clickerにも通ずるところがありそうですが、これってもしかして共通の文脈があるんですかね
O(1)なので解いてる時の感覚は完全に200点とか100点をやってる時のそれでした。でもやっぱり簡単ではなかったですね。100とか200にこれがあったらびっくりする
Submission #4208905 - Yahoo Programming Contest 2019

D - Ears

すぬけ君にひどいことしないで
何気に「数直線上を連続的に散歩」とかも面白いですよね。
情報をうまく吸い出して簡略化していく部分はうまくできたと思います。途中「偶数回でもいいのは両端の1つだけ」だと思ってた時間もありましたが、しばらくして気づけました。
問題はその後で、DPに気付けなかったのが本当に良くなかったです。「DPをやるとうまくいく場合の感覚」みたいな定跡力が完全に抜け落ちていました。
解説ACです。
Submission #4218697 - Yahoo Programming Contest 2019

まとめ

Hewlaさんの「みんなのプロコン 2019」での成績：647位
レーティング：1605→1612 (+7) :)
Highestを更新しました！ https://atcoder.jp/users/Hewla/history/share/yahoo-procon2019-qual?lang=ja

前回の日経コンでしれっと青になっていました。そして水色落ち回避、微増です。自分の実力を鑑みると絶対水色落ちすると思ってたのでこの結果は喜ぶべきなんだと思うのですが、Bの1WAとかDのDPを落とすとか悔しいポイントがたくさんあるのであんまり嬉しくないです。だってD通してたら黄色パフォもありえたわけですから...
次回はいつになるかわかりませんが、頑張ります。

青になるまでやったこと記事は受験がひと段落した時にもしまだ青だったら執筆しようと思います。

When I hit my pocket... - AtCoder 「みんなのプロコン 2019」 C

400点。慎重にやります。
問題リンク

解説

ポッケを永遠に叩いていても1枚ずつしか増えませんが、A枚のビスケットを1円にして1円でB枚のビスケットを買ってくれば2回の操作でB-A枚増やすことができます。どっちがお得かな、というふうに考えたらいいと思います。あとは場合分け。

まず、ビスケットを一枚も換金しない/できない場合について。

• A-1 >= K (ビスケットを換金できない)
• B-A <= 2 (ビスケットを換金するよりポッケを叩いたほうがいい)

の場合に答えが

• K+1

になります。

A枚のビスケットをB枚に変えるためには2回の操作が必要です。K回目の操作でうっかりビスケットをお金に変えてしまうと損なので、所持枚数がA枚に到達した時点での残り操作回数 K - (A - 1) の偶奇による場合分けが必要です。

• 偶数の時 A + (K-A+1) / 2 * (B-A)
• 奇数の時 A + (K-A) / 2 * (B-A) + 1

補足説明をすると、
偶数の時 A枚集めた後、クッキーを(K-A+1)/2回 (B-A)枚ずつ増やす
奇数の時 A枚集めた後、クッキーを(K-A)/2回 (B-A)枚ずつ増やし、一回ポッケを叩く
という立式です。

▶ソースコードを開く

#define int long

int k, a, b;

signed main(){
	scanf("%ld %ld %ld", &k, &a, &b);
	if(a > k+1 || b-a <= 2){
		printf("%ld\n", k+1);
		return 0;
	}
	if((k-a+1) % 2 == 0){
		printf("%ld\n", a + (b-a) * (k-a+1) / 2);
	}else{
		printf("%ld\n", a + (b-a) * (k-a) / 2 + 1);
	}
	return 0;
}

Cookie Clickerって意外と時間溶けるんですよね

Restore the Tree - AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 D

500点です。
問題リンク

結局何を求めればいいのかの考察はすぐ終わりましたが、それをどう実装するのかでそれなりに詰まりました。

解説

　「子孫へ有向辺を引く」とあります。このことから、新しい辺を引くことによって、根からその頂点への最短距離は短くなった、ということが言えます。つまり、各頂点への最長経路で通る辺が元の木というわけです。

　これを実装します。トポロジカルソートを用いた解法がわかりやすくてよいと聞きましたが、今回は自分が採用したBFS(幅優先探索)を用いた解法を解説します。トポロジカルソートは名前しか知りませんでした。

　最長経路の探索はよくわかりませんが、最短経路ならできます。辺に重みがないのでBFSをしてやればよいですね。そこで、BFSをして、見つかった最短経路の辺を消していくことを考えます。
　頂点によっては親が複数いるわけですが、本来親は1つだけなので、この親のうち一番頂点から遠いものから伸びている辺だけ残し、残りの辺を消して仕舞えばいいです。

　BFSの実装方針です。BFSなので、根からの距離が短い経路から順にわかっていきます。根からBFSを行ってある親からある頂点に到達した時、

• その頂点の親が他にあれば、今通ってきた親を「その頂点の親リスト」から消す。BFSのqueueへのpushは行わない
• 他に親がなければ今通ってきた親は真の親である。その頂点をBFSのqueueにpushする

　「pushを行わない」という部分は重要で、これを行わなければ同じ頂点からの探索を何度も繰り返すことになり無駄が増えます。僕はこれで計算量が爆発することを全く考えずTLEを出しました。また、最長経路を見つけたいので、最後にその頂点を訪れた時だけpushします。この点でも普通のBFSとは異なります。

▶ソースコードを開く

int n, m;
std::vector<int> edge[100005];
std::set<int> parent[100005];
int ans[100005];

void bfs(int rt){
	std::queue<int> que;
	que.push(rt);
	while(!que.empty()){
		int vis = que.front();
		que.pop();
		for(int i = 0; i < edge[vis].size(); i++){
			int next = edge[vis][i];
			if(parent[next].size() > 1){
				parent[next].erase(vis);
			}else{
				ans[next] = vis;
				que.push(next);
			}
		}
	}
	return;
}

signed main(){
	scanf("%ld %ld", &n, &m);
	for(int i = 0; i < n+m-1; i++){
		int a, b;
		scanf("%ld %ld", &a, &b);
		edge[a].push_back(b);
		parent[b].insert(a);
	}
	for(int i = 1; i <= n; i++){
		if(parent[i].size() == 0){
			bfs(i);
			break;
		}
	}
	for(int i = 1; i <= n; i++){
		printf("%ld\n", ans[i]);
	}
	return 0;
}

Different Strokes - AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 C

400点
問題リンク

考察の流れ

　2人分の得点について考えるのは面倒なので、得点を1種類のみにしてやりたいです。最終的に出力するのは「高橋くんの点数 - 青木さんの点数」なので、この点数についてずっと考えてやると良さそうです。

　こういう問題は、僕の場合はまず高橋くんの料理の選び方から考えていきます。
　高橋くんが料理を選ぶと何が起こるでしょうか。高橋くんは点得ますが、同時に青木さんは点を失うというふうに考えてみます。高橋くんは、が大きい料理から順にとっていくと良さそうな気がします。高橋くんが料理を選ぶと、高橋くんと青木さんの点数の差は大きくなるというわけです。すると、青木さんが料理を選ぶルールも同様で、この点数が大きい順にとっていきます。こうすることで、aとbの2種類あった点数が1種類に収まりました。
　このように考えるならば、初めは青木さんが全ての料理を持っていて、それから1ターンおきに高橋くんが料理を奪っていく、というふうに考えるとよさそうです。高橋くんはが大きい料理から順にとっていきますが、同時に青木さんも同じルールで自分の料理を選んでいくので、高橋くんは実際には奇数番目にが大きい料理を選ぶことができます。
　
　もちろん逆でも構いません。高橋くんが全ての料理を独り占めしていて、それを青木さんが奪っていくタイプのプログラムでもいいと思います。僕はこちらでやりました。

▶ソースコードを開く

int n;
int a[100005], b[100005];
int score[100005];
int sum;

signed main(){
	scanf("%ld", &n);
	for(int i = 0; i < n; i++){
		scanf("%ld %ld", &a[i], &b[i]);
		score[i] = a[i] + b[i];
		sum += a[i];
	}
	std::sort(score, score+n, std::greater<int>());
	for(int i = 0; i < n; i++){
		if(i % 2 == 1){
			sum -= score[i];
		}
	}
	printf("%ld\n", sum);
	return 0;
}