けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

stack

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (500 点)

区間反転操作問題シリーズ!!! それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

AtCoder AGC 005 B - Minimum Sum (400 点)

教育的な典型問題! 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…

AOJ 2931 括弧を語る数 (RUPC 2019 day3-B)

こういうのを頭混乱させずにきっちり素早く解ける人が、強い人なんだと思う。強くなりたい!!!!!! ということで教育的な楽しい問題!!! 問題へのリンク 問題概要 整合するカッコ列 があって、 から以下のように定義される長さ の順列 が与えれる: i …

AtCoder ABC 120 C - Unification (300 点)

久しぶりのカッコ列の整合判定問題!!! カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…

AtCoder ABC 064 D - Insertion (400 点)

教育的典型題 問題へのリンク 問題概要 カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。 制約 考えたこと 超定番。 AtCode…

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C)

こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…

AOJ 1188 階層民主主義 (ICPC 国内予選 2013 C)

超苦手系だと思いながら恐る恐る実装したら、ノーデバッグでサンプル全部通った上に、そのまま提出したら AC もらえて超ビックリしたん!!! パースして木構造作って木 DP 的なことをするのが主流かもだけど、なんかもっとアドホックにできたん。 問題への…

2018 codeFlyer 本選 C - 部分文字列と括弧 (500 点)

超定番の「対応がとれている」カッコ列を題材にした問題なん。色んな出題がやり尽くされてそうな中、まだこんなのが残っていたのんな!! ある文字列が与えられたときにそれが正しいカッコ列かどうか判定するのは、AGC 005 A - STring の方法でできるん。 今…

AtCoder AGC 005 A - STring (300 点)

超定番の stack を使うやつなのんな。類題として 2018 第4回ドワンゴからの挑戦状 予選 B - 2525文字列分解 ABC 064 D - Insertion AOJ 1173 世界の天秤 AOJ 2369 CatChecker AOJ 2490 () があるのん。これらは見た目は違えど、どれも "*1()())())()))(())" …