解法 重ねあわせた全体のカードの束から、２つに分ける位置を決めるように区間DPする。 元のカード束のうち２つの隣接する束を重ねるという動作を最も原子的なものとして、同様のアルゴリズムが最後まで展開されることを汲み取れれば解ける。反省 問題文を読…

解法を考えている途中

概要 二分木が入力されるので Intersect または Union して出力せよ。解法以下がBNF。 := ( , ) | ε 一つの親ノードと２つの子ノードの３つのノードについての処理を考える。つまりカンマの位置を特定することが必要なのでその方法を考える。 先頭の'('を読…

解法 ２×２の正方形のグリッドを取り出したとき、その中央の格子点を生命体の分割の数が変わるイベント点とする。するとグリッドのパターンは分割の数が 1 増加する２つと、1 減少する２つの４パターンのみに絞られる。（以下のコードでは check() 関数にそ…

解法 直前与えた肥料が何であるかが、今回に何を与えるのが最適であるかを決める。 よって、状態として「肥料を与えた回数」と「直前に与えた肥料」を持ち、成長率を最大化するDPをすればよい。 具体的には、k 日目に肥料 j を与えたときの成長率は、k-1 日…

解法 問題の「x+y=a」という式は x-y と x+y を繋げた式。 a を string とみなして切り分ける場所を決める。切り分け方が正しいかどうかのチェックは以下で可能。 切り分けた結果、先頭に0を含まない数字になるかどうか 和より差の方が必ず小さい xとyが両方…

解法 容易に定まる条件を持つものから決定していく。 円の中心が三角形の内側にあるかどうか調べる必要があるが、これはCCWするかそれに値するような外積の符号を見る式を書けばよい。内積で角度出してやろうとしたらうまく行かなかった。単純なミスなのか、…

解法 問題文を読んで、やるだけ反省 ボウリングの意味を勘違いしてたので、ずっとサンプルが合わなかった。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { typedef pair<int, int> Pii; int N; while(cin >> N && N) { vector<Pii> SCORE(N); for(int m</pii></int,></vector></algorithm></iostream>…

解法 地鶏を上限まで買えるだけ買った後、鶏肉の地鶏と普通の鶏との合計が足りるように地鶏を減らしながら調整する。地鶏が1匹も購入できない場合は "NA" と出力。ポイント 購入できる地鶏の数を予算から単価を整数除算することで見積もること 購入する地鶏…

考え中の解法 シミュレートする。1000個のブロックが落ちてくるとき最悪ケースでフィールドがどれだけうまってしまうかは 5*1000 で 5000 なので、grid[5001][5] を用意すれば十分。

解法考え中 多分、球面三角法使う。二点を最短で通る円から、その中心から二点までのベクトルのなす角を求める。 なす角が分かったら、半径に角度を掛けて弧を求める。

解法 拡張ダイクストラ。各エッジをわたるコストが0または1で、1のみではないことを考えると幅優先ではなくコストの小さいものをキューから取り出す拡張ダイクストラがいいと思うけど、多分幅優先でも出来る。問題では場外から目的地に向かうが、スタート地…

解法 問題文が長いが、冷静に必要な部分を把握して解く。 ポイントはエラトステネスの篩をかけた後に、区間の素数の数をO(1)で求められるように累積和を取ること。つまり、サブプライム(sub-prime)は求めずに、サムプライム(sum-prime)を求めればよい（激寒…

解法１ 牽牛と織姫とをつなぐ線分と、三角形の３つの線分との交差を判定しカウントする。 一回の交差のみなら "OK" それ以外の回数の交差なら "NG" と出力する。解法２ 牽牛と織姫が、三角形の内部か外部かで同じ場所にいるかどうかを判定すれば良い。 例え…

解法 bitDPで解く。 dp[S] := 状態Sでステージを全てクリアするのにかかる最小時間 dp[0] = 0 for S[0, 1<

解法 行の赤丸の数で降順sortする。全ての列の一つの赤丸で一行を丁度全て使いきったなら正しい。それをすべての行でループする二重ループ。 このGreedyで何故一意に復元できると言えるのかはわからない。 int n, row[10000], col[10000]; bool solve() { so…

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

解法 蟻本の反転の考え方を使う。最上部を踏むか踏まないか2^10で決め打ちし、2段目からはマスの一つ上が 1 であるなら 0 に埋めることを 9*10回 繰り返す。反転のオーダーは O(M*N*2^N)蛇足 Emacsのゲームにある 5x5 で遊んだらイメージがしっかり掴めて実…

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

解法 １．先ず太郎と鬼を結ぶ線分と円の中心点との距離を求める。 線分のベクトルと線分の端点と円の中心を結ぶベクトルのなす角が鈍角なら、線分と円の中心点との距離は、鈍角になる線分の端点と円の中心点との２点間の距離に当たる。鈍角の判定は内積が負…

解法 BNFが与えられるので、そのとおりに実装する。ただし substr() で時間がかかるためメモ化する。 BNFの実装方法は、自分は 'e' の位置を全て調べて正しい構文かどうかを再帰で繰り返し判定し、一つでも正しいパターンがあればその文字列はBNFによって正…

解法 本が全て「入りきる」または「入りきらない」を評価の条件として、本棚の幅を二分探索により求める。本棚の幅が正の整数の増加列の中の値であることから、この数列のうちで解を仮定して二分探索をすることができる。二分探索の基本問題。 #include <bits/stdc++.h> usi</bits/stdc++.h>…

解法 先にハミング数を全列挙してクエリに答える。 2と3と5の数を決めうちして列挙する。重複を許さないように、得られた値は set に詰める。 2^20 が100万を超えるので、2, 3, 4 は 20 個まで選択すれば十分。 #include <bits/stdc++.h> using namespace std; set<int> hamming;</int></bits/stdc++.h>…

解法 メモ化した愚直な素数判定。エラトステネスの篩でも良い。反省 はじめnの制約を見てなかったので愚直のisPrimeでTLEだったが、実行時間は4秒ほどだった。これならメモ化で十分かとなり、コードを書き直す必要はなかった。 #include<bits/stdc++.h> using namespace std</bits/stdc++.h>…

解法 やるだけシミュレーション。注意すべきところは思いつかない。反省 はじめused配列をboolで宣言してたにも関わらずintとして利用してた。 それを直してサンプル通って提出したらWAでおかしいと思ったら3x3の中で数にダブりがないかチェックする作業忘れ…

解法 購入するそば粉がちょうど入力と一致するとき買うことが出来る。 ナップザックでDPしても解けるが、入力は 500 〜 5000g の間で、100g 刻みで与えられると書かれているので全探索でも解くことが出来る。それぞれの店で購入するそば粉の量の単位を三重ル…

解法 ワーシャルフロイドした後、１つ中継点を決めてソースから２つのシンクまでのコストの和を最小化する。 中継点を k とすると、 cost[S][k] + cost[k][g1] + cost[k][g2] とすればコストの和が求まるので、forループで和が最小となる k を決める。反省 …

解法 ２円の交点を全て求めて、交点の集合を得る。その交点それぞれがどの円に含まれるかを全て調べ、含む円の数をカウントし最大値を求めれば良い。 ２円の交点を求める際、complex の polar が便利。polar(r, θ) で、対応する複素平面における座標が求まる…

解法 探索やるだけ。ブロックの位置と色をうまくグリッドに記録する。初期位置の色と同じ色を辿るように判定する。BFSで解いたけど普通にDFSの再帰で問題ない。反省 簡単...のはずが2x4の長方形を2x3で実装してて、生成したマップがおかしくて優に1時間くら…

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