にぼしの日記

だらだらと

解き方 全問題 (ABC,ARC,AGC編)

AtCoderで解いていった問題の解き方(簡易版)をまとめていく
この問題、あの問題みたいにやれば解けそう!!って時にココ見れば分かる。って感じにしたい。
Code Festival等(other contest)は↓のほうにぶち込んでいきます
AtCoder otherContest まとめ - にぼしの日記


他人に教えられるほどのレートじゃない(茶色)なので、人に見てもらうというよりかは自分の整理のためです。
アドバイスなどあれば随時twitterでもこちらのコメントでもしてくださるとうれしいです。
(こっちには短く問題の要点をまとめようとしてるんだけど、何かけばいいかわからん)

ABC

・一次元リバーシ / 1D Reversi
C - 一次元リバーシ / 1D Reversi
ABC047C -一次元リバーシ /1D Reversi - にぼしの日記
同じ文字のまとまりを1つの区画として、何区画あるか数え上げる
特別なことはしていない

・Go Home
C - Go Home

ABC056C Go Home - にぼしの日記
ちょっとずつ動ける範囲が広くなる
負の方向に跳ねるのは無駄だ

・Dubious Document / 怪文書
C - 怪文書 / Dubious Document

ABC058C 怪文書/Dubious Document - にぼしの日記
その文字が何回出てきたかを数える
英小文字と数字を対応させる。
mapでも解けそう


・Splitting Pile
C - Splitting Pile
ABC067C Splitting Pile - にぼしの日記

整数列が与えられて、前から値を足していったとき、その整数列の総和の半分に値を近づける。

・Grand Garden
C - Grand Garden

ABC116C Grand Garden - にぼしの日記
操作をする系問題(おおざっぱかよ)
左からどんどん花を完成させていくっていう方針で大体いいと思う。

・Megalomania
D - Megalomania

ABC131D Megalomania - にぼしの日記
Yes,No問題、締め切りが近い順にやっていけばいい
証明は分からないけど直感がそう言ってる
とか言って証明はURL飛べばある(あるよ)


ARC
・Scc Puzzle
C - Scc Puzzle

ARC069C SccPuzzle - にぼしの日記
計算量1の問題


AGC
・Prefix and Suffix
A - Prefix and Suffix

AGC006A Prefix and Suffix - にぼしの日記
substrを使うと綺麗かな
二つの文字列 S , Tに対して
Sの後ろ側と Tの前側で一致する文字列の長さの最大値が答えに関連する


・Airport Bus
A - Airport Bus
AGC011A Airport Bus - にぼしの日記


sortして、到着するのが早い人からどんどん処理をしていく。
難しい構文は使っていない。

・Sorted Arrays
A - Sorted Arrays

AGC013A Sorted Arrays - にぼしの日記
実装が難しい問題(?)
数列が与えられて、期待する数列に分けるにはどうしたらいいか?みたいな

・Evilator
B - Evilator

AGC015B Evilator - にぼしの日記
難しいことはしていない
どの階にも1回か2回押せばいける。

ABC047C -一次元リバーシ /1D Reversi

C - 一次元リバーシ / 1D Reversi

提出AC
Submission #8511739 - AtCoder Beginner Contest 047

int main()
{
	cout <<setprecision(10);
	string S;
	cin >> S;
	int n = S.size();
	int count = 0;
	For(i,1,n){
		if(S[i] != S[i-1]){
			count ++ ;
		}
	}
	cout << count << endl;
}

解法

黒と白の区画がいくつあるかだけ数えればいい

白 黒黒黒 白
みたいなとき
左と右に黒を置く(コストは2)
だけど、
そう考えるってよりかは
左にどんどん置いていく
まず一番左に黒
黒 黒 黒黒黒 白
次に一番左にしろ
白白白白白白白
って考えたほうが分かりやすかったです(どちらもコストは2)
黒や白が何個連続していようが、オセロのルール上、白と白 もしくは黒と黒で挟まれた区画
が全部 挟むのに使った色に変換するので
何個連続してるかは関係なくて、何区画あるかが分かればいい。

以後 白 黒 白 は白の区画 黒の区画 白の区画 みたいな感じで考えて

一番左の区画の色と違う色を置くことで区画を1個ずつ減らしていくことが出来て
区画を1までもっていけばいい

つまり、求める答えは区画-1

AGC006A Prefix and Suffix

Prefix 意味 前に置くもの、接頭辞、敬称、
Suffix 末尾に転化したもの、接尾辞、添え字、拡張子
A - Prefix and Suffix



提出AC
Submission #8511255 - AtCoder Grand Contest 006

int main()
{
	cout <<setprecision(10);
	ll n ; 
	string s , t;
	cin >> n >> s >> t;
	int additional = n;
 
	int j = 0 ;
	for(int i = 0 ; i < n ; i ++){
		if(s[i] == t[j]){
			additional --;
			j++;
		}else{
			additional = n;
			j = 0;
			if(s[i] == t[j]){
				additional--;
				j++;
			}
		}
	}
	cout << n + additional << endl;
}

解法
やっていることは、sの前から順に、tの文字列と同じになっているものが何文字あるか、みたいなのを数えていった。
最小でも答えはn、でそれにn - 被ってる数 みたいな
s,tのサイズが同じだから添え字もエラーになることはないと思う。
(s,tの長さが違うとき、s[i](iはs.size()以上)をやったら、勝手に' 'とする。みたいなことをするんですかね?知らないけど)
汚いコードですね
そして何やってるかもよく分からん


良さげな解き方

int main()
{
	cout <<setprecision(10);
	int n , i ;
	string s ,t ;
	cin >> n >> s >> t;
 
	for(i = 0 ; i < n ; i++){
		if(s.substr(i,n-i)==t.substr(0,n-i)){
			break;
		}
	}
	cout << n + i << endl;
 
}

綺麗な解法
結局は、sの後ろの方が、tの前のほうと何文字被っているのかが大事
sについては後ろ側からn-i文字
tについては前からn-i文字を見る

(解説っぽい解答?)

AtCoder otherContest まとめ

解き方 全問題 - にぼしの日記
これの ABC ,ARC ,AGC 以外がこちらになります


・CodeFestival2017 qual B Problem Set
B - Problem Set

CODE FESTIVAL 2017 qual B Problem Set - にぼしの日記
二分探索では解けない(と思う)
線形探索(?)をしてくのですが、配列をソートするのがポイントで、こうすることで同じ値を二度カウントしないようになっている。
多分マップ使っても解ける(解説がmap使ってた、し、そしてmapの解説、コードが書いてあるよ)

CODE FESTIVAL 2017 qual B Problem Set

B - Problem Set

提出AC↓
Submission #8508519 - CODE FESTIVAL 2017 qual B

int main()
{
	cout <<setprecision(10);
	ll n ; cin >> n;
	vector<ll> D(n);
	rep(i,n){
		cin >> D[i];
	}
	SORT(D);
	ll m ; cin >> m;
	vector<ll> T(m);
	rep(i,m) cin >> T[i];
 
	SORT(T);
	ll start = 0 ;
	ll count = 0;
	rep(i,m){
		//難易度がT[i]となるものを探す 二分探索
		ll search = T[i];
		For(j,start,n){
			if(D[j] == search){
				//ok
				start = j+1;
				count ++;
				break;
			}
		}
	}
	if(count==m){
		cout<<"YES"<<endl;
	}else cout << "NO"<<endl;
}

解法
難易度がT[i]となるものを探す 二分探索 これは嘘です
二分探索で探していこうと思ったのですが、それだと同じ必要難易度があったときに、すでにそれを使ったかどうかみたいなのが分からなくなる。
vectorで要素の削除をするのは、配列変数.pop_backで 末尾を消せるらしいですけど途中は消せないので。
嘘ついた
eraseを使えば消せるらしいです
vector::erase - cpprefjp C++日本語リファレンス
計算量⇒削除される要素の数と同じ回数のTのデストラクタが実行される。
何言ってるのか分からないっすね

だから、どちらもソートして難易度の値が小さいものから探していく。
見つかったらその次の難易度のものは、その見つかったものの次の要素番号から探す。
ということで実装してみました。

二分探索を使うのであればeraseが使えるかもしれない
でもmapなり僕の解法のほうが圧倒的に楽だと思う

ARC069C SccPuzzle

C - Scc Puzzle

提出AC
Submission #8507588 - AtCoder Regular Contest 069

int main()
{
	cout <<setprecision(10);
	ll s , c ;
	cin >> s >> c;
	
	ll ans = 0;
	if(c < s * 2){
		ans = c / 2;
	}else if(c < s * 2 + 4){//sをcにすることはできない
		ans = s;
	}else{
		//cをsにしたほうがいい。c4でsccを一つ作れる
		ans = s;
		c -= s * 2;
		ans += c / 4;
	}
	
	cout << ans << endl;
 
}

・解法
sccを1個作るには、s1個c2個、もしくはc4個で作ることが出来る。
sからcを作ることはできないのでまず、sに対応する個数以上cがあるかを見る
なければ c / 2が答え

次①
sに対応するだけ cはあるけど、それから先c4個からsccを作ることはできないなら
答えは s

その次②
c4でsccを作れるぜってとき
cからsに対応する個数 2 * s 個 引いた値を4で割った商だけ更にsccを作れる

ってやったけど
①②はまとめることが出来ますね

if(c < s * 2){
		ans = c / 2;
	}else{
		//cをsにしたほうがいい。c4でsccを一つ作れる
		ans = s;
		c -= s * 2;
		ans += c / 4;
	}

ABC116C Grand Garden

C - Grand Garden
提出AC
Submission #8507430 - AtCoder Beginner Contest 116

int main()
{
	cout <<setprecision(10);
	ll n ; cin >> n ;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
	
	int active = 0 ;
	int ans = 0;
	rep(i,n){
		if(active < a[i]){
			ans += a[i] - active;
			active = a[i];
		}
		else if(active > a[i]){
			active = a[i];
		}
	}
	cout << ans << endl;
}

解説AC
・解法
解説を見ると良い
active って変数を用意するんですけど、
これよりもa[i](花の高さ)
が大きいんだったら、a[i] - activeを足すんだけど、
これが active よりもa[i]が高いときか、a[i]よりもactiveが高いときか分からなくなる

active = 0 スタートで 花の高さ2 だけがあるときを考えると楽で、
2 - 0 で2が答えになるから
a[i] - active を足せばいいと分かる

なんだこれ。うまく解法書けない

AGC013A Sorted Arrays

A - Sorted Arrays

↓ 提出AC
Submission #8506903 - AtCoder Grand Contest 013

int main()
{
	cout <<setprecision(10);
	int n ;
	cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
 
	bool up = false , down = false;
	int ans = 1;
	for(int i = 1; i< n ; i++){
		if(up){
			if(a[i-1] > a[i]){
				up = down = false; 
				ans++;
			}
		}else if(down){
			if(a[i-1] < a[i]){
				up = down = false; 
				ans ++;
			}
		}
		else{
			if(a[i-1] == a[i]){
				//何もしなくていい
			}else if(a[i-1] < a[i]){
				up = true;
				down = false;
			}
			else{
				up = false;
				down = true;
			}
		}
	}
	cout << ans << endl;
}	

実装系の問題ですか?多分。
a[i] がa[i-1]と一緒のときは単調非減少かつ単調非増減なので特に何もしなくていいですね。
それ以外のとき、今単調非減少を見ているのか単調非増減を見ているのかを記憶しておく。
っていうのを実装させるのが結構めんどくさいので多分実装系の問題ですね。

で、まあ、一回ai < ai+1 < ai+2 > ai+3 ってなったら数列の区切りを一個増やさなくちゃいけないので増やす
、ai+4 とai+3の関係(=ならai+5 or ai+6...)`を見て 今見てるのが単調非減少か単調増減化を見る。って感じですね
それを実装すると↑のコードになります。(ACなのでそう)