エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
AtCoder ARC002 C-コマンド入力 の嘘解法について - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
AtCoder ARC002 C-コマンド入力 の嘘解法について - Qiita
のようなケースで誤りになることが公式解説において説明されています。 正解はL=AB,R=BAとすればLLRRと... のようなケースで誤りになることが公式解説において説明されています。 正解はL=AB,R=BAとすればLLRRと出来るので「4」ですが、 嘘解法ですと、LLBLAあるいはARBRRとなって「5」となってしまいます。 ただしこのようなケースがテスト項目に入っていないため、嘘解法でもACになります。 正しい解法 公式解説にある通り、動的計画法を用います。 自分は、i文字目を ・(j=0) L,Rで置き換えない場合の文字数 ・(j=1) Lで置き換えられて、置き換えた場合の文字数 ・(j=2) Rで置き換えられて、置き換えた場合の文字数 という3状態を作って解きました。 このdp表を dp[j][i]と書いています。 dp[0][i]は、1文字前の時点での文字数の最小値に+1した値です。