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

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

AtCoder Beginner Contest 119 C - Synthetic Kadomatsu

はじめに

  • AtCoderで解けなかった問題(AtCoder Beginner ContestのC問題、D問題が中心になると思います)を復習しています.

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

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


C - Synthetic Kadomatsu (300点)

概要

  • 竹が N本あり,その長さはそれぞれ l_{1},  l_{2}, ...,  l_{N}である
  • 目的:これらの竹を使って,長さ A B Cの3本の竹を作る
  • 3種類の魔法を任意の順に何度も使える
    • 延長:ある1本の竹の長さを1増やす.必要な MPは1
    • 短縮:ある1本の竹の長さが2以上である場合にその長さを1減らす.必要な MPは1
    • 合成:2本の竹を1本にする.その後も魔法を使える.必要な MPは10
  • 出力:目的を達成するために,必要な最小の MPを求める

読んだ解説のまとめ 1 2 3

  • 魔法は,合成を先にまとめて行って,必要に応じて延長や短縮を使用すればよい
    • それぞれの魔法をばらばらに実行するのと,上記の方法はほぼ等価なため
  • それぞれの竹は,竹 Aか竹 Bか竹 Cのいずれかで使用する場合と,全く使用しない場合の4通りがある
  • 制約条件から,最大でも 4^{8}=65,536通りしかない=全探索が可能
    • 以前見たりんご氏の解説によると,「使用する言語によって異なるものの,単純なループであれば1秒間で 10^{6} 10^{8}回計算できる」ため(要出典)
  • 深さ優先探索(dfs)で,竹の組み合わせと合成に必要な MPを計算
    • 組み合わせの全列挙が,この問題のキーポイント
  •  A B Cを作るのに,不足もしくは過剰な長さを延長もしくは短縮で調整する
  • 必要なMPの最小値を出力

実装のポイント

  • 再帰による組み合わせの全列挙
    • 基本ケース:再帰の深さが Nと等しいとき
    • 再帰ケース:竹 A B Cの構成要素かどうか,もしくは使用しないかの4通りについてdfsを並べる
    • 言語によっては,標準ライブラリを使用するという手もある
  • 再帰関数の引数・戻り値の例
    • 引数:再帰の呼び出し回数(再帰の深さ)
    • 引数:再帰関数を呼び出した時点での竹 A B Cの長さの合計値
    • 戻り値:必要な MPの合計値
  • 再帰ケースを呼び出すことにより,次の状態がどのように変化するかを一般化
    • 再帰の深さが1増える
    • ある竹 iが使用されない場合:竹 A B Cの長さの合計値はそのまま
    • ある竹iが使用される場合:竹 A B Cのいずれかの長さの合計値に加算する.最初の1本目以外は,必要な MPの合計値に10加算する
  • 合成後の長さの不足もしくは余りを調整する部分は,必要な竹 A B Cの長さとそれぞれの合成直後の長さとの差の絶対値を取る
  • 使う竹が1本も存在しない場合は,必要な MPを極端に大きな値として扱う(最小値とならないように例外的な処理をする)

筆者の到達度

  • それぞれの竹を選ぶかどうかを1(選ぶ)か0(選ばない)で管理する
  • 制約条件から最大でも 2^{8}通りしかない=dfsで全探索できそう
  • 各組み合わせとも合成を先にしてしまえばいい
  •  A B Cそれぞれについて,長さが足りないor余っている部分は後で調整すればよさそうだ
  • それぞれの竹を使って,長さがちょうど A B Cとなるように構成するするには, DPが必要?
    • ここで,自分の中での制限時間(1時間)が経過したため,解説を読むことに

想定解法と筆者の到達度とのギャップ

  • 必要な竹がどのように構成されるかという視点 vs それぞれ竹をどう使うかという視点
  • 再帰を使って,竹の組み合わせと長さ A B Cの竹を作るために必要なMPを,どのように管理すべきか思いつかず

ソースコードの一例

提出コード

得られた知見

  • ABCのC問題までは全探索で間に合う可能性が高い.数学的な解法やDPなどは,計算量の見積もりをしてからでも十分かも
  • 条件を整理して,操作の順番に依存しない部分/依存する部分をまとめる
  • 再帰ケースに直接,分岐条件を持たせるとシンプルに実装できる
  • 再帰の引数に,再帰の深さと求めたい状態を持たせる

感想

  • 再帰による全探索の基礎を学べて良かったです
  • 公式解説・解説ブログのコードを見て,その簡潔さと美しさに感動しました

つまづきポイント(○印が該当を表す)

問題 解けず 理解 発想 方針 実装
C

各項目の意味

  • 解けず:自力で解けたどうか
  • 理解:解法を理解するのに時間を要した問題
  • 発想:発想が難しい(思いつけば簡単)な問題
  • 方針:方針を見出すのが難しい問題
  • 実装:実装に手間取った問題

要復習・追加調査

  • 再帰のお気持ちを察することができるように,類題を解きまくる

参考

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