TCO10 Online Round 2

TopCoder

研究室の生き残りが自分だけとなってしまって若干心細いRound 2。

  • -

250. SnowPlow

問題：N個のノードからなる有向グラフがあって，i->jの枝がK本あればj->iの枝もK本ある。ノード0からスタートしてすべての枝を通るための最小コストは？通れない枝が存在する場合は-1を。

  • ノード0を含む連結成分についてはオイラーグラフになってる
    • 有向グラフは全てのノードについて入次数＝出次数ならオイラーグラフ
    • なので全ての枝を通れるなら枝の本数が答えになる
  • ノード0から到達できないノードに対して接続する枝があれば-1を返す。
  • しばらくオイラーグラフということに気付かず時間がかかってしまい206.55pt.

500. RepresentableNumbers

問題：各桁の数字が全て奇数であるような2つの数の和で表せる数をrepresentableという。与えられる整数X以上の数のうち、最小のrepresentableな数は？

  • とりあえずrepresentableな数は偶数
  • 小さい桁から順に見る事である数tがrepresentableかどうかは判定できる
    • t%10 == 0 : t/10 - 1がrepresentableかすべての桁が奇数かならtはrepresentable
    • t%10 != 0 : t/10 がrepresentableかすべての桁が奇数かならrepresentable
  • representableな数の間隔もそんなに大きく無いだろうと踏んでX以上の数を片っ端から調べた
    • 適当に作ったケースで110msのものがあったのでちょっと不安に
    • 適度にチャレンジもされてさらに不安に
  • 何とか通って310.60pt.

1000. BreakingChocolate

問題：サイズW×Hのチョコレートを分割していく。何個かは特別なチョコで，「チョコを一つ選び分割する」操作を繰り返して、チョコを特別なチョコだけからなる破片と特別なチョコを含まない破片に分けたい。必要な最小ステップ数は？

  • ちょっと考えて貪欲じゃない事は分かったので250と500をテストすることに。
  • 部屋で4人提出してたので実は簡単なのか…と思いきや全員Challengeで落ちてました。
  • -

結果：AC / AC / -- ，517.15pt, 176位
レーティング：1821 -> 1910

去年は部活の演奏会と被ったので不戦敗を選んだRound2。
今年は突破したいと思っていたので、まずは目標をクリアする事ができました。
今度はRound3が演奏会に被ったのですが、さてどうするか…。