問題概要： 次の制約を満たすような木は存在するか？1. 木の頂点iのeccentricityがちょうどd[i]である.ここで、頂点iのeccentricityとは、頂点iから最も遠い頂点との距離のことである. 存在するのであればその木の辺集合を配列にして返すこと. 存在しないの…

問題リンク : https://icpcarchive.ecs.baylor.edu/external/58/5873.pdf問題概要 : ２次元平面上にT本の木とH本の道が存在する. T本の木のうち60%以上を道の上から見ることはできるだろうか？ 木は以下の条件を満たすとき、道から見ることができる : 道から…

問題リンク : D: Greedy customers - CODE FESTIVAL 2016 qual B | AtCoder問題概要 : 日本語なので略解法 : (備忘録） 貪欲法。１ずつ引いていけば良い？1を引けなくなったら2を、それもダメなら3を、...という流れで、 => Sample Input 2 の答えが13になる…

問題リンク : C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder問題概要 : 日本語なので略解法 : (ほぼ備忘録) クラスカル法。 ただし、辺が多すぎて愚直に列挙することはできない。 そこで、この問題では行または列ごとに辺の重みが決まっていること…

問題リンク : B: Qualification simulator - CODE FESTIVAL 2016 qual B | AtCoder問題概要 : 略解法 : 既に通過した国内の学生と海外の学生の数を変数に保持しながらループを回します。コード : #include<iostream> using namespace std; const string YES = "Yes"; c</iostream>…

問題リンク : A: Signboard - CODE FESTIVAL 2016 qual B | AtCoder問題概要 : 略解法 : ループを回します。コード : #include<iostream> using namespace std; int main() { string s = "CODEFESTIVAL2016",t; getline(cin,t); int mini = 0; for(int i=0;i<(int)s.si</iostream>…

問題文 : https://icpcarchive.ecs.baylor.edu/external/65/6503.pdf問題概要 : ２次元平面上にn個の点がある. ( 4 この中から異なる４点を選び凸包を作る. 得られる凸包の面積の最大値を求めよ.解法 : 凸包 + キャリパー法 + 三分探索以下の問題の完全上位…

問題概要 : n人にm回質問をする. 人と質問にはそれぞれ0からn-1,0からm-1まで番号が割り振られている. 人iの質問jに対する回答は英大文字('A'~'Z')として表現される. 各人の各質問への回答が入力として与えられる. 全ての人を区別するためにしなければならな…

問題概要 : n人の生徒からなるクラスがある. 各生徒には強さがあり、それらは0以上255以下の整数として表される.n人の生徒を3つのグループに分ける. ただし、グループ分けを行う際に、だれも生徒が属さないようなグループが出来てはいけない. グループの強さ…

問題概要 : 問題文で定義されている Matrix Calculator を実装せよ シンタックスはBNFで与えられるMatrix Calculator : 行列計算を行うプログラム Matrix Calculator の機能等を適当に列挙 1. +, -, * : 行列の加算、減算、乗算 2. - : 単項演算子のマイナス…

Graphvizでノード名にプライムをつけようとしたらエラーが出た ググっても解決策がでてこなかったのでメモ 解決策 : ノード名を"で囲む ダメな例 : digraph g { node0' [color="#ffffff", fontcolor="#ffffff"];node1', node2->; } 良い例 : digraph g { "no…

問題概要 : n個のノードが存在し、それらは0からn-1まで番号が割り振られているノードiはi+1がn-1以下であればノードi+1に向けて重みw1[i]の辺を持つまた、ノードiはi+2がn-1以下であればノードi+2に向けて重みw2[i]の辺を持つ各辺は無向辺であるこのように…

最後の国内予選なので参加記を残そうかと チームは私と後輩Sと後輩Tです。（イニシャルだけだと去年と同じだけど後輩Tは去年とは別の人 [追記]後輩Tではなく後輩Mでした、後輩Mさんごめんなさい リハーサル 後輩Sは2,3限に授業があるため不参加 後輩Mととも…

問題概要 : 任意の２点間に辺があるような重み付き有向グラフが隣接行列Dとして与えられるこのグラフはn個の頂点から成り、各頂点には0から順にn-1まで番号が割り振られている全ての頂点を少なくとも１回以上訪れるような閉路について考えたとき、この閉路に…

問題概要 : n個の頂点とn本の無向辺があり、頂点は0からn-1まで番号が割り振られている また、辺は頂点iから頂点a[i]に向けて貼られている ( ただし、i != a[i] )このグラフに対して次の処理を行う 1. 新たな頂点 n を追加する 2. 0からn-1までの頂点集合か…

問題概要 : '('と')'からなる文字列sが与えられる この文字列に対して次の処理(1,2を連続で)を行うことができる 1. ２つの整数l,r (l 例 s = "((()", l = 1, r = 3 => s = "(((" 2. s[l]からs[r]までの各文字に対して、'('なら')'に、')'なら'('に変更する …

問題概要 : N人の人がいて、それらの人は0からN-1まで順に番号が割り振られている これらの人の間には友好関係があり、これは２つの整数で表される 友好関係は2つの配列A,Bとして表されA[i]番の人とB[i]番の人は友達である A[i] != B[i] これらの友好関係は…

問題リンク : http://codeforces.com/contest/624/problem/C問題概要 : 長さnの{'a','b','c'}で構成されている文字列が存在した これを次の手順でグラフに変換した 1. n個のノードを作成、各ノードに１から順に番号を割り振る 2. 異なる２つのノード番号i,j…

問題リンク : J: ボール - Typical DP Contest | AtCoder問題概要：略解法： 期待値苦手すぎて謎だったので以下の解説記事を参考にしました Typical DP Contest J - ボール - Lilliput StepsビットDP (orメモ化再帰) まだ倒れていないものがある場所に対応す…

herokuでweb appを作ると通常xxx.herokuapp.comというurlになっている このherokuapp.comを消してxxx.comにしたい したのでその過程をメモ ちなみに月1100円くらいかかる1. ドメインを買う ( 年1300円くらい、購入するドメイン名によるけど ） 自分は VALUE-…

問題リンク : D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder問題概要 : 略解法 : 長方形を２つ選ぶので、縦か横に領域を分割して それらの中の最大値を足したものの最大値が答えとなる そのため、ある長方形の中の最大値について求めることができれ…

herokuのサーバー上に一時ファイルを作る必要があり、それが出来るようになるまでに困ったところと解決策をメモ 1. 一時ファイルを作成できるのは /tmp 内だけそれ以外の場所にファイルを作成しようとしても無駄です例えば、 java で一時ファイルを作るため…

問題リンク : I: イウィ - Typical DP Contest | AtCoder問題概要 : 最大iwi数解法 : メモ化再帰 => WA 区間DP => TLE TLEを解消する方法が全く浮かばなかったので諦めてrngさんのコードを参考に解いたdp[L][R] := 閉区間[L,R]までで得られるiwiの最大値 区…

問題リンク : H: ナップザック - Typical DP Contest | AtCoder問題概要 : 日本語なので略解法 : まずナップザックに入れるものを色の番号が小さい順にソートする （同じ色のものは連続した場所に存在するようにしたいだけ） 通常のナップザックに加えて、今…

問題リンク : G: 辞書順 - Typical DP Contest | AtCoder 問題概要 : 文字列sと自然数Kが与えられる sから得られる連続でない部分文字列のうち、辞書順でK番目のものを求めよ解法 : 他の人のブログを参考に解いたので、 コードにある通りコード: #include<bits/stdc++.h> #d</bits/stdc++.h>…