当局みてるぅ〜？？？

このブログの楽しみ方
曲をかけながら下まで流し見する．

しゅわしゅわ〜〜

今日も競プロ明日も競プロ

競技プログラミング以外のプログラミングは取っ掛かりがきつくて触れないですねぇ〜〜

AGC054 A- Remove Substrings

[文字列，操作の最小回数, 灰diff]
与えられた文字列Sの中から文字列を削除していく．
このとき，削除は，選んだ区間の端の文字２つが異なっていれば削除できる．
例えば，ushitapunichiakun っていう文字列sの，[ushitapu]nichiakunこういう区間は削除できないけど，[ushita]punichiakunみたいな区間は削除できる．
で，この操作は最小何回でSを空にできるかっていう問題

Sの０文字目とn-1文字目が異なっている場合は，一回で全部削除できる．
それ以外の場合を考える．

とりあえず，Sの両端の文字は'a'だとして考えるか．
S = a ??????????????? a みたいな感じ．
このとき，?の中にa以外の文字が一つしかないと，空文字列にすることは出来ない

S = aaaaaaabaaaaaaaaaみたいな感じ．左端のaからbまでとっても，bから右端のaまでとっても，その後の操作ができなくなってしまう．

次に，a以外の文字が複数あれば必ずから文字列にできるのかを考えてみる．

S = aaaaabbaaaaaaaみたいなとき，左端のaから左のb,右のbから右端のaの２手でクリアできる． S= aaaaabcaaaaaaaみたいな感じで，bbじゃなくてbcであっても，同じようにしてクリアできる．だから，両端の文字(a)以外の文字に対しては，区別しなくていい(bとcは同じ役割をしてくれて，互いに干渉しない)

こうしてみると，a以外の文字が2つ以上あれば必ず解けるのかな？と思えてくる．実はそうではない．

S = abaaaababaaba みたいなとき，どうやってもクリア出来ない．どの区間のaからbを消してもその操作の後の両端は必ずaになっている．だから無理．ちなみに，この中でbがb以外のもの

S= abaaaacadaaea みたいな風に，bじゃなくても同じ．「aから見ると，端として選ぶ相方がbからc,d,eになっただけで元と変わりがない．」って感じで，「b(とかcとか)から見ると，端として選ぶ相方がa,c,d,eに増えた．でも，相方に誰を選んでも，Sの両端がaという状況は変わらない．

上に上げた2つの例は，Sの中に，連続したa以外の文字が出てくる場所がないってこと．

だから，証明とかはしてないけど結局，Sの中にa以外の文字が連続して2回出てくる場所があれば，から文字列にできる．そしてそのときの操作回数は，以下のようにすることで2手である．

S = [a???????????b] [b???????????a]

こんな感じ．1手目の操作（左の区間でも右でもどっちでもいいけど）をすることで，Sの両端が違う文字列にすることができるので，更にもう1手加えることで空文字列にできる．

それで，a以外の文字が複数あればいいのかな，とかって言ってたけど，それじゃ駄目な理由（空文字列に出来ない理由）は，どれだけ操作を加えても，Sの両端が異なる文字にすることが出来ないからであるとも言える.

もともとのSの両端と異なる文字が２つ続く場所を見つけるのは，下のコードみたいにすればokたぴ

int n;
cin >> n;
string s;
cin >> s;
char c = s[0]; //s[0] とs[n-1]は同じっていうときだけの話ね
for(int i = 1; i < n-2){
    if(s[i] != c && s[i+1] != c){
        // 連続する二文字が，Sの両端の文字と異なる
        cout << 2 << endl;
        break;
    }
}

注意だけど，このコードはACコードじゃなくて，連続する２文字が異なる場所があるか見つけるだけだからね．

ARC124 A- LR Constraints

[mod,場合の数，組み合わせ]

提出AC

はじめに制約がないとき，N枚のカードについて，それぞれK通りの書き方がある．

だから，もしも制約が1個もないならNのK乗が答えですね.

カードが5枚あって，K=3のとき，{3,3,3,3,3}みたいな配列を用意しておきます．これは，制約をまだ一つも確認していないとき，1番目，2番目…，5番目のカードに書かれる数は1~3の3通りあることを示しています．

制約を1個見る． L 3

こんなとき，3番目のカードは1で，それより左には1がないことがわかります．これを先程の配列に反映させます．反映のさせ方としては

3番目の数は1で確定したので，3番目は1の1通りだけになる．{3,3,1,3,3}
1番目と2番目（3番目より手前)の数は，1以外の数が入る（つまり，1番目，2番目は2か３の２通りになる) {2,2,1,3,3}

2の手順では，2か３の２通りになるって書きましたが，これは，もともとの配列の数-1になるってことです

とりあえず具体例として，適当に制約を続けていきます

２つ目の制約 R 2

意味は，２番目の数は2で，それより右には２がない．

配列更新の手順は次の感じ

２番目の数は２で確定したので，２番目は２の１通りになる {2,1,1,3,3}
２番目より後には，2が入らないことがわかったので，1ずつ小さくする
ただし，既に1である場所は「数字が確定してる（3番目は1だよ)」ので，何もしない

{2,1,1,2,2}

よしよし，最後に，3つ目の制約を考えよう

5番目は3．それより右に3はない．じゃあ{2,1,1,2,1}だね．

で，最終的な答えは，配列の全ての数をかけて2 * 1 * 1 * 2 * 1 = 4通り！みたいな感じ．

これを実装すれば勝ち．俺はこの日，参加登録だけして問題を見て「わかんね〜」をしながら布団ゴロゴロしてた．

草体にぼ日記

だらだらと

8月9日であってほしい 2021年

当局みてるぅ〜？？？

今日も競プロ明日も競プロ

AGC054 A- Remove Substrings

ARC124 A- LR Constraints