問題文 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]に保存する。…

解法 深さ優先探索で、（int 分子、int 分母、int 分母の積、int 今何個目の数か、int 現在の分母の値）を管理しながらやる。ここで、n = 3の時、 とすればよい。 #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=ma</map></bits/stdc++.h>…

多少工夫してみたがMLEが取れないため保留 問題自体は解けたため次に進む #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; </bits/stdc++.h>…

深さ優先探索で全通り試せばいい。素直に全通り試すとO(2^36)となりなかなか厳しいが、全チームプレーオフにならないと分かったら探索を打ち切ればそこまで計算量は多くならない。 再帰では、今いる場所・それぞれのチームの勝利数・敗北数を渡していけばよ…

円盤を取り除く順番によって取り除ける最大数が違ってくるので取り除く順番を深さ優先探索で全通り試す。 何も工夫せずにシンプルに解いたらTLEだったので、mapを使って状態を保存しておき同じ状態が訪れたら打ち切るようにしてAC。 #include <bits/stdc++.h> #define chmin</bits/stdc++.h>…

ただのやるだけ #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;</int,></int,></bits/stdc++.h>…

パネルの変更の組み合わせを全通り試せばよい。（6^5 結合パネルかどうかはunion-findで判定すれば楽。 #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 emplac</bits/stdc++.h>…

解法：全探索＋ダイクストラ馬車券を使う順序が重要で、1 全組み合わせのそれぞれについてダイクストラで最短を求めてそのなかで一番小さい値が答え。 通常のダイクストラを拡張して、馬車券を何枚目まで使ったか、という次元を加える。priority_queueに三つ…

基本的にやることはICPC 国内予選2007D 崖登り AOJ1150 - intさわだんのBlack Historyとおんなじ 幅優先探索でゴリ押す #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc</map></bits/stdc++.h>…

解法：幅優先探索。右足でたどり着いたときの最小時間と左足の時の最小時間を分けて考える。この手の問題は得意なので秒で通した。（実際は分で通した。tupleとqueueのコンボが最強であることを知った。（自分が現役だったころはtupleなかった気がする。最近…

解法：深さ優先探索でゴリ押す 特に難しいところはない。計算量も気にしない。 #include <bits/stdc++.h> #include <map> #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 </map></bits/stdc++.h>…

解法：Union-Findでそれぞれのcell同士つながってるかをわかるようにし、つながってないcall間で必要なcorridorの長さの最小値を求めそのcorridorを採用する。という処理をすべてのcellがつながるまで繰り返す。小数の扱いが闇だった。printf使えば小数点以…

やるだけ。解法はICPC 国内予選2015C ICPC 計算機 AOJ1602 - intさわだんのBlack Historyと完全に同じ #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define </map></bits/stdc++.h>…

初心者なので幾何の問題に慣れてなくて焦ったけどかなりすんなりできた。解説一応しますが説明がすこし面倒なのと解説が必要なほど難しい問題ではないと思うのでかなり簡潔にします 建物のx座標の値はありがたいことに整数なので（これが小数だと面倒）x座標…

いわれたとおりにやるだけ。特に難しいことはない。 最後priority_queueを使えば楽に答えを求められる。（まあソートでもいいけど） #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs firs</map></bits/stdc++.h>…

シミュレーションやるだけ. （ドット）の多いところから計算すればよい #include <bits/stdc++.h> #include <map> #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 namespa</map></bits/stdc++.h>…

イキってDPで解いたら実装重くて痛い目にあった 集中してやったのでバグは起きなかった。dp[i][j][0] : 場所i,jをスタート地点にした時の数字の桁の最大数 dp[i][j][1～] : 最大の時の数字の列これを i = h-1, j = w-1 （一番右下のブロック）から i=0,j=0 …

解法： 探すもととなる折れ線を方向を変えた8パターンに分けて保存しておく（for文一つで実装できるがめんどくさかったためfor文8個使って泥臭く解いた） あとはその8パターンのうち一つでも一致するパターンがあるか地道に確認するだけ。 #include <bits/stdc++.h> #define</bits/stdc++.h>…

かなり初歩的なDPやるだけ。 #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; type</int,></bits/stdc++.h>…

シミュレーションやるだけ。折るたびに原点の座標を更新していけばよい。実装も重くないので楽。 #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</bits/stdc++.h>…

やるだけ。シミュレーション。実装もそこまで重くなかった。 #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</bits/stdc++.h>…

解法：しゃくとり法（？）（しゃくとりほうがどんなものなのかはっきり覚えてないけどたしかそう #include <bits/stdc++.h> #include <map> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb em</map></bits/stdc++.h>…

やるだけ。簡単すぎる。難易度100の実装重めのやつのほうが明らかにめんどい（個人差 #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 name</bits/stdc++.h>…