Codeforces Beta Round #33

Codeforces

久々にCodeforcesに参加し、初めてのCodeforces format。
結局はHackする事もされる事もなく、順位的にも平常営業に終わりました。

  • -

A. What is for dinner?

問題：m列に並ぶn個の歯があって各歯にはHPがある。食べ物1個を食べるには歯を1列使って、使った列の歯はもれなく1のダメージを受け、歯が1つでもHPが負になると歯医者に行かなきゃいけない。k個の食べ物が用意されてるとき、歯医者に行かずに食べれる最大数は？

  • nもmも最大1000。
  • ある列を使える回数は、その列に属する歯のうち最小のHPの値。
  • 各列について使える回数の合計と、kの小さい方が答え。

B. String Problem

問題：2つの文字列が与えられる。「文字aiをbiにコストciで置換する」という規則がいっぱい与えられて、その規則を好きな回数使って2つの文字列を同じものにするための最小コストを求める問題。同じものに出来ない場合は-1を出力。

  • とりあえず、2つの文字列の長さが異なったら同じ文字列にできない。
  • 同じにするには2つの文字列を先頭から比較して置換コストが小さい方に合わせれば良いよね…。
    • WrongAnswer(PreTest7)
  • あれ…。そういえばaをbに置換し、その後bをcに置換というのもアリか。
  • というわけでワーシャルフロイドを回して再提出。
    • 色々やってWrongAnswer×2(PreTest7)
  • PreTest7強すぎだろ…。
  • (Cに現実逃避。解いてから戻ってくる)
  • 片方のaをbに置換、もう片方のcをbに置換というパターンもあるじゃないか。
  • というわけで、a〜zそれぞれに置き換えるコストを全部試すコードを書いて再提出。
  • やっと通った。

C. Wonderful Randomized Sum

問題：長さ10万以下の数列が与えられる。初めに先頭から0個以上の要素の符号を反転させ、次に後ろから0個以上の要素の符号を反転させる。この操作の結果とりうる数列の総和の最大値は？

  • 符号反転のパターンを全部試したら死んでしまう。
  • 先頭からと後ろからの符号反転する領域を被らせることに意味は無さそう。
    • 2回符号反転したら元に戻るし。
  • 前後からDPして結果を合わせれば良さそうな気がする。
    • DP[i] : (先頭からの操作で)i番目の要素までを使ってできる和の最大値
    • DP[i] = max(DP[i-1] + i番目の要素の値, i番目の要素までの和の絶対値)
    • 後ろからも似たような感じ
  • DP[i](forward) + DP[i+1](back)の最大値が答え。

D. Knights

問題：円上のフェンスm個で区切られた土地上にn個の点がある。「a番目の点からb番目の点に行くために越えなきゃいけないフェンスの数の最小値は？」というクエリをk個消化する。

  • nとmが1000以下で、kが10万以下。
  • その昔、TopCoderで同じ問題(k=1バージョン)を見た気がする。
  • 点aからbに行こうと思ったら，aとbのうち片方だけを内包する円の数が答えになる。
  • というわけで、1つのクエリをO(m)で計算できるけど、O(km)って間に合うのか…？
    • ここで何故かkmの最大値を10億と勘違いした
    • 結果、ビット演算で高速化しても無理と判断
  • (m+1)個に区切られた領域の隣接関係をグラフで表せば木になる
  • となると、1つのクエリは木における最短路問題になる
  • 木なら幅優先すれば単一始点最短路はO(m)なので、全点間求めてもO(m^2)
  • あらかじめ全点間最短路を出してしまえば各クエリはO(1)
  • こ　れ　だ　！
  • というわけで頑張って実装して提出したら通った。
  • 普通にO(km)使っても間に合ったらしい。涙目。
  • -

結果：0:10(480, +0) / 0:57(622, +3) / 0:48(1212, +0) / 1:37(1224, +0) / -- ，60位
レーティング：1852 -> 1959 -> 1942


順位的にも内容的にも、誠に遺憾ながら平常営業でした。
こういうミスは減らさないといけないのに…。