思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 064 D - Insertion

目次

結論

  • 辞書順最小とするには,'('が不足している場合は左端に追加したほうがよく,')'が不足している場合は右端に追加したほうがいい.

  • 括弧'('')'を整数の正負の扱いに変換して,一つの変数で管理する.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

D - Insertion (400点)

発想・解法とそれらを引きだすための方法・解釈

考察のキモ(Key Insight)は?

  • 対になる括弧がないときに,対応する括弧をどう追加するとよいか?

  • 辞書順最小とするには,'('が不足している場合は左端に追加したほうがよく,')'が不足している場合は右端に追加したほうがいい.辞書順だと'('が先に来て,')'が後に来るため.

どうしたら思いつけそうか?

  • 手を動かして書いてみる.

  • 辞書順という用の意味を知っている必要がある.

実装のポイントは?

  • 括弧が連続して登場回数を管理する変数を用意(筆者のコードの場合,count).

  • 文字列を順番に見ていき,'('が登場したときはcountを+1,')'が登場したときはcountを-1する.

  • 左端に'('を追加する必要があるのは,count=-1となったとき. その直後に左端に追加すべき個数を管理する変数を+1,countを0にする.

    • 例:(())))…条件を満たすために,左端に2個追加する必要がある.
  •  N文字見たあとに残っているcountの値が,右端に追加すべき')'の数.

    • 例:(((()…条件を満たすために,右端に3個追加する必要がある.

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    n = int(input())
    s = input()
    count = 0
    new_left = 0
    new_right = 0

    # See:
    # https://www.youtube.com/watch?v=5FOTOiV5p0U
    for si in s:
        if si == '(':
            count += 1
        else:
            count -= 1

            if count == -1:
                count = 0
                new_left += 1

    new_right = count

    print('(' * new_left + s + ')' * new_right)


if __name__ == '__main__':
    main()

得られた知識・知見

  • 括弧'('')'を整数の正負の扱いに変換して,一つの変数で管理する.

感想

  • Python3の標準ライブラリであるdequeで括弧そのものを追加・削除しようとして,ケース3で無限にバグらせてしまったのが反省点です.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/06/24 作成
  • 2019/0x/xx 更新