競技プログラミングにおけるインタラクティブ問題まとめ

インタラクティブ問題への取り組み方

• 最適戦略がある
• 二分探索・三分探索
• ビット毎に聞く
• 乱択

問題

• 最適戦略がある
  • CF440 Something with XOR Queries 解説
  • CSA64 Prime Factors
  • CSA64 Limited Moves
  • CF532 Dasha and Chess 解説（デバッグ辛い）
• 二分探索
  • yukicoder No.246 質問と回答
  • yukicoder No.253 ロウソクの長さ
  • CC Find an element in hidden array 解説
  • CSA64 Trailing Zeros
  • APC001 Vacant Seat 解説
  • CF503 The hat 解説
  • AC Majority of Balls 解説 （二分法と呼ぶ？）
• 三分探索
  • yukicoder No.594 壊れた宝物発見機 (整数で最小値)
  • LC1095 Find in Mountain Array （三分探索＋二分探索）
• ビット毎に聞く
  • CF427 The penguin's game 解説
  • AOJ 場所当てゲーム 解説
• 乱択
• 他
  • AtCoder ニワンゴくんの家探し
  • CF504 Down or Right
  • CF Guess the number（わからない）
  • AOJ 遭難 解説
  • HUPC2019E 最短経路の復元 解説