まず到着時間が早いもの順にソートする。それぞれの時間をソートした順にみていき、その時間に運行できる電車があればそのなかで一番最後に到着するものを採用し、なければ新しく電車を使う。電車の合計数が答え。 #include <bits/stdc++.h> using namespace std; typedef p</bits/stdc++.h>…

簡単なDP。5秒考えればわかる。 #include <bits/stdc++.h> using namespace std; #define INF 2000000000 int dp[20010][260]; int c[20],x[20010]; int main(){ int n,m; while(true){ cin >> n >> m; if(n + m == 0)break; for(int i = 0;i < m;i++)cin >> c[i]; for(int </bits/stdc++.h>…

問題文 judge.u-aizu.ac.jp解法は自明なので書きません setを乱用すれば簡単に解ける #include <bits/stdc++.h> using namespace std; int n; bool day[35][55]; int main(){ while(true){ cin >> n; if(n == 0)break; for(int i = 1;i <= n;i++){ int f; cin >> f; for(int</bits/stdc++.h>…

judge.u-aizu.ac.jpあらかじめ考えられるすべての辺の長さをキーに、その長さの出現回数を値にして保存しておけばよい。大きめの配列を使えばいいがmapを使った。 #include <bits/stdc++.h> using namespace std; int n,m; int h[1600],w[1600]; int main(){ while(true){ c</bits/stdc++.h>…

reading-hard ＆ 実装に工夫が必要 #include <iostream> #include <algorithm> #include <vector> #include <set> using namespace std; int n; int h[7]; bool m[6010][7]; int b[1010][5]; int main() { while (true) { cin >> n; if (n == 0) break; for (int i = 0; i < 5500; i++) { for (</set></vector></algorithm></iostream>…

問題文 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>…

解法 深さ優先探索で、（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>…

問題：nums行列の中の整数値から和がtargetと同じ値になるものを二つ選ぶ。 解法：やるだけ。全探索。O(N) class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> ans; for(int i = 0;i < nums.size();i++){ for(int j = i + 1;j < nu</int></int></int>…

多少工夫してみたが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>…

次の微分方程式と境界条件を満たす特解を求めよ. 解答 とする。両辺を微分して これを与式に代入して uでくくって 式(1)が成立するためには であれば十分である。式(2)は となる。両辺を積分すると となるので となる。最後の等号では により定数をにおきか…

解法：全探索＋ダイクストラ馬車券を使う順序が重要で、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>…