読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

興味深い問題: 2014/10-12

興味深かった問題を記載しておきます。基準は

  • 問題設定が面白い
  • アプローチが面白い
  • 解法が面白い

などです。
ここでは開催日は2014年10月~12月の問題を紹介。

TopCoder SRM 636 Div1 Medium ClosestRabbit - kmjp's blog

  • 何かしらの期待値を足しこむという点までは推測できるが、その先が難しい。
  • ペアの期待値が最終的な答えになる、というアプローチが面白い。他の問題にあまり無い解法。

Bayan 2015 Contest Elimination: D - Towers - kmjp's blog

  • 高いブロックをまとめた方が良い、という推測は立つが、それをちゃんとアルゴリズムとして書き下すための考察が面白い。
  • 余り他の問題で見ないタイプの考察だった。

Bayan 2015 Contest Elimination: E - Water Barrels - kmjp's blog

  • 同時に複数の(最低位の)タンクに水がたまっていくという設定が自分には斬新だった。
  • 水を灌ぐ系の問題だと、こういう解法は割と一般的なのかな?

TopCoder SRM 637 Div1 Hard ConnectingGame - kmjp's blog

  • グリッドの境界線からグラフを作る、というフローの作り方が面白かった。
  • Div2 Hardもこれほどではないけどなかなか面白い。

Bayan 2015 Contest Warmup: F. Meta-universe - kmjp's blog

  • 同じ計算を繰り返すことを防ぐための、計算量の落とし方が面白かった。

TopCoder SRM 638 Div1 Hard CandleTimer、Div2 Hard CandleTimerEasy - kmjp's blog

  • 複数の蝋燭で時間を測る」というのはたまにクイズで出るけど、それに木構造を組み合わせていろんな時間を測る、という設定が面白かった。

K4PC : E - はじめての動的計画法(Easy Dynamic Programming) - kmjp's blog

  • 単なる典型問題の逆問題と見せかけて、解法のアプローチが面白かった。

K4PC : F - タイトル未定(Untitled) - kmjp's blog

  • 不等式をグラフの最短経路に落とし込めるのをすっかり忘れていた。
  • さらに先に累積和に対する最適解を求めたうえで、その後各座標の値を求める、というアプローチも勉強になった。

yukicoder : No.93 ペガサス - kmjp's blog

  • Nクイーンの変形というシンプルな問題ながら、挿入DPの状態遷移が面白い。

TopCoder SRM 642 Div1 Hard WheelofFortune - kmjp's blog

  • 「ある状態になる確率の期待値」と「得られるスコアの期待値」と異なる2値をDPしていくのが面白かった。

Good Bye 2014: E. New Year Domino - kmjp's blog

  • シンプルな問題設定でありながら、SegTree+ダブリングの使い分けという解法が面白かった。
広告を非表示にする