簡単な問題をたくさん解いた。
2021 : 姫血液の問題。memo[ノード][冷凍残り時間]でdjikstra
1145 : ゲノム文字列の問題。構文解析. 長さがインデックスになるまで解凍する感じ。
1138 : 馬車チケットの問題。memo[ノード][持ってるチケット]でdijkstra
1140 : 掃除ロボットの問題。bfsで各汚れ間の距離を出して10!通り試す。
1136 : 折れ線を探す問題。回転したやつとかを全部探索するだけ。回転は虚数掛けると楽
1127 : 宇宙ステーションの問題。最小全域木やるだけ。
2399 : プライバシーを守る問題。やるだけ。
2019 : 姫が護衛を雇う問題。貪欲法。
1165 : 角角画伯の問題。やるだけ。
2151 : 姫が護衛を雇う問題。memo[ノード][残り予算]でdjikstra
2402 : 星間ダイクストラの問題。五角形にして星同士の距離やってdijkstra
2182 : Eleven Loverの問題。なめるだけ。
1189 : 素数洞窟の問題。メモ化探索。
1187 : ICPCのランキング付けの問題。プレディケート書いてソートするだけ。
2014 : WとBの柵の問題。やるだけ。
1335 : 漸化式立ててメモ化。漸化式考えるの楽しかった。
2007 : お釣りを渡す店員が親切な問題。持ってる金全部渡してみるというのがわかれば楽
2012 : 宇宙ヤシガニの問題。探索の順番。
1142 : 列車の文字列の問題。やるだけ。
1125 : できるだけ沢山木をとる問題。英語読むだけ。
1137 : ローマ数字の足し算の問題。YARUDAKE.
こんな問題がDとかに来てていいのかよ、って感じの問題が散見された。
Håstadのスイッチング補題
回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...
-
0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます. 1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ... -
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで... -
1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと...
0 件のコメント:
コメントを投稿