ARC141 C Bracket and Permutation
①順列Pにおいてj<iかつPj>Piなるjが存在するようなは')'で確定です。
②同じく、順列Qにおいてj<iかつPj<Piなるjが存在するようなは')'で確定です。
このようにして確定させた'('の個数はちょうどnでなければならないです。
'('を1、')'を-1に対応させたとき、一般に「正しい括弧列⇔累積和が常に0以上」が成り立ちます。
もしSiが')'にも関わらず①を満たさないとき、[P1,Pi]は[1,i]の並び替えになっています。が成り立つのでです。
②も満たさないとすると同様にです。この二つを足すととなりますが左辺は-1なので矛盾します。
よってSi=')'のとき上記上記の方法で必ず')'だと確定されます。
このように確定された')'以外を'('とすることでSは一つに定まります。
このようにして求めたSから貪欲に辞書順最小のもと最大のものを作り、P,Qに一致するか確認すれば終わりです。
プログラミング初心者が競プロを初めた時にやること
こんにちは。自分は去年(2020年)の4月、大学に入学してから競プロを始めました。それまではプログラミングもした事がなく完全に初心者の状態でしたが、1年経った今そこそこ問題も溶けるようになって来ました。(atcoder青とか)
そこで、去年自分が競プロ始めたての時にどのような方法で勉強していたかを雑に書こうと思います。よければ参考にしてください。(それぞれ要した時間を最後に書いてます)
①環境構築
適当に「競プロ 環境構築」とかでググッたら色々記事が出てくると思いますが、pcをイジイジしたことが無いと知らない単語も多く出てくるので誰かにやってもらった方がいいと思います。(たぶん部でやって貰えると思います)
②apg4b(名前を覚えていないがこの五文字の並び替えだった気がする)の1.2章を読む。
付属の問題はといて解かなくてもいいです。出力とか変数とか配列とか基本的な関数とかが書いてあります。boolとか再帰関数のとこはあんまり理解できなくて1ヶ月ぐらい放置していた記憶があります。for文を書けるようになることが一番重要で、for文かけたらABCのa.bは解けると思います。実際にコンテストの問題を解いてみるのも競プロをやっている事が実感できていいと思います。(①、②で2週間ぐらい)
③ABCのCを解きながらapg4bの残りを確認する。
ABCのCはfor文だけで解けない問題もあります。mapを使う問題とか自明な貪欲とか、多少計算量を気にしないといけない問題もあるので、問題を解きながらapg4bの残り(主に3章のSTLのコンテナ、pairの章)を読んで使い方を覚えます。(1週間ぐらい?)実力を付けてからコンテストに出たいという人も、ここら辺からは出るべきだと思います。順位と照らし合わせて自分の実力を知ることが出来ます。
④緑diffを埋める。主にABCのDを埋める。
ここが自分が一番推したいところです。緑diff埋めはかなり実力が着きました。緑diffがどんな分野でもある程度短時間で解けたら水色くらいの実力はフツーにあると思います。
累積和やらmodintやら二分探索やらdfs、bfs(のひねりのないバージョン)がでてきて、ここからはテクニックの話になります。正直すぐに理解するのが難しいものも多かったので、自分はすぬけさんの解説放送をかなり何回も繰り返し見ました。editorialより初心者向けに丁寧に解説してくれているので基礎が身についていればだいたい理解できると思います。実際にコーディングして下さるのがとてもありがたくてコードの書き方も初めはかなり参考にしていました。modintなどのライブラリも概要欄のリンクに貼ってあるので、解説放送で使い方を見ればすぐに使うことが出来ると思います。(1ヶ月ぐらい)
最初は問題をただとけばいいだけ、という訳にはいかず勉強の仕方が難しいと思いますが質問等あればいつでも答えられるのでDMとかで何でも聞いてください($・・)))/