精進(2024/2/12) - あるぱかのブログ

CODE FESTIVAL 2015 あさぷろ Easy B - ヘイホー君と置き換え
CODE FESTIVAL 2017 qual C B - Similar Arrays
AtCoder Grand Contest 029 A - Irreversible operation

AtCoder ProblemsのRecommendation(Moderate)を解く

CODE FESTIVAL 2015 あさぷろ Easy B - ヘイホー君と置き換え

diff=430くらい

リンク：B - ヘイホー君と置き換え (atcoder.jp)

概要：文字列 $S$ を前半後半に分けて、前半＝後半にするために必要な操作数を出力してね

よくある文字列の置換操作の操作数を求める問題です。

今回は文字を自由に置き換えできるので簡単です。

（ $n$ 文字目と $m$ 文字目を入れ替えみたいな制約が無い）

まず $S$ の文字数が奇数の場合は前半後半に分割不可能なので $-1$ を出力します。

偶数なら最悪全文字を置き換えれば題意は満足できます。

とりあえず $S$ の頭から $\dfrac{N}{2}$ 文字目までを前半として文字列 $A$ 、 $\dfrac{N}{2}$ 文字目から最後を後半として文字列 $B$ としました。

スライス記法で $S[:N//2$ ]とすることで $0$ ~ $\dfrac{N}{2} -1$ 文字目までを取り出しています。

あとは $0$ から $\dfrac{N}{2}$ まで走査して文字が異なる場所を数え上げれば答えになります。

実際に文字列を置換する必要はありません。

N = int(input())
S = input()
if N % 2 != 0:
    print(-1)
else:
    A = S[:N//2]
    B = S[N//2:]
    count = 0
    for i in range(N//2):
        if A[i] != B[i]:
            count += 1
    print(count)

提出リンク：提出 #50230109 - CODE FESTIVAL 2015 あさぷろ Easy (atcoder.jp)

CODE FESTIVAL 2017 qual C B - Similar Arrays

diff=430くらい

リンク：B - Similar Arrays (atcoder.jp)

概要：配列 $A$ の各要素 $A_i$ に対して配列 $B$ の各要素 $B_i = A_i -1$ or $A_i$ or $A_i +1$ としたときの配列 $B$ の全項の積が偶数になるパターン数を出力してね

配列長さ $N$ の制約が10以下なので最悪全探索しても $3^{10} = 59,049$ パターンなので間に合いそうです。

が、多重for文でややこしくなりそうなので別の方法を考えます。

今回は積が偶数か奇数かだけ分かればいいという点を使います。

かける数に1つでも偶数があれば積は偶数になります。

逆に言えばすべて奇数をかけるパターンでしか積が奇数になりません。

つまり全パターン $3^{N}$ から配列 $B$ の全要素が奇数のパターンの数を引くことで答えとなります。

また $A_i$ が偶数なら $B_i = A_i \pm1$ の範囲で奇数となりえるのは2通り( $A_i +1, A_i -1$ )あり、 $A_i$ が奇数なら $B_i = A_i \pm1$ の範囲で奇数となりえるのは1通り( $A_i$ )あります。

配列 $A$ の各要素について偶奇判定を行うことで $B$ の全項が奇数になるパターン数を把握できます。

これにより計算量 $O(N)$ で答えを求めることができます。

N = int(input())
A = list(map(int,input().split()))
count = 1
for i in A:
    if i % 2 == 0:
        count *= 2
    else:
        count *= 1
print(3**N - count)

提出リンク：提出 #50230176 - CODE FESTIVAL 2017 qual C (atcoder.jp)

AtCoder Grand Contest 029 A - Irreversible operation

diff=430くらい

リンク：A - Irreversible operation (atcoder.jp)

概要： $B$ と $W$ からなる文字列について $BW$ の並びを $WB$ にする操作を可能な限りやって最大回数を出力してね

これもよくある文字列のスワップです。

この問題では文字列 $S$ の長さが最大 $2 \times 10^{5}$ なので計算量 $O(N)$ でないとTLEになります。

つまり文字列 $S$ を頭から走査して $BW$ のスワップをする動作を愚直に繰り返す方法では計算量が最悪 $O(N^{N})$ となるためACできません。

(例えば $B$ が $2 \times 10^{5} -1$ 個並んだあとに $W$ があるような並び)

ということで、題意の操作を繰り返すと最終的にどういう形になるか、それに対して初期値はどのくらい離れた状態にあるのかを考えることにします。

$BW$ の並びを $WB$ にするということは言い換えると $W$ を左側に、 $B$ を右側に固めることになります。

例として入力例2の $BWBWBW$ は6回の操作で最終的に $WWWBBB$ の並びになるはずです。

$W$ の位置に着目して、最初は $1, 3, 5$ 番目にありますが最終的には $0, 1, 2$ 番目に移動しています。

1つ目は $1 - 0 = 1$ の距離を、2つ目は $3 - 1 = 2$ の距離を、3つ目は $5 - 2 = 3$ の距離を移動していることがわかります。

移動距離の総和をとると6となりこれが答えとなります。

実際には複数ある $W$ を区別する必要はないので、各 $W$ の初期位置の総和と操作完了後の $W$ の位置の総和を引き算することで答えを出します。

ちなみに $0$ ～ $N-1$ の総和は $\dfrac{N(N-1)}{2}$ で計算できます。

文字列 $S$ を1巡だけ走査すれば目的を果たせるので計算量は $O(N)$ となり十分高速です。

S = input()
N = len(S)
count = 0
dist = 0
for i in range(N):
    if S[i] == 'W':
        count += 1
        dist += i
W = (count*(count-1))//2
print(abs(W-dist))

提出リンク：提出 #50230261 - AtCoder Grand Contest 029