多い&難しい気がするが、思いつくままに……
線形代数の授業でやるような掃き出し法を、 行
列の行列で、左側を上位ビットとみなすイメージでやる。
すると、総XORで作れる要素を昇順に並べたときに 番目に来るような要素について、
の
ビット目が経っている場合、基底の（2進数で見たときに）小さい方から
番目を選ぶ感じでやると構成できる。
ビット間の強弱関係（あるビットがたっているときにそれより下位のビットがすべて立っていても2進数で見ると真に小さい）と、基底間の強弱関係（ある基底が含まれるときにその基底より下位の基底たちで作れるどんな要素も総XORは小さくなる）が対応するイメージ。
掃き出しそのものはchmin(v, v ^ b)でできることに思いを馳せると以下のような実装になる。
#include "my_template.hpp" using namespace std; int main() { INT(N); I64(L, R); VEC(i64, A, N); vector<i64> base; REP(i, LEN(A)) { // i行目の基底を見つける i64 mx = MAX(A); if (mx == 0) break; // それより上の行の基底を掃き出す FORE(b, base) chmin(b, b ^ mx); base.push_back(mx); // それより下の行の基底を掃き出す(上の行の基底だったものは0になっている) FORE(v, A) chmin(v, v ^ mx); } // ビットの大小関係と基底の大小関係を揃える REV(base); L--; vector<i64> ans; REP(k, L, R) { i64 e = 0; REP(i, LEN(base)) { if (k >> i & 1) { e ^= base[i]; } } ans.push_back(e); } print(ans); return 0; }
noshi基底はすぐに思いついたためただの基底の組の1つはすぐに求められたが、そこから基底の大小関係とビットの大小関係を対応させること、そしてそのような基底がnoshi基底に少し変更を加える方法や線形代数の授業でやるような普通の掃き出し法で求められることがわからなかった。
2022年9月に友人に誘われてVALORANTというゲームを始めたのですが、1年とちょっとかけてようやくゴールド1になることができました。
何をしたかや今の自分の考えを整理しておくためにも、約1年間を振り返る記事を書こうと思います。
| モード | プレイ時間（時間） |
|---|---|
| コンペティティブ | 154 |
| アンレート | 229 |
| デスマッチ | 115 |
| チームデスマッチ | 33 |
| その他 | 7 |
| 合計 | 538 |
もともとVALORANTに限らず複数人でできる様々なゲームをプレイする友人グループがあり、その中でVALORANTが流行したことがゲームを開始したきっかけでした。
開始前はFPSゲームをほぼプレイしたことがなく（強いて言えばLeft 4 Dead 2を数時間やった程度）、対人FPSに至っては全く経験がないという状態でした。そもそもキーボードとマウスを用いたアクションゲームでさえMinecraftを多少やった程度です。しかしDiscordの通話に参加するたびに皆がVALORANTをやっているというような状況だったため、せっかくの機会だと思って始めました。
最初は他FPSゲームの経験がある友人等に教わりながらキーボードとマウスの操作に慣れつつ、ゲームのルールを理解しつつという感じでした。 ただ自分もPCゲーム自体はしていたこともあり、マウス・キーボード・マウスパッドなどのデバイスはこのときからある程度揃っていました。現在でもマウスパッド以外は同じものを利用しています。
（ところでその友人グループの構成員は10人くらいなのですが、ほとんどが小学校か幼稚園からの付き合いで、ここまで長いのはなかなかすごいなと思います。）
レベルが20を超えたため（40くらいあったかも）、コンペティティブに参加するようになりました。 友人グループのメンバーとデュオやフルパで参加したり、日によってはソロで参加することもありました。
認定戦はアイアン3でしたが、ブロンズに上がることはできず、さらに年明けくらいに9連敗してアイアン2に落ち、ショックを受けてそこからしばらくコンペティティブには参加しませんでした。（友人らと通話する際にアンレートに参加する程度になりました。）
大会などを見ていてVALORANT熱が再燃したこともあり、コンペティティブに再び参加するようになりました。 ほぼソロ参加でしたが、それまで4か月くらい参加していなかったうちに上達したためか、アイアン帯はスムーズに抜けることができました。
アンレートや大会の観戦を通してある程度各キャラクターの役割やスキルの効果を理解していたため、この頃は合わせピック的にイニシエーターやコントローラーのキャラをピックすることが多かったと思います。 このようなロールは一般にスコアが伸びにくいと言われていますが、撃ち合いについてもロールとして求められる程度には勝てていたため回数をこなすうちにランクは上昇していきました。
余談ですが、この頃は補助輪クロスヘアと呼ばれる移動エラーが可視化されるクロスヘアを使っていた気がします。
ついにシルバー帯に突入しました。友人らの多くはこのランク帯であるため、アンレートなどを友人らとプレイする際にはあまり困らなくなっていたのですが、友人らに勝ちたいという気持ちもあり、より上のランクを目指そうと思い参加を続けていました。
しかしシルバー2に突入したあたりから、試合に勝利した際にもらえるポイント数が、試合に敗北した際に減少するポイント数を下回り、長期的に見るとランクが下がるという現象が発生するようになりました。
上記のリンクに詳しくは記載されていますが、VALORANTにはRR（ランクレーティング）とは別にMMR（マッチメイキングレーティング・内部レート）というものが存在し、試合後のRRの変動値はMMRに近づく方向に補正がかけられるようになっているそうです。
また、tracker.ggというVALORANTのスコアなどを確認できるサイトで最近Tracker Scoreというものを閲覧できるようになりました。これは仮説ですが、MMRとRRの差分が大きい（つまりMMRにRRが追い付いておらず勝利時の獲得ポイントが大きい）際にはTracker Scoreも高いような気がしています。 実際、シルバー2で停滞していた際にはTracker Scoreは低かったですが、スムーズにランクを上げることができたブロンズの頃やゴールド1になった現在はそれに比べると高めです。
MMRを上げるためにはスキルの点で他のプレイヤーを上回る必要があるそうです。 ここで、Tracker ScoreはRound Win %、KAST、ACS、DDΔ/Roundの4つの要素から成り立っていますが、このうち後者3つは個人の成績によるものです。つまり先ほどの仮説（MMRとTracker Scoreに相関がある）を適用すると、MMRを上げるためにはTracker Scoreを上げる必要がある、すなわち個人の成績を上げることで、他のプレイヤーを上回ることができると考えられます。
実際、巷でよく言われる「ランクを上げるためにはデュエリストを使え！」という言説も、適切な構成の戦いならばデュエリストがまず撃ち合うことが多く、また他のプレイヤーからのスキルなどによる支援もあり個人の成績が伸びやすいことからこの考察と一致していると考えられます。
また、この頃ももっぱらソロで参加していたのですが、合わせピック的にイニシエーターやコントローラーをピックした結果、エージェントの練度が足りず、味方とスキルのタイミングを合わせることができず、連携力で相手チームに負けていると感じることもありました。
ということで、以下のようにプレイ方針を変更しました。
上記で述べた考察によれば、デュエリストをピックするのが順当であると思われますが、最近のデュエリストの弱体化（主にジェット・レイズ）やソロ参加における連携の難しさ、そもそも自分がデュエリストというロールに慣れていないことなどの要因により、センチネルを中心にピックすることにしました。
センチネルはデュエリストよりも個人の成績は伸びにくいですが、それでも
など、ソロ参加でランクを上げる際に有効である点があります。（最後の点は完全に個人的な事情ですが）
具体的にはキルジョイ・サイファー・ヴァイパーを中心にピックすることにしました。（ヴァイパーはコントローラーですが、スキルがセンチネルに似ています。ただし2コントローラー構成はコンペティティブでは連携が難しいためブリーズでのみピックするようにしていました。）
センチネルというエイム力が個人の成績に直結するロールを選んだ以上、エイム力を鍛える必要があります。 以下のような点に注意しました。
正直効果があったのかわかりませんが
というメニューから
にウォーミングアップのメニューを変更しました。
もともとのウォーミングアップメニューはプロゲーマーであるLazさんの以下の動画を参考に行っていましたが、チームデスマッチの登場や、初心者であり伸びしろが多岐にわたるため様々なメニューをやるほうが良いのではないかと考えたことによる変更でした。
KovaaK'sというエイム練習に特化したゲームがあります（1000円くらい）。
Aimlabsにしなかった理由は、プロゲーマーであるGONさんの以下の動画のプレイリストをやるためです（こういう時にとりあえず有名なものを試しがち）。
このプレイリストにはトラッキング系とスイッチング系とフリック系がありますが、特に効果を感じたのはトラッキング系の練習メニューです。
トラッキング系の練習はVALORANTの射撃場では練習が難しいですが、壁から少し離れたところにエイムを維持しながら移動する際など、重要な場面は多いと感じました。 逆にスイッチングの練習は、KovaaK's上ではリコイルの必要がないため、初心者にとっては変なリコイルの癖がついてしまうかもしれません（つきました）。 フリック系の練習は射撃場でもできるのかなと思います。
無音でデスマッチを行ったり、カスタムで練習しました。 カスタムではサイファーを選択し、ワイヤーでヘッドラインを確認しつつ、ケージで壁越しにエイムを合わせる練習を行いました。 また、この練習においては、ゆっくりとやりすぎないことを意識しました。（実践でもゆっくりすぎて痛い目を見たことがある）
もともと特に意識していなかったため、かぶせ持ちのような持ち方をしていたのですが、つまみ持ちに変更しました。
細かい点ですが、以下のことも注意するようにしました。
自分のプレイを見返したり、他人のプレイを参考にする際に、そのプレイが強い理由を言語化できるように意識しました。 定点動画の普及などにより、「理由は知らないが各エージェントの強い動きは知っている」という場合は多くあり（特にセンチネルのセットアップはそう）、その理由を言語化することで、試合中に選択を迫られた際に良い動きができることが増えたと感じています。
センチネルだと別行動をすることも多いため、本陣に状況を伝えるためにもVCは効果的だと思います。 また、ラウンド中のVCはエイムへの影響が多少なりともあると思いますが、ラウンド開始前に初動について提案するのはエイムへの影響が少なく、かつ効果的だと感じました。
深夜には怖い人の割合が増えると感じます。
調子が悪い日はあります。
これらのプレイ方針の変更により、VALORANTにおける運の要素が以前より減り、個人練習で鍛えられる要素が個人の成績に大きく影響するようなゲームへと変化していきました。 その結果、伸び悩んでいたころは300程度であったTracker Scoreが600程度まで上がり、ゴールド1になることができました。
FPSというジャンルのゲームをプレイしたことがありませんでしたが、練習方法などを自分で考えて実行することでゴールド1になることができました。割合としては上位50%程度であり、決してすごいランクというわけではないですが、練習方法を考えて実行するという一連の流れにおいては学びがあったように思います。
これらの練習方法を続けることなど、個人的にはまだ伸びしろがあると思っているので、もう少し上のランクを目指してみようかなと思っています。
最後になりますが、ある著名な競技プログラマの方が書いたブログ記事（現在は非公開になっています）の一部にこの記事と類似する内容が記載されていました。
もともとVALORANTをプレイする上で気を付ける点や練習方法について書いた個人的なメモがあり、今回の記事はその内容を参考にしながら書いたものです。そのため、真似たわけではなく偶然似たような内容になってしまっただけなのですが（競技プログラマの色変記事における練習方法論が同じくらいの色では似たようなものになるのと同じ現象だと思っています）、この記事を書くにあたりふと記事の存在を思い出し内容を確認したところ、類似する内容が記載されており驚いた次第です。
もし内容に問題がありましたらご連絡くださると幸いです。よろしくお願いします。
ICPC 2023 Asia Yokohama Regional に pointN さん、niuez さん、ruthen で Big O of N cubed として参加しました。
国内予選までについては以下の記事を参照してください。
ICPC 2023 国内予選 参加記 (ruthen 視点)
10 月中旬ごろから毎週末のどちらかに 5 時間のバーチャルコンテストを走っていました。
走ったセット（時系列順）
ライブラリに関しては国内予選と同じものを使用し、その際に追加でいくつか印刷しておいた資料についてもそのまま持っていきました。
ホテルについては、横浜 DeNA ベイスターズ ファンフェスティバル 2023 の影響なのか予約がかなり埋まっていました。早めにとることをおすすめします。
11 時に秋葉原駅に集合し、その後関内駅で降りて横浜中華街で昼食を食べました。 その後 13 時半くらいに受付を済ませ、14 時から開会式→ルール説明→リハーサル→チーム紹介の順で進みました。
ルール説明では、英語を聞き取るのが大変だったので手元の資料を読んでいました。トイレに行くのにも申告が必要だったり、Day 2 ではコンテスト開始前に使わない荷物はすべて袋に入れることなど、ここで初めて知ったルールも結構ありました。
リハーサルでは、CLion の使い方や印刷の仕方やジャッジシステムの仕様を確認しました。 想定よりジャッジシステムの性能が良くて TLE 想定のコードが AC してしまうことがありました。
チーム紹介は無難に真面目路線で行った方が良いです。（マイクの声が聞き取りにくく、ネタを考えてきても伝わらない可能性が高いです。）
その後夕食を再び横浜中華街で済ませ、ホテルにチェックインして解散となりました。 ABC が開始する前に寝ました。（起きた後に問題を確認しました。）
6 時くらいに起き、ホテルで朝食を済ませ、8 時過ぎにコーチや筑波大学のもう一つのチームであるGoodBye2023 のメンバーと合流しました。
会場に入るとお菓子が入った袋が置かれていましたが、それ以外は Day 1 と変わりませんでした。 （具体的な時刻は覚えていませんが、お弁当も昼過ぎに配布されました。） 特に遅延などはなくコンテストが始まりました。
※コンテストから数日が経過しているので一部の記憶が曖昧です。
国内予選では ruthen がセットアップと A を、pointN さんが B を、niuez さんが C 以降を読むことにしていましたが、今回は ruthen がセットアップを行い、niuez さんが A を、pointN さんが B やそれ以降を読むことにしました。 これは問題文が封筒に入っており開始直後から A 問題を読めるため、また、セットアップが国内予選と比べてやや面倒であるためです。
セットアップが終わったら niuez さんが A を解けていたのでパソコンを渡し、AC。 B は pointN さんが読んでいましたがぱっと見わからないとのことだったので、niuez さんも B に参加し、ruthen は C 以降を読むことにします。
niuez さんが B は遅延セグメント木を使えば解けると言っていたので、実装を任せ、pointN さんと ruthen は問題に目を通していきます。
その頃順位表では F が通されていたので、pointN さんが読むと解法がわかり、内容を聞いて良さそうだったので B を通した niuez さんに F の解法を説明して実装してもらいます。F はすぐに通りました。
自分は CH あたりを読んでいましたが解けておらず、順位表を見ると DEK あたりが（たしか）解かれており、D は pointN さんが読んでいたので内容を聞きます。
区間 DP で行けそうとなり、 かかりそうだなと思いつつ、
が小さめなので間に合うかもしれないということで niuez さんが実装を開始します。（当時 ruthen は反復回数が 1 桁であることを見落としていました。）
その間にだいたいすべての問題に目を通し終え、EGK あたりを中心に考えていきます。 D が通ると EG よりも K が解かれていたので、K を考えます。
インタラクティブ問題で、幅 199 おきにクエリを投げることによって大まかな位置を特定するところまでは良いですが、そのあと正確な位置を特定する際に三分探索などが必要になりそうでクエリ回数が足りない、みたいな話になります。 最終的に pointN さんが幅 1 だけずらしてクエリを投げ、算数をすることで解く方針を考えたため、実装を任せます。
その後は（自分はあまり理解できていなかったのですが）G を考察していた niuez さんの話を聞いたり、E を考察していました。すると突然 E の BitDP 解が生えます。（この時は でした。）
niuez さんに相談したところ、
に落ちたので実装を開始します。
E に提出しますが TLE で、コードを印刷して高速化について考えます。
おそらくこの前後に K が通り、チームとしては E の高速化と G の解法を並行して考えます。
E については最終的に定数倍高速化手法をいくつか試したところ通りました。非想定だと思って についてしばらく考えていたのですが、もうすこし早く試しても良かったと反省しています。
その後 G に取り組みます。自分は E に取り組んでいたこともあり解法を理解していなかったのですが、niuez さんが TLE すると言いつつコードが書きあがっていたので、提出してみることを提案し、ジャッジ結果を確認したところ WA が返ってきてしまいました。その後少ししてコンテストが終了しました。
コンテスト後はスポンサー企業の紹介→問題の解説→ Yes/No の順で進みました。 Big O of N cubed は 6 完で 27 位でした。台湾勢のチーム数を踏まえると国内予選とほぼ同じ順位という感じですね。
pointN さんが 位だということに気づいており少し感動していました。
GoodBye2023 は 9 完して 9 位になっており、すごいな～と思いました。
懇親会では食事をいただき、いくつかの企業ブースも見に行きました。 過去にインターンとして参加させていただいた企業も参加しており、（当時直接お世話になった方はいませんでしたが）挨拶もすることができて良いものとなりました。 他にも何人か初めて話すことができた方がいたため非常に満足したものとなりました。 会場で配られる名札には本名しか書かれていないため、ハンドルネームが書かれた名札を持参するのがおすすめです。
B1 の秋に競技プログラミングをはじめ、ICPC のアジア大会には合計で 3 回出場することができました。 うち 2 回はオンライン実施であったため、今回初めてのオンサイトは新鮮でとても楽しかったです。 大会運営に関わってくださった全ての方々、そして、会場にはいなかった方も含めすべての競技プログラマの皆様、ありがとうございます。
私は現在 M1 で早生まれでもないため、これで ICPC は引退となります。 競技プログラミングの活動としては一区切りつきますが、今後もコンテスト等には参加していこうと思っています。 また、作問方面で協力できることは少ないかもしれませんが、JAG に入るなどして少しずつ競技プログラミング界隈に恩返し出来たら良いなと考えています。
これからもどうぞよろしくお願いいたします。
Macbook Air Apple M2 を購入し、競プロの環境構築中に遭遇したエラー。
すでに Homebrew で gcc をインストールしており、g++ で clang ではなく gcc が呼び出されているようになっている。（Homebrew GCC 13.2.0）
#include <vector> int main() { std::vector<int> a; return 0; }
std::vector を使おうとするとエラーが出る。
% g++ main.cpp ld: warning: ignoring duplicate libraries: '-lgcc' 0 0x104f77648 __assert_rtn + 72 1 0x104eabfac ld::AtomPlacement::findAtom(unsigned char, unsigned long long, ld::AtomPlacement::AtomLoc const*&, long long&) const + 1204 2 0x104ec1924 ld::InputFiles::SliceParser::parseObjectFile(mach_o::Header const*) const + 15164 3 0x104ecee30 ld::InputFiles::parseAllFiles(void (ld::AtomFile const*) block_pointer)::$_7::operator()(unsigned long, ld::FileInfo const&) const + 420 4 0x184138440 _dispatch_client_callout2 + 20 5 0x18414bf1c _dispatch_apply_invoke + 224 6 0x184138400 _dispatch_client_callout + 20 7 0x184149fb8 _dispatch_root_queue_drain + 684 8 0x18414a6c0 _dispatch_worker_thread2 + 164 9 0x1842e4038 _pthread_wqthread + 228 ld: Assertion failed: (resultIndex < sectData.atoms.size()), function findAtom, file Relocations.cpp, line 1336. collect2: error: ld returned 1 exit status
ld: Assertion failed: (resultIndex < sectData.atoms.size()) にもあるように、リンカーのバグで、Xcode 15 以上で発生するらしい。 スレッドの開始日がこの記事を書いた 1 週間前くらいで、かなり最近発生したバグっぽい。
GitHub の issue にあった解決策を試した。
結局のところ Xcode 14 以前なら大丈夫っぽいので、-ld_classic をつけてコンパイルすれば良い。
brew reinstall -sv gcc すればオプション無しでも大丈夫らしい（が、時間がかかるようなので実行していない）。
ICPC 2023 国内予選に pointN さん、niuez さん、ruthen で Big O of N cubed として参加しました。
チーム名の由来は 3 人ともハンドルネームに N が含まれていたためです。
今年の4月下旬くらいにチームが決まり、毎週末のどちらかを主な練習日に充てました。
走ったセット（時系列順）
模擬国内2023の結果は現役内では23位でした。（参考）
ライブラリに関しては、持っている量が圧倒的だったこともありほぼ niuez さんに丸投げしてしまいました。（ありがとう……。）
パソコンは ruthen のものを（新しいアカウントを作り）、キーボードとマウスは niuez さんのものを（練習・本番ともに）使いました。
エディタは CLion をしばらく使っていましたが動作が重く、一部の拡張機能の利用が認められたこともあり途中から VSCode に切り替えました。
必要なライブラリの印刷は既に済ませていましたが、kazoeage.pdf や seisuuron.pdf などを追加で印刷しました。
直近にチームで走った模擬国内2020バチャのupsolveとして、F アローダイスを通して寝ました。
14時くらいに大学の計算機室に集合しました。 国内予選のために他の部屋からプリンタを移動するなどの作業があったため、その手伝いなどをしていました。
初動については、ruthen が問題文を印刷し、そのまま A に取り組み、pointN さんが B を読み、niuez さんが問題を切り分けつつ C 以降に目を通すというところまでは練習時に決めていたため、その通りに動きます。
問題はこちら
A は特に難しいところはなかったため、問題なく AC しました。 かなり急いだつもりではありましたが、それでも全体 FA とは 2 分半ほどの差がありました。
pointN さんが B を読み終えたのでパソコンを渡して、自分は C を読みます。
構築問題で、 程度距離を開けながら配置していけばよさそうでしたが詰め切れず、D を読み終えた niuez さんから D の概要を聞きます。
概要を聞いて割とすぐに、個数制限付きナップサックで 2 べきに分割するテクニックを使うことで、答えの上界が 7 であることに気づきます。つまり 6 以下を全探索すれば良いということが分かります。
そこで niuez さんが候補の集合は集合の要素の和が になるため、5 つの要素を確定させれば残り 1 つは決まるということに気づきます。
ここで、答えの集合の最小の要素と、作るべき値の集合の 0 より大きい最小の要素が一致するため、4 要素を全探索すれば良いという嘘考察を生やしてしまいます。
その頃 B が AC したこともあり、pointN さんに C の概要を投げて、niuez さんが D の実装を始めます。 デバッグなどを終えて D を提出してみると WA が出たため、コードを印刷してデバッグを開始し、その間に pointN さんに C の実装を任せます。
D の実行があまりにも高速に終わったため、別に 5 要素を全探索しても良いのでは、ということで実装を変更したところ AC します。
その後 C も pointN さんが AC します。（完全に丸投げしたのに通していてすごい。）
E の AC 数が F より多かったため、E を考えます。
ぱっと見で の DP が思いつきますが、それ以上オーダーが落ちません。
しばらくして niuez さんが dp[i][y] = i 番目の要素の y 座標を y に固定し、x 座標は動かさない時の最小コスト というような DP を考案し（多分）、遷移を式変形して観察すると Range Minimum Query の Segment Tree で解けるということで実装を開始します。
実装を見つつ、ruthen と pointN さんは他の解法がないかを考えます。その後終了 30 分前くらいに、pointN さんが dp[i][c] = i 番目までの位置を決めており、現在のコストが c のときの最大の (x, y) の位置 という DP を考案します。
niuez さんの解法はやや複雑だが実装はデバッグだけという段階であり、pointN さんの解法は簡潔だがまだ実装が全く進んでいないため残り時間で書きあがるかわからないという状態だったため、niuez さんと pointN さんが交互にパソコンで実装するという形になりました。そしてその結果どちらも実装が終わらないままコンテストが終了してしまいました。
結果は 23 位で、Yokohama への進出が決定しました。
今思えば 3 人目としての理想的なムーブは、2 人の解法をそれぞれ理解したうえで、pointN さんの解法を niuez さんに伝えてそちらに集中しようと提案することではあったのですが、仮に pointN さんの解法が正しいとすると E は通されてなさすぎるのではないかと思ってしまい、確信をもって動くことができませんでした。（それでも niuez さんに概要を伝えるべきではありましたが。）
とりあえず大学から 2 チーム出るという目標が達成できて良かったです。
他の 2 人に比べると実力が足りていない（というか、得意分野がない）と感じることが多いので、Yokohama までにはもっと練習しようと思います。
模擬国内2020D
公式解説以上の情報はありません。
普通の括弧列の場合は ( に +1 を、) に -1 を割り当てて、総和を 0 に、prefix sum が常に 0 以上となるかを判定する。
今回は、 ( に +2 を、) に -2 を原則割り当てるが、連続する 2 つの ( の組は +1+1 に、連続する 2 つの ) の組は -1-1 に割り当てることもでき、複数の組に同じ括弧を対応付けてはならないとして、同様の条件を満たすかを判定する問題である。
まず、必要な ) の個数について考える。
) は末尾に付けるだけで良い。なぜなら、付ける位置によらず全体の総和は不変であり、かつ prefix sum への影響を考えると、末尾以外の部分に付いているものを末尾に付けても損しないためである。
) を末尾に付けるとして、必要な ) の個数は、前から文字列を見ていき
( が出てきたらスタックにプッシュする) が出てきたら可能な限り 2 つの ( に対応させる（インデックスも保存すれば簡単に判定可能）上記のような貪欲法を行い、残った ( に ) を対応させることで、必要な ) の個数の下界が分かる。（提出コードのほうがわかりやすいかも。）
次に、必要な ( の個数について考えると、) の場合と同じことを文字列を反転させて行えば良い。
( の個数と ) の個数は独立に考えて良いため、この個数の和が答えの下界になる。
そして、この下界が実際に達成できることが証明できる。
らしいが、証明の仕方が分かりませんでした！いかがでしたか？
#include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i = 0; i < (n); i++) void solve(string S) { int N = int(S.size()); int ans = 0; REP(_, 2) { vector<pair<char, int>> T; REP(i, N) { if (S[i] == '(') { T.emplace_back('(', i); } else { int M = int(T.size()); if (M >= 2 and T[M - 2].first == '(' and T[M - 1].first == '(' and T[M - 2].second + 1 == T[M - 1].second) { T.pop_back(); T.pop_back(); } else if (M >= 1 and T.back().first == '(') { T.pop_back(); } else { T.emplace_back(')', i); } } } while (T.size() > 0 and T.back().first == '(') { int M = int(T.size()); if (M >= 2 and T[M - 2].first == '(' and T[M - 1].first == '(' and T[M - 2].second + 1 == T[M - 1].second) { T.pop_back(); T.pop_back(); ans++; } else if (T.back().first == '(') { T.pop_back(); ans++; } else { assert(0); } } string NS; REP(i, N) NS += S[N - 1 - i] == '(' ? ')' : '('; S = NS; } cout << ans << '\n'; } int main() { string S; while (cin >> S, S != "#") solve(S); return 0; }
