問題文 judge.u-aizu.ac.jp パッと見DP感があるな～と思って少し考えたらほんとにDPだった。 解説： i番目の円とi+1番目の円の交点は2つある。その二つの交点に適当に0個目、1個目の点とすると。 dp[i][j] =0番目の円（一番端の円）から、 i番目の円とi+1番…

問題↓ judge.u-aizu.ac.jp 解説 「各立方体は 0 個，1 個 または 2 個の立方体と重なることがあるが，3 個以上とは重ならない．」という条件から各立方体は鎖状もしくは環状になることがわかる。 任意の二つの立方体が重なるかどうかは少し考えればわかる（…

解説（文章にするのがめんどくさいので箇条書きで書きます） 最初の入力では数字が1~9の範囲しかなく、ピースが10個以上の時に区別が難しいのでO(WH)で番号を振りなおす。（これによってピースが合計何個あるのかもわかる） 次にそれぞれのピースについて、…

解説:まずそれぞれの障害物について、直線状のコースへの距離の最小値を求める。（つまり、障害物とコースの間の一番短くなるときの距離を求める）。これについては、点と線分の距離を用いて求める。ライブラリについては下記のサイトを参照しました。 qiita…

解法： 任意の二点を選ぶ(N*N通り） その二点が円周上にくるような半径１の円の中心の座標を求める。（二点間の距離が２以上の時はそのような円は存在しないのでスキップ） その円にいくつの点が含まれているか計算量Nで求める。その最大値が答え。 計算量O(…

解法： 大きめにとった二次元配列に1から10^6までの数の洞穴を書く。（たぶんここが一番めんどくさい エラトステネスで素数をすぐ求められる配列を作っておく。 あとは最初に指定された位置から簡単なDPを解くだけ。（もはやDPと呼べるレベルではない気がす…

解法：ロボットとそれぞれの汚れたタイル間の距離を幅優先探索で求める。 この時点でロボットから到達できない汚れたタイルがあるかどうかわかるので-1の出力判定ができる。 あとはnext_permutationですべての汚れたタイルを回る順番を全通りためしてその中…

パッと見シミュレーションか貪欲法かなと思って考えていたが一向に解法が浮かばなかったので解説を見ました。DPという発想が出てこなかった。こういう問題がでたら確実に通したい。解法： 2個、4個、6個....連続で取り除けるかの情報をdp1[i][j]に保存する。…

#include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const ll MOD=1</int,></int,></bits/stdc++.h>…