ABC350

A - Past ABCs

与えられる文字列は 6文字で、先頭の3文字は気にする必要が無く、末尾 3 文字は数字であることが保証されています。
そのため、文字列の4文字目から6文字目までの部分文字列を数字に変換して条件を満たすか値かどうかを調べればよいです。

B - Dentist Aoki

長さ N の論理型の配列を用意します。歯が生えている状態を TRUE, 抜いている状態を FALSE として、
初期状態はすべて TRUE とします。与えられた治療する番号について、その配列要素が TRUE のときは FALSE, FALSE のときは TRUE に変えます。
最終的に TRUE の数が答えになります。

C - Sort

与えられた配列 A を先頭から順にみていきます。
i 番目の要素 A[i] が i と異なるとき、 i 番目の要素と A[i] 番目の要素を入れ替えます。
すると A[i] 番目の要素は正しい値になります。これを i 番目の要素 が A[i] = i になるまで繰り返します。
A[i] = i になったら、i に 1加えて同じことを繰り返します。
たとえば、
3 4 6 1 2 5 8 7
↓ 　1番目と3番目入れ替え
6 4 3 1 2 5 8 7
↓ 　1番目と6番目入れ替え
5 4 3 1 2 6 8 7
↓ 　1番目と5番目入れ替え
2 4 3 1 5 6 8 7
↓ 　1番目と2番目入れ替え
4 2 3 1 5 6 8 7
↓ 　1番目と4番目入れ替え
1 2 3 4 5 6 8 7
↓ 　7番目と8番目入れ替え
1 2 3 4 5 6 7 8
のように入れ替えればよいです。

D - New Friends

ユーザを頂点、友達関係を辺で表現するグラフを考えます。条件から無向グラフです。
Union-Find 木から、友達関係の連結成分を求めます。頂点 i が含まれる連結グラフの頂点数が N で、
頂点 i の次数が d のとき、頂点 i は追加で (N-1-d) の頂点を相手に辺を結ぶことができます。
この値を全頂点で合計します。一つの辺で2つの頂点の次数を1つずつ増やすことができるため、合計した値を 2 で割った値が答えです。

E - Toward 0

メモ化再帰で解きます。
ある整数 N について、支払金額の期待値の最小値を とします。
1番目の操作を選ぶと、支払金額の期待値は です。
2番目の操作を選ぶと、



となります。
そこで、 と の小さいほうを とすればよいです。
これを再帰で求めます。値が決まった Cost[N] を連想配列などで管理してメモ化することで効率よく答えが求められます。

F - Transpose

( ) の深さが一つ増えるごとに反転されるので、深さが奇数のときは反転、偶数のときはそのままでよいことになります。
あらかじめ、何文字目の "(" と 何文字目の ")" が対応しているかを探しておきます。
処理は再帰で行います。 "(" と ")" で挟まれた範囲について、深さが偶数のときは前から順に、奇数のときは後ろから大文字小文字を反転させて一文字ずつ出力していきます。
"(" または ")" が見つかったら再帰で処理して、それが終わったら対応するカッコの次から処理を継続します。