AOJ
解法 ループ全探索やるだけ。確認してないけど多分ジャッジには '*' が数字の末から詰まっていくパターンでないものも有ると思うので、それにも対応するように '*' は一致確認をスキップするような実装にする。反省 さすがに20分くらいで実装できた。慎重目…
解法 二重ループの全探索。 必ず左端から詰めるという制約の元、できるだけ右端まで到達できる権力を持つものを選ぶ。右端がNまで辿り着かない場合は"Impossible"と出力する。反省 D問題だし特殊な貪欲のようなものが有るのではないかという余計な考え方から…
解法 拡張ダイクストラ。施設で冷凍する時間を決めるときに、その場にとどまって最大Mまで回復する場合を全て priority_queue につっこむ。ここで、その場にとどまることがポイントでエッジの移動と冷凍を同時にやろうとしないこと。同時にやろうとすると、…
解法 BFS (or Warshall-Floyd) BFSではノードの接続を隣接行列でなくて連結リストにして解いたけどその必要はあったのだろうか。 因みにnは100以下なので、コストを1に定めて Warshall-Floyd しても解ける。この方が実装が短いし、一度最短路を求めればクエ…
解法 典型の配るDP。ジャンプ後の位置に障害物がある場合を見逃さないようにする。 あと問題文に書かれているけれど、ジャンプ台に乗って Y を超えるようなケースも注意。 自分は斜めからスキー台に侵入する場合分けが面倒になりそうだと思ったので直進を0, …
未実装考えてる解法メモは続きにある
概要 漢文の返り点を書き下し文に変換するアルゴリズムを実装せよ。
解法スプリンクラーとぴょん吉の dx, dy を作成してdfsすればいい。至極単純なやるだけ問題なのに1時間30分は要した。コンテスト中の1時間30分を考えたら、どうしようもない痛手になる。理由その１ 「その番号が作動する順番を表しています」を見落として、…
未実装 イメージしてるやつのメモ
未実装、合ってるか分からない解法メモは以下
解法１．まだ使っていないパズルの選択 ２．回転方向の選択 ３．上下左右で配置に適当なパズルかどうか判定 ４．配置可能なら更にパズルをおく（再帰） ５．全てのパズルを配置できたら、答えの場合の数が１増加する ６．再帰関数の戻り値を利用して、全ての…
初めに素数洞穴のマップを作る。 渦状にマップを作るのはバグりやすいので、まずはdx, dyを使わずに渦を1方向ずつforループを回して作ると良い。これでかなり楽に書ける。後はDPすればよい。自分は初めの地点から下３方向の洞穴に向かってBFSしていきDP配列…
二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。
解いてる途中のメモ MAPの中で数字のものだけを使って文字列結合をしていく。dpはstringの配列(vector) でもつとよい。 dp[i+1][j+1] = max(dp[i][j+1]+M[i+1][j+1], max(dp[i+1][j]+M[i+1][j+1])) Mが数値か文字かの判定が必要。数値なら、数が大きくなるよ…
任意の二点を選んでその点を通る円を作る。円は2個ある。 そのような全ての円それぞれが包含できる点の数を数えて最大値を求める。N 円の中心点の求め方 選んだ2点a, bの作る直線Aの生む垂直二等分線と、2点のうち一方の点と中心を結ぶ長さ１の線分から、三…
途中 メモ p, q, a, n が与えられる。 分数の値が等しいというのを確かめる際に浮動小数点に直してはいけない。 p/q, nume/deno の2つの値が等しい p*deno == q*nume であることを利用する また、問題文で指定されるような枝刈りを行うこと
途中 訪れたケーキの集合と現在地点を状態として持って拡張ダイクストラを実行する。 L, C, H, Dの種類のノードがあるが、全て一つのノードに詰める。その時、添字が例えば H, D, L, C の順になるように詰めて、予め種類ごとの場所を決めてやるのが上手い。
蟻本のそれで座標圧縮する。テープの区間を塗りつぶしたらDFSorBFSすればよい。座標圧縮する問題ではスタックオーバーフローの危険のないBFSの方が安全。まだ座標圧縮自体が掴みきれてない。
二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。
隣接リストを用いて拡張ダイクストラをする。 やりかた知ってれば書き下すだけだった。状態として 「前の位置」「現在位置」「到着時の速度」「経過時間」 を持つとよい。priority_queue に push する条件として制限速度を与えてやることに注意。
未解決 初めに洞穴のマップを作る。エラトステネスの篩を掛けて、マップのidと対応を見ると素数洞穴がわかる。 洞穴のマップがバグりそうならdx, dyを使わずに渦を1方向ずつforループを回して作ってみれば良い。これでまずバグらない。後はDPなのだが、私は…
二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。
記事作りかけのやつと1144 Curling 2.0
