RUPC2011

First AC狙いでやっぱり後ろか見ていくことに。

I問題

• うまい扇の取り扱い方ってあったっけ？
  • モンテカルロ法とかεずつ動かして試すくらいしか思いつかんなあ。

H問題

• 夏合宿に似た問題があった気がする。
  • 今見ているノートの切れ端を2つとどこまで見たかでメモ化再帰すればいいはず。
  • 書いた。submit。MLE。
  • どうせ全状態に行くわけないからmapで保持してやれ。submit。AC。

G問題

• うわ、めんどくさい問題。
  • 水が画面外に出たり三方向にしか溢れない場合は1/3流れるんかなあ。
  • イベントドリブンでやって、水があふれたら四方向に蛇口を追加する感じで。
  • 途中まで書いたが、連結成分はまとめないとダメですね。
  • 書きなおす。とりあえず書き終わった気がするけど、どうせバグっているのでソースコードを見直す。
  • 予想通り何箇所かでミスっていた。サンプルを入れてみたら最後の3つが合わない。
  • 画面外にも水が流れるようにしたら一致した。submit。RE。
  • 水があふれる処理とかがミスってたのを直したけどWA。
  • 2時間くらい経っていたので他の問題へ。

F問題

• 既約分数の問題。
  • SternBrocot木は無理だな。約数を考えればいいんじゃね。
  • 書いた。submit。WA。
  • naive実装と比べてみるとn=6からおかしい。
  • 約数じゃなくて互いに素な数の個数か。分からん。
  • 考えるのがめんどくさくなったので、「既約分数　個数」とかでググッて式をそのままコードに直した。
  • submit。AC。

E問題

• DPっぽい問題。
  • メモ化再帰+シークレットの方は全探索でokか。AC。

D問題

• 幅優先探索ですね分かります。
  • 書いた。なんかよく分からん挙動をすると思ったら数値は一桁じゃないのね。
  • 書きなおした。TLE。
  • 時間が無いのでとりあえず後回し。

C問題

• ダイクストラですね分かります。
  • 途中で拾うってそこまで行くっていう意味なんかな。
  • 書いてる途中でdijkstraのライブラリを作っていた事を思い出したので貼付け。AC。

B問題

• なんだこの問題は。
  • 実は実装するだけか。書いた。AC。

A問題

• 後ろからやるだけ問題。
  • 書いた。WA。
  • 問題文を見たらstr[b[i]]-str[a[i]]じゃなくてb[i]-a[i]だった。AC。

結果

6完 23位。
G,F,Dは問題文をよく見れ＋コード書く前にどんなコードを書くかをちゃんと考えろと。あせってもいいことは無いですね。