解法 ただ拡張ダイクストラするだけ。到達したノードとコストと残り回数をpriority_queueに突っ込む。コスト小さい -> 残り回数大きい の順にキューから取り出す。 初めに持っている回数券が経路をたどる回数より多い場合も有ると思う（未確認）ので、回数券…

解法 ループ全探索やるだけ。確認してないけど多分ジャッジには '*' が数字の末から詰まっていくパターンでないものも有ると思うので、それにも対応するように '*' は一致確認をスキップするような実装にする。反省 さすがに20分くらいで実装できた。慎重目…

解法 二重ループの全探索。 必ず左端から詰めるという制約の元、できるだけ右端まで到達できる権力を持つものを選ぶ。右端がNまで辿り着かない場合は"Impossible"と出力する。反省 D問題だし特殊な貪欲のようなものが有るのではないかという余計な考え方から…

解法 拡張ダイクストラ。施設で冷凍する時間を決めるときに、その場にとどまって最大Mまで回復する場合を全て priority_queue につっこむ。ここで、その場にとどまることがポイントでエッジの移動と冷凍を同時にやろうとしないこと。同時にやろうとすると、…

解法 BFS (or Warshall-Floyd) BFSではノードの接続を隣接行列でなくて連結リストにして解いたけどその必要はあったのだろうか。 因みにnは100以下なので、コストを1に定めて Warshall-Floyd しても解ける。この方が実装が短いし、一度最短路を求めればクエ…

入力は全て正しいか、雰囲気だけでなく確認しよう ある程度のまとまりを書いたらコードを読み直して正しいか確認しよう コンパイルして実行する前にもう一度コードを見直そう サンプルと全て完全に一致しているかどうか確認しよう 適切な場所にデバッグをか…

解法 典型の配るDP。ジャンプ後の位置に障害物がある場合を見逃さないようにする。 あと問題文に書かれているけれど、ジャンプ台に乗って Y を超えるようなケースも注意。 自分は斜めからスキー台に侵入する場合分けが面倒になりそうだと思ったので直進を0, …

問題概要 正の整数 n の "proper factor" とは、1 と n を含まない n の因数として定義づけられる。ある正の整数 n の全ての "proper factor" が int[] で入力されるので、ここから n を導け。解法 入力の最小の要素と最大の要素の積が答えとなる。以下 edit…

問題概要 ランダムウォークするロボットがある。４方向に遷移確率が与えられるので、同じ場所を踏まずにN回ウォーキングを続けられる確率を求めよ。解法 訪れた場所を **used で記録して遷移確率をかけながら状態を持って dfs するだけ。 EPSについての記述…

問題文 http://uva.onlinejudge.org/external/5/542.html問題概要 サッカーのトーナメント戦がある。a国がb国に勝つ確率が隣接行列で与えられるので、出場する16カ国それぞれについての優勝確率を算出せよ。解法 1試合で a国が勝つパターンと b国が勝つパタ…

問題文 http://uva.onlinejudge.org/external/104/10466.html概要 一つの恒星の周りを惑星が周り、その惑星を別の惑星が衛星のように周わることが繰り返し続く惑星系がある。この惑星系で、それぞれの惑星は二次元上の円を成して周わる。N個の惑星が存在する…

問題文 http://uva.onlinejudge.org/external/115/11559.html概要 ポイントは以下 You are free to choose from a number of weekends this autumn, and have to find a suitable hotel to stay at, preferably as cheap as possible. > コストを最小にする…

問題文 http://uva.onlinejudge.org/external/106/10678.html概要 距離 D の２本の柱に長さ L ロープが繋がっている。 一頭の牛がこのロープに付けられたリングと繋がって放牧されていとき、牛が動ける面積を求めよ。解法 牛の動ける領域は楕円の面積分の領…

未実装考えてる解法メモは続きにある

概要 漢文の返り点を書き下し文に変換するアルゴリズムを実装せよ。

問題文 http://uva.onlinejudge.org/external/104/10489.html概要 深さに対して分岐するノード数が決まっている木がある。全部で B 個の木があるので、全てのノードを N 人に等配分し、そのときの余りを出力せよ。解法 英文の意味が取れればやるだけ。深さと…

問題文 http://uva.onlinejudge.org/external/104/10493.html概要 葉ノード数がちょうど M で構成される N 分木は存在するか。 そのような N 分木のノード数が一意に定まるなら、"N M 全体のノード数" を出力。 複数存在するなら "Multiple" 存在しないなら …

解法スプリンクラーとぴょん吉の dx, dy を作成してdfsすればいい。至極単純なやるだけ問題なのに1時間30分は要した。コンテスト中の1時間30分を考えたら、どうしようもない痛手になる。理由その１ 「その番号が作動する順番を表しています」を見落として、…

未実装 イメージしてるやつのメモ