2020年 9月 2日

まえがき

こんにちは、お久しぶりです。私の名前はハタモリジュウゾウ。
最近は絵日記ばかり描いていてブログを書いていなかったのですが、絵日記よりもこっちのほうが百億倍簡単ですね。

まあ、実際はゲームばかりしていてUbuntuを起動しないからブログを書く機会が無かっただけなんですけどね。

補足すると、僕のPC(ココちゃん）はUbuntuとWindowsが入っていて、競プロをする時はUbuntu,ゲームをする時はWindowsを使うようにしているので、競プロをしない→　Ubuntuを起動しない。ってことです。

で、今なんでUbuntuを立ち上げているかと言うと、ApeXやりまくる　→　ライザのアトリエやりまくる　→　ApeXに戻る気が起きねえなあ…　→　Ubuntu立ち上げるかあ…（渋々）　って感じです。
だれか僕の彼女になってくださいね。

健康管理

モチベーションが無い。

何した

蜘蛛との同棲を開始した。

具体的に

こんにちは。アシダカグモ。

今日解いた問題

ARC013 B-引っ越しできるかな？

[最適化,最小化]
それぞれの荷物について、縦、横、高さがありますが、どれが縦とか横とか別にどうでもいいので、用意したい箱の縦、横、高さを、縦が一番短く、高さが一番長くするようにしようかな。っていう解法。（証明不明）
つまり、入力で与えられる N, M, L を N <= M <= L とする。 N <= M <= L でないならば、適当にN,M,Lを入れ替えてやる。そうして、N0 ~ Ncのうち最大のものが箱の縦の長さ。
M0 ~ Mc のうち最大のものが箱の横の長さ。
って感じでやれば解ける。
解説でもなんでもないな。

うーん、お気持ちを言えば、いったん全ての荷物について、どの辺を縦にして、どの辺を横にして、どの辺を高さにするか、向きを決めてやる。って感じかな。

各荷物の一番短い辺の長さを縦として採用したい！！！
みたいなね。

CODE FESTIVAL 2014 決勝 D-パスカルの三角形

[パスカルの三角形もどき,ﾋﾗﾒｷ~]
パスカルの三角形を実際に書いてみたら、(1-indexed)で左から2番目の数は1ずつ増えていってることが分かるから、任意の数がパスカルの三角形に登場することが分かる。

具体的には、ある数AはA+1段目の左から2番めに出てきます（あ、答え言っちゃった）

dwangoプログラミングコンテスト B-ニコニコ文字列

[部分文字列,数え上げ,ほんのひと粒の涙]
ｴｯﾄﾈ,この問題の答えの最大値は,5 * 10⁴ の2乗なんだけど、それは2³²に収まらないのでlong long を使おうね。（そのときの入力は、2525252525...25(5万組の25)です)

この問題で着目すべきは、連続する2と5の組の数です。たとえば、"252525"1112"25"5という入力が与えられた時、3個の連続する25と、1個の連続する25という風に見てあげたいです。(ダブルクオーテーションマークはみやすさのためにつけました)

で、簡単（になるかどうかは知らないけど)のために、25という文字列を'A'と置き換えて上げました。すると先程の入力は AAA1112A5というふうに書き換えることが出来ます。このもとで,Aだけが含まれた部分を取り出す方法が何通りあるか的なやつを数えて上げれば良いのです。
AAA1112A5のAが3つ連続した部分を領域a,Aが1つ連続してる(2と5の間にあるやつ)部分を領域bとする。
今回の場合は、領域aからAを1個取り出す場合、どのAを選ぶかで3通り。
領域aからAを2個取り出す場合、どのAを選ぶかで2通り。（Aは連続している2つじゃないと行けないことに注意)
領域aからAを3個取り出す場合、3つのうち全てのAを選ぶ1通りだけ。
次に、領域bからAを1個取り出す場合、1個選ぶだけの1通りしかない。
全てを合算して答えは(3+2+1)+(1) = 7です。

で、領域xはAが連続してk個ある時、その領域からニコニコ文字列の取り出し方が何通りあるかと言う部分についてお話します。
まず、領域xから1個のAを選ぶ時は、k通りある。
これは簡単だと思います。
次に、領域xから2個以上のAを選ぶ時です。
このとき、Aは連続しているものを取らないと行けないということに注意しなければなりません。つまりAAAとあって、1つ目のAと3つ目のAで2つAを取る。ということはダメなのにゃ。

連続するAを2つ選びたいとき、どのAを開始地点として2つ取るか。ということを意識すればわかりやすくなると思います。

4つの連続するAから2つの連続するAを選びたい時、開始地点となるAを括弧でくくってあげます。
[A]AAA
A[A]AA
AA[A]A
開始地点となるAの選び方はこの3つだけ。
よって、連続する2つのAの選び方は、連続する1つのAの選び方よりも1だけ少なくなります。

最終的には、4つの連続するAから4つの連続するAを選ぶときが何通りあるかというと、1通りですね。

つまり、領域xはAが連続してk個あるとき、その領域から何通りニコニコ文字列が取り出せるかというと、 k + (k-1) + (k-2) + ... + 1 = (k * (k-1)) / 2通りあることが分かります！(ﾔｯﾀｰ

ちなみに僕のコードはこれ。

int main()
{
    string s;
    cin >> s;
    string t = "";
    ll count = 0;
    rep(i,s.size()-1){
        if(s[i] == '2' && s[i+1] == '5'){
            t.push_back('A');
            i++;
        } else {
            t.push_back(s[i]);
        }
    } 
    //cout << t << endl;
    ll n = t.size();
    ll ren = 0;
    ll ans = 0;
    rep(i,n){
        if(t[i] == 'A'){
            ren++;
        } else {
            ans += (ren *(ren+1)) / 2;
            ren = 0;
        }
    }
    ans += (ren *(ren+1)) / 2;
    cout << ans << endl;
}

入力で受け取った物の、25をAに変えたものを、tという変数に持っておいてもらいます。後は、各領域ごとにAが連続して何個続いているかを数えて、領域が終わるごとにansに数え上げたものを足していく。っていうやつです。

おわり

あとがき

リハビリなので緩め。

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2020年9月2日　日記