E - Mex Min

問題

長さの整数列が与えられる．
を満たすすべての整数について，を求め，その最小値を答えよ
atcoder.jp

解法

解法1

なので，個の数字をstd::setで管理すれば解ける

Submission #33224842 - AtCoder Beginner Contest 194

解法2

上記の解法では，更新部分はたかだか２つなので，その更新を行いつつsetを用いてを求めていた．
ある部分列に対してのは，更新前のがわかっていれば，更新部分を見るだけで良い．言い換えると，部分列から外れる数字がの候補になりうる．

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N,M;
    cin >> N >> M;
    
    vector<int>A(N);
    vector<int>count(N + 1, 0LL);
    
    for(auto& a : A)
        cin >> a;
    
    for(int i = 0; i < M; ++i)
        count[A[i]] += 1;
    
    int mex = INT_MAX;
    
    for(int i = 0; i < count.size() && mex == INT_MAX; ++i)
        if(count[i] == 0)
            mex = i;
    for(int i = 0; i + M < A.size(); ++i){
        count[A[i]] -= 1;
        count[A[i + M]] += 1;
        
        if(count[A[i]] == 0){
            mex = min(mex, A[i]);
        }
    }
    
    cout << mex << endl;
}

D - Online games

問題

個の区間が与えられる。個の区間が重複していた数を答えよ。
atcoder.jp

解法

まず最も簡単な愚直な解法を考えてみる。
の区間をすべて全探索してしまい、かぶっている区間の数を数え上げて、最後にそれを答えとしてしまえば良い。
この解法はTLEとなる。そこで少し工夫を加える。
重要な考察として、重複している区間の数が変化するのは、与えられた区間の左端と右端のみである。そのため、入力となる個の区間のみをつかって答えを探していけばよい。

ここまで見ると、区間スケジューリングに近いなという感じがする。
(実は区間スケジューリングで問題を解こうとしていた。始点でソートするとうまくいきそうな気がするか、うまく行かなかった。うまく行ったとしても、めちゃくちゃ大変な実装を要求されそう。)

ただし、今回は区間で見る必要はなく、単純に左端と右端をソートし、単に数え上げるだけで良い

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <tuple>
#include <map>

using namespace std;
using Int = long long;


int main()
{
    Int N; cin >> N;
    vector<tuple<Int,int>>v;
    set<tuple<Int,int>>S;
    
    for(int i = 0; i < N; ++i)
    {
        Int A,B;
        cin >> A >> B;
        v.emplace_back(A,0); v.emplace_back(A + B,1);
    }
    
    vector<Int>ans(N + 1,0);
    Int crt = 0;
    Int key = 0;
    
    sort(v.begin(),v.end());
    
    for(auto [e, type] : v)
    {
        if(type == 0)
        {
            Int prev = e - crt;
            ans[key] += prev;
            ++key; crt = e;
        }
        else
        {
            Int prev = e - crt;
            ans[key] += prev;
            --key; crt = e;
            
        }
    }
    
    for(int i = 1; i < ans.size(); ++i)
    {
        if(i != 1)
            cout << " ";
        cout << ans[i];
    }
    
    
    cout << endl;
}

E - Putting Candies

問題

長さ の数列が与えられる。以下の操作を回繰り返す。
・ 最初の数をとする。　に を追加する。
を答えよ

解法

愚直にシミュレーションするのは自明にTLEとなる。
よく考えると、追加されるのはで割ったあまりを添え字とする数列である。この数は、たかだか個である。
重要な考察として、の値は常に増えていくが追加される数はの番目である。つまり、 の追加によって増える増加分を一度記録しておけば、後はそれを使い回すだけで良い。
鳩の巣原理ja.wikipedia.org

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

using Int = long long;

int main() {
    Int N,K;
    cin >> N >> K;
    
    vector<Int>A(N);
    map<Int,Int> visit, pans;
    
    for(auto& e  : A)
        cin >> e;
    
    Int ans = 0;
    
    for(Int i  = 0; i < K; ++i){
        Int mod = (ans % N);
        Int elm = A[mod];
        ans += elm;
        pans[i] = ans;
        
        if(visit.find(mod) != visit.end()){
            
            Int prev = visit[mod];
            Int T = i - prev;
            Int csum = ans - pans[prev], remain = K - i - 1;
            
            ans += (csum) * (remain / T);
            
            for(int j = 0; j < remain % T; ++j){
                mod = (ans % N);
                ans += A[mod];
            }
            break;
        }
        
        visit[mod] = i;
        
    }
    
    cout << ans << endl;
}

NAIST 体験記

注意事項

この記事は、奈良先端大の卒業記念ポエムです。

個人的な体験談に基づく感想である点にご留意ください。また、身バレとブログの文章量を抑えるため、ところどころ適当に書いています。詳しく知りたい！という方がいれば、Twitterやブログのコメント欄にてお知らせください。

また，この記事で述べられているイベント(e.g., ご飯を食べに行った，ラーメン屋に行った)などは，コロナによって不要不急の外出が禁じられている時期に行われたものではありません．

はじめに

NAIST受験記 - 予鈴 を書いてから2年と少しが経ち、奈良先端大を 3/24日に無事卒業することができました。大学、大学院ともに情報工学を専攻し，ソフトウェア寄りの研究を行っていました。

NAISTの環境（物理）

アクセスといろいろな環境とか

2年間実家（大阪の隣の県）から電車と徒歩で奈良まで通っていました。寮に住んでいる方の体験記はありますが，実家通いから見たNAISTの環境の体験記は少ないと思うため，この機会に書き残そうと思います．

NAISTは最寄り駅の学研北生駒駅から徒歩20分程度の場所に位置しています。NAISTまでのアクセスですが，最寄り駅の学研北生駒はそこまで便利な駅ではないし*1、奈良先に向かうバスの本数も多くないので、はっきり言うと便利ではありません。加えて、学研北生駒　→　奈良先端までは上り坂と下り坂です．夏場は歩くと汗が止まらなくなります．

アクセスとは少し異なりますが，キャンパスは大自然に囲まれています．情報棟を出て真っ先に目に映るのは，自然豊かな緑です．夏場はカエルの大合唱が聞こえたりします．(余談ですが、運が良ければうさぎ、白い鳥、たぬき、リスなどに出会えます*2。空気は毎日がキャンプ場です)

自宅から通う学生は，お弁当を持ち込むか，食堂で食べるか，あるいは周辺で何かを買うかのいずれかになると思います．残念なことに，学研北生駒駅からNAISTに向かう道までにコンビニは1軒しかありません。大学生や大学院生行きがちなお店（ラーメン屋やすき家）なども徒歩の圏内にはありません。あまり遊びにでかけない自分から見ても、便利とは言い難い環境でした．

ただ、車や電車を使うとそれなりに便利な環境にアクセスできます。（富雄とかイオンとか…

僕は車を持っている同期によく連れて行ってもらっていました．

実家が通いから見ても、まぁまぁ過酷な環境だったと思います。

食堂・コンビニ

上述の通り、周辺になにもないので食堂でご飯を食べたり，コンビニでご飯を買うことが多かったです。

どちらも規模は大きくありませんが、大学院大学であることを考えると十分だったと思います。食堂では、日替わりメニューと通常メニューがあります。僕は日替わりメニューの頼み方がわからなかったので、常に通常メニューを頼んでました。少し値が張りますが，カレーうどんがおすすめです．コンビニでは定期的に品物が入れ替わっており，飽きることはありませんでした．

図書館

修士２年間で積極的に用いることはありませんでした。ただ、修論執筆中などの極限精神状態でラボの作業が困難なときは時折使っていました。

学部時代の図書館がものすごく恵まれており（ここ）、ここと比較するとどうしても見劣りしてしますが、特に不便な点はありませんでした。個人的には、もう少し蔵書が多いと嬉しかったです。

NAISTでの環境（研究とか）

後にも述べますが、この章は筆者が所属していた研究室の感想になります．このあたりは，研究領域と研究室の色で大きく変わります．ご注意ください．

学校での生活

修士の間はかなり忙しかったと思います。個人差がかなりありますが，ざっくりと時系列順に並べると

M1: 入学　→　授業(前)　→　(夏休み) → 授業(後) →　チューター　→　中間発表　(M1終)

M2 : 就活　→　研究/授業 →　(夏休み) →　中間発表　→　修論 →　卒業

といった流れでした。ただ、この間にオープンキャンパスの準備（義務ではありません）やICPCに取り組んでいたため、体感的には大忙しでした.　授業を取っていた時期は特に忙しかったような気がしています．

また，人によってはかなり早い段階から就活・インターンに取り組んでいる人もいます．大学院はモラトリウムの延長と言われることもありますが，そこそこ本気で取り組むとモラトリムのモの字も無いような生活になると思います．

研究活動はこれらの合間を縫って進めなければなりません．大変でした．

授業

あまり詳しくは述べませんが、それなりに大変です。単位を落とすと研究活動にも支障を及ぼすので、できるだけM1の間に集めておいたほうが良いかもしれません。

CS系の授業はもちろんのこと、面白い授業が多かったです（サイバーセキュリティとか、理解するのは大変ですが）

おすすめは科学哲学です。今でも強く印象に残っています。残念ながらしょっぱい評価でしたが，内容自体はとても興味をひかれる内容でした．在校生の方はぜひ．

チューター

新しくNAISTに入学する留学生の諸々の手続きを手伝うやつです。

市役所に出向いて書類を一緒に書いたり、日用品の買い出しを手伝ったりします。日本語が得意ではない留学生もいるので、その場合は英語で説明することになります。入学に必用手続きは、そもそもかなり大変です。チューターの業務ではこの責任重大な手続きを英語縛りで行うことになります。

お給金的には……かなり損ですが、過去自分が短期留学したときはホストの国の人に助けてもらったので、その恩返しだと思ってやりました。間違いなく貴重な経験の一つだったので、もしチャンスがあればぜひ挑戦してみてください。プライスレスな経験でした。

中間発表

M1,M2のそれぞれ一度ずつコロキアムという中間発表があります。これがかなり大変です。

しっかり準備して望まないと、かなり厳しい質問愛のムチが飛んできます。

自分の場合，研究は締め切り駆動型だったので、コロキアムの1ヶ月前から研究そのものペースを上げてコロキアムに備えてました。

コロキアムは中間発表ですが，自分は研究をすすめるモチベにしていました．ある程度の期間で発表できる進捗を生むように研究を進めるのは大変でしたが，いいペースメーカだったのでは無いかと思います．研究を進めると全然だめなことがわかって進める以前にロールバックしたりしましたが...

中間発表は自分の発表番以外にも数回の視聴が義務付けられているので、必然的に自分の研究分野以外の研究も聞くことになります。同じ情報系といっても、研究の内容は全く違うことが多く、面白かったです。

（過去自分が参加したセッションでは、最初にセンサーを用いたような研究から、半導体関連の研究の発表まであり、レイヤー高低差にびっくりしたことに覚えています）

研究室

自分が所属していたのは下記のような研究室でした

• 研究分野はソフトウェア寄り
• コアタイムなし
• 週に一度に全体のミーティングが１時間ほど
• 別途細かいチームに別れてミーティングあり
• 研究室の運営はM1に役割が振られる（ウェブ更新係など）
• 留学生の比率は高め

進捗報告会なども無いため、自分自身から指導教員にミーティングをお願いする人が多かったです。自分は(締め切り駆動型で怠惰なので)不定期でミーティングを行っていました。

研究室の環境（物理）

環境としては、かなり恵まれていたと思います。研究室の設備だけ見ると，雰囲気はイケイケのベンチャー企業のようでした。

研究室から貸与されたディスプレイ(高くていいやつ）、Mac Book Pro, Mac miniに加えて、十分な性能のサーバーなどを利用することができました．研究分野的にGPUやCPUパワーで殴ることはなかったので，計算資源で困ることはありませんでした。

研究室の環境(not 物理)

留学生が多く，和気あいあいとした雰囲気でした．研究室内では英語・日本語・タイ語　の３つがよく用いられていましたが，いずれも完璧でなくてもよく，とりあえず喋ってみようという感じでした．英語が堪能でなくとも，コミュニケーションを取るだけならなんとかなります（個人の感想です）．

日本人学生が留学生とチームを組んで論文を書く　といったこともありました．

留学生と研究のディスカッション，論文の書き方などを議論するには，それなりの英語力が要求されます．良い経験でした．*3

研究室では積極的に論文投稿を行っており，ooがxxにアクセプトされたなどのニュースは日常茶飯事でした．特に有名なジャーナルの締め切り前などは，ラボのメンバーがoverleafの前で黙々と作業をしており，非常に活発な研究室だったと思います．

このような環境だったこともり，僕が所属していた研究室では，実験して論文を書くといったことは特別なことではなく，日常となっていました．殆どの学生が，修論を書くテーマ以外に別のテーマで研究を行っていました．

私生活

コロナウイルスによる諸々

自分が入学した頃(2020年）はコロナウイルスが猛威を奮っており、体感的には1/4程度の月日をオンラインで家から参加することになりました。授業のみならず、研究やミーティング、競プロコミュニティの活動や中間発表なども一部オンラインでした。

幸いにも，NAISTは授業アーカイブなどの設備があり，特に不便を感じるようなことはなかったです．ミーティングなどもZoomやwebexなどを用いて行えるようになっていました．対面での作業を強いられるようなことはありませんでした．

就活

就活なんかせんでええ！人生は冒険や！！

とは行かず，やはり就活には取り組む必要があります．僕は全くやる気が出なかったのですが、運良く声をかけてくださった企業があり、今はその企業で働いています．

所感ですが，就活に力を入れている人は多く，一度は聞いたことがある企業に内定をもらっている人が多かったです．

やる気がない自分でもなんとかなったので，就活はそこまで苦労しないかもしれません．

研究

卒業したので明かしますが，大学院への進学理由はモラトリウム・競プロ・研究の３つであり，全部平等に力を注ぐつもりでしたが，結果として多くの時間を研究に費やす事になりました．

やはり環境の力は大きく，自分もなにかせなあかんなという気持ちになり研究に向き合っていました．

最終的には，査読あり(英)と査読なし(日）に論文をそれぞれ提出し，後者は研究奨励賞をいただくことができました．両方とも，向き合っているときはかなり辛いお気持ちでしたが，研究室のメンバーや指導教員の先生方に助けてもらい，なんとか成果に繋げることができました．僕以外の同期のメンバーもなんやかんや体外発表や論文投稿を行っており，良く言えば刺激がある環境，悪く言えば，さぼればサボるほどプレッシャーが積もる環境だったと思います．

競プロ

主にプロコン部の活動とCodeforcesに参加していました．プロコン部ではICPCに参加し，予選敗北したり，Codeforcesでは青になったりしました．

ただ，学部のときのような精進はしていなくて，程よくお付きあいしていました，結果としてこれぐらいの距離感がちょうど良かったのかもしれません．

その他

箇条書きにします

・暇をしていたら，学内からソフトウェア開発のアルバイトのお誘いが来たのでやっていました．学内のプロジェクトだと研究との兼ね合いも取れて，お小遣いも稼ぐことができた非常に良かったです．

・土日にこっそり登校して，研究室で研究したり全然関係ないプログラムを書いたりしていました．コロナで人がいない時間帯に投稿するのが表向きの理由でしたが，関係なくこの習慣を続けていました．土日のNAISTは，穏やか空気が流れており，平和そのものでした．

・コロナ禍でイベント事は皆無だったのですが，同期とはコロナが落ち着いている時期だったり，などにご飯に行くことがあったり，誕生日を祝ったりしていました．これがなかったら精神的に落ち込んでいたかもしれません．

ロウソクの灯が2進数なのもすごい

C++を完全に理解できるよになる聖杯．誕生日プレゼントとしてもらいました

同期にとても恵まれた2年間でした．

その他

NAISTプロコンサークル

NAISTはサークルはほとんどありません．僕は，非公式のコミュニティであるNAISTプロコンサークルに所属していました．

コロナ禍でオフラインの活動が全滅気味でしたが，今も後輩くんが引き継いて活動を続けてくれています．

NAISTプロコンサークルでは，定期的にバチャを開きICPCの予選突破を目指しているコミュニティです．興味がある在校生の方はぜひ参加してください！

NAIST定点観測部

NAIST定点観測部では，あるポイントで写真を撮ってTwitterに投稿するのが伝統となっています．入部条件などは一切無いので，誰でも参加できます．

僕はかなり本気で取り組んでいました．特に気に入ってるやつをいくつか．

奥の木で季節感がわかるのが良いポイントです．

定点観測部　夏

定点観測部　秋

富雄

 生駒駅から二駅のところに富雄という駅がありますが，うまいラーメン屋がめちゃくちゃ多いです．コロナが落ち着いている頃に，同期に車に乗せてもらってよく食べに行っていました．

何がすごいって，マジで全部美味しいんです．在校生の方はぜひ．駅に近いラーメン屋さんも多いので，最悪車がなくてもいけます．

修論提出直後に食べたラーメン

店内で流れているBGMがB'z

土曜日だけつけ麺が食べられるのです

なぜかNAISTからすこし離れるとめちゃくちゃ美味しいお店が多いです．近くにあればいいのに...

まとめ

いかがでしたか？

NAISTでの２年間は大変かつ有意義であり，苦しみと充実感は排他的ではないのだなぁと強く痛感した期間でした．また，先輩・同期・後輩，指導教員に非常に恵まれたと感じています．仮に違う世界線でNAISTに入学しても，出会う人が違っていれば，異なる結末になっていたのかもしれません．このあたりは難しいなと感じています．もし入学を検討している方がいらしたら，在校生の方にたくさん話を聞いてみることをおすすめします．

この記事を読んで，NAISTに興味を持ってくれたり，NAISTを知った読者の方がいれば，これにまさる喜びはありません．もし機会があれば，ぜひNAIST を訪ねて見てください．

末筆ではありますが，NAISTでお世話になったすべての方々に，深く感謝いたします．

 

*1:近鉄を経由すると，２つ前の生駒駅で乗り換える必要があります．生駒駅から学研北生駒駅までの電車の本数も少ない...

*2:猫ちゃんは残念ながら天国に旅立ってしまったようです．悲しい．一匹は引き取られたようです。

*3:僕が書いた英文を，it doesn't make sense とつぶやきながら全部書き換えられたのはいい思いです．

E - Skiing と ポテンシャル

問題

atcoder.jp

解法の前のお勉強

辺のコストの持ち方以外は難しくない。制約的に、Dijkstra法を用いることで解ける。さて、問題はコストが負になりうるという点である。
Dijkstraのアルゴリズムは、負の辺があると動作しない。ならば、負の辺を消してしまえば良い。

具体的には、ポテンシャルという概念を導入する。
ここでは、ながたかなさんの記事とできるだけ同じ記法を使って説明してみる。下の参考文献にもリンクがあります。

（感覚的には、最短経路の性質が壊れないように、適当な値を加えて辺を変える。多分)

頂点 を結ぶ辺を とする。各頂点ごとにポテンシャルを考え、ポテンシャル導入した辺をを次のように定義する。ただし、変更後の辺はコストが正になってほしいので、ポテンシャルは次のようにしておく。

この辺を用いたときの最短経路の求め方をエミュレートしてみる。は、上で定義した辺()を用いたときの、始点からまでの最短距離を表す。

ここで、 と考えると

となって、置き換えると最短距離のまんまになる。辺のコストを書き換えただけなのに、元の辺のコストが現れた…だと

これだけだと? となるので、口語的な説明を追記してみる。

まずはじめに、との差は、のポテンシャルの差になる。頂点のポテンシャルの差分(始点と終点）のみに依存するため、変更後の辺()上で求めた最短路も、変更前の辺()上で求めた最短路になる。

始点と終点以外のポテンシャルの値は辺を移動するときに消えそうだな、という感じもするが、せっかくなのできちんと説明しておく。

さて、最終的にほしいのはではなく、ポテンシャルを導入する前の最短経路である。今までは始点を省略していたが、ここからは と のように記述することにする。

結論から言うと、 が成り立つ（らしい）。

正直全然わからないので、もう少し詳しく見てみる。

という最短路だったとしよう。とする。

一方で、

これを比較するとさっきの式がでる。
なるほど、たしかに端点だけを考慮するだけで良い。すごい。

解法

はい。それではようやく問題を解き始め
最大化なので、最小化に言い換えてDijkstra法を適用することにする。これに伴って、のときは, のときは と言い換えることができる。

さて、ここからポテンシャルを導入することを考える。

として、ポテンシャルを導入してみる。

のとき

のとき

良さそう。この辺を使って解くと問題が解が得られる。

解法

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

using Int = long long;
constexpr Int inf = (1LL  << 60);

inline Int potential(Int a, Int b,vector<Int>&H){
    
    if(H[a] > H[b])
    {
        return H[a] - H[b];
        
    } else
    {
        return 0LL;
    }
}

int main(){
    
    int N,M;
    cin >> N >> M;
    
    vector<Int>H(N);
    vector<vector<pair<int,Int>>>edge(N);
    
    for(auto& h : H){
        cin >> h;
    }
    
    for(int i = 0; i < M; ++i){
        int u,v; cin >> u >> v;
        --u; --v;
        edge[u].emplace_back(v,potential(v,u,H));
        edge[v].emplace_back(u,potential(u,v,H));
    }
    
    vector<Int>d(N,inf);
    d[0] = 0;
    
    priority_queue<pair<Int,int>,vector<pair<Int,int>>,greater<>> que;
    que.emplace(d[0],0);
    
    while(not que.empty()){
        auto [td,cv] = que.top();
        que.pop();
        
        if(d[cv]  <  td)
            continue;
        for(auto p : edge[cv]){
            int nv = p.first;
            Int cst = p.second;
            if(d[nv] <= cst + d[cv])
                continue;
            d[nv] = cst + d[cv];
            que.emplace( d[nv], nv);
        }
    }
    Int ans = 0;
    for(int i = 0; i < N; ++i)
        ans = max(ans, -1 * (d[i] - H[0] + H[i]));
    
    cout << ans << endl;
}

参考

すこし難しいがとても詳しい。
https://qiita.com/ngtkana/items/d7fc4463e56b966d1ebf

理解にとても役立った
niuez.hatenablog.com

やはり先人は偉大で、こういった記事で理解が何倍も早く進む。感謝します。

謝辞

この記事を書く（勉強する）に至って、Twitter上で質問に答えてくださった皆様に感謝します。
ありがとうございました。

D - Dance

問題

大事なところだけ抜粋すると、 を個の2つの組に分ける通り数答えよ。

atcoder.jp

解法

2つの組というところがミソで、うまく数え上げることができなかった。
例えば、{ (1,2), (3,4) } と{ (2,1), (3,4)} は同じになる。
これを回避するには、各要素の右端の数字が小さいように並べれば良い。
以下プロコン部のプロの引用

最も小さい値aと任意の数字b(a≠b)とでペアを作っていくことで遷移の途中で同じ結果の集合が生成されるのを回避できる
みたいなのはよくあるかもしれないです

確かに、各要素に何らかの順序関係を注入するとうまくいきそうな気がする。

実装は最近良く見る形の再帰。これぐらいの制約だと、再帰関数にvectorを値渡しでコピーしてもなんとかなりそうな気がするけど、再帰呼び出し前に条件を更新、呼び出し終了後にその条件を解く方針で実装した。正直まだこの形は苦手。

#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <algorithm>
#include <set>

using namespace std;
using Int = long long;
vector<vector<Int>>g;
vector<bool>used;

Int ans = -1;

void solve(Int tans = -1)
{
    if(find_if(used.begin(),used.end(),[](bool res) { return !res;}) == used.end())
    {
        ans = max(ans,tans); return;
    }
    
    for(int i = 0; i < used.size(); ++i)
    {
        // 未使用で最も小さい値を探す
        if(not used[i])
        {   
            //ペアの数字は適当に選ぶ
            for(int j = i + 1; j < used.size(); ++j)
            {
                if(not used[j])
                {
                    used[i] = used[j] = true;
                    solve((tans == -1 ? g[i][j]  : (tans xor g[i][j])));
                    used[i] = used[j] = false;
                }
            }
            break;
        }
    }
}
int main()
{
    Int N; cin >> N;
    g = vector<vector<Int>>(2 * N,vector<Int>(2* N,-1));
    
    used = vector<bool>(2 * N, false);
  
    for(int i = 0; i < 2 * N - 1; ++i)
    {
        for(int j = 0; j <= 2 * N - 1; ++j)
        {
            if(j <= i)
                g[i][j] = -1;
            else
                cin >> g[i][j];
        }
    }
    
    solve();
    
    cout << ans << endl;
}

B - Count 1's

問題

長さの数列が与えられる。
の連続する部分列を一つ選び、これを一度flipする。
スコアをに含まれる1の個数とするとき、の取りうる値が何通りあるか求めよ。

atcoder.jp

考えたこと

・答えの候補はたかだか程度なので、全部試せる
・最大値さえわかれば良さそう
・どうやって最大値求めるんだ…？

解法

まず方針として、1の個数を最大にできる場合と、1の個数を最小にできる2つがわかれば良い 。
変化量だけ考えればよいという感じ。をflipしたときに、1の数が増える/ 減る分のだけを考えるという感じ。つまり、flipしたところ・しなかった部分をわざわざ数え上げる必要はない。これも思いつけませんでした。

このは累積和を用いると高速に求めることができる。
まずはじめに、flipするという操作を言い換えると、1→0 ,0→1となるなので、元の数列に対して、1 → -1, 0→ +1　とした数列を考えて、累積和を計算する。

このままだとただの累積和で、を指定することで、その区間をflipしたときの1の数がでわかるが、制約からを全探索はできない。

ここで、のみを全探索して効率的に求める方法を考える。
累積和の配列をとすれば、は0からまでの和となる。
問題は、が最大となる を探し出したい。
これは、はより前に現れているはずなんで、でが最も小さいものを記録しておけば良い。

最小値も同様。

感想

(解説に1 の個数を最小/最大で何個にできるか，は簡単に求まりますとあるが、自分にとっては簡単ではなかった)
難しいと思う。ちなみに公式の紙の解説よりも、ビデオのほうがわかりやすい。

最大値と最小値の間の値はすべて取れるのか、というのも考える必要があるが、これは自分の場合は素直に理解できた。グラフを書くとなめらかになるので、その間の数字は全部取れるだろ、みたいな。

#include <iostream>
#include <vector>

using namespace std;

using Int = long long;

int main()
{
    Int N; cin >> N;
    vector<int>A(N);
    
    for(auto& e : A)
        cin >> e;
    
    int maxm = 0, mini = 0;
    int prevMax = 0, prevMin = 0;
    
    int csum = 0;
    for(auto cur : A)
    {
        csum += (cur == 0 ? 1 : -1);
      
        maxm = max(maxm,csum - prevMin);
        mini = min(mini,csum - prevMax);
        
        prevMin = min(prevMin, csum);
        prevMax = max(prevMax, csum);
        
    }
    
    cout << maxm - mini + 1 << endl;
}