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

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

CPSCO2019 Session3 D - Decode RGB Sequence

f:id:hiro_kato:20190505231004j:plain

目次

はじめに

  • AtCoderの問題を復習しています.

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

想定読者

  • 筆者と同じくらいのレートの方:失敗談・回り道をみて,共感していただける部分もあるかもしれません.

  • コンテストのwriterの方:サンプル n=1ではありますが,レート茶色上位~緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません.

記事の狙い

  • 丁寧でわかりやすい解説記事がたくさん公開されているため,解法そのものについての記述は少ないと思います.

  • ACに至るまでにどうしてそのような発想に至ったのか,考察や実装で試行錯誤した過程(=失敗談や回り道)を重視しています.

  • また,得られた前提知識や着眼点について,今後応用できるように抽象化・言語化していきます.

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


問題のリンク

D - Decode RGB Sequence (400点)

提出コード

試行錯誤した過程

  • 文字列に対して,以前に得た着眼点として「後ろから順番に見る」を試した.

    • Rが連続して続く場合などで,うまく判定できなさそうと断念.

  • RGBの組み合わせについて,条件を満たすかどうかを方眼ノートに書き出した.

    • 前提条件:1文字目はRである必要がある.それ以外の場合は条件を満たさない.

    • 条件を満たす:RG+Bが1個以上ある.Rが1個以上+GBなど.単独でGが出現する場合も(サンプル3)

    • 条件を満たさない:Gが2個以上連続する,もしくはRBとなる場合.

  • 文字列の条件のチェックに尺取り法のようなアプローチが使えそうだと思った.

    • 用語を聞いた程度で,実装できず断念.

  • コーナーケースを2つ特定できず.

    • 先頭から3文字ずつ見る(計27パターン)を判定することも考えたが,場合分けで時間を要して断念.

    • ある3文字の左側・右側で必要な文字を列挙.この点については,想定解法につながる要素はあったものの,思いつかず.

得られた知識・知見

  • 条件分岐をいかに少なくシンプルにするか.

  • そのためには,条件を満たさない場合(もしくは条件を満たす場合)だけに着目できないか試す.反例がないか列挙する.

感想

  • 想定解法の鮮やかに感動しました.

  • 自分のようなレート帯にとっては,ものすごく教育的な問題だったと思います.

  • コンテスト中は,コーナーケースを2つ特定できず残念でした.

  • 解説PDFを見た瞬間,末尾がB以外となるケースを処理していなかったことに気がつきました.こういう部分を落とさないようにしたいと思います.

課題

派生問題という名の妄想(既出や不備などがありましたら,ご一報いただけると幸いです)

  • 長さ Nの文字列 Sが与えられる.文字列は'R''G''B'からなる.
  • 文字列'RGB'が何個含まれているかを求めよ. Sは,最終的な状態を表すため,上書きされている場合も含まれることに注意せよ.

参考

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