土下座しながら探索中

主に競技プログラミング

AOJ 2437 : DNA

問題リンク : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2437&lang=jp問題概要 : 日本語なので略解法: DP + 半分全列挙で解いたまず、i文字目(1 与えられる文法に含まれる非終端記号間の関係をグラフにするとDAGなので、これは再帰などで…

LiveArchive 6396 : Factors

問題リンク : https://icpcarchive.ecs.baylor.edu/external/63/6396.pdf問題概要 : 関数 f は2^63未満の正の整数 k を引数にとり、 k の素因数の異なるarrangementの数 n を返す関数である 例えば、 f(10) = 2 である なぜなら、 10 = 2 * 5 = 5 * 2 である…

SRM 730 easy : StonesOnATree

問題概要: 各頂点に重みのついた木が与えられる.. 木の情報は以下の通り .... 木の頂点数はnで表される .... 木の各頂点には0からn-1までの番号が割り振られており、 .... i番目(0 .... また、各頂点の子の数は高々2である この木を使ってゲームをする ゲ…

AOJ 2099 : Walk under a Scorching Sun

問題リンク : Walk under a Scorching Sun | Aizu Online Judge問題概要 : いくつかのの道と建物に加え太陽がある。 道、建物、太陽はそれぞれ線分、凸多角形+高さ、点として表される。道の上にあるある点xと太陽を結ぶ直線が建物と交差するなら、 その点xは…

TCO17 Algorithm Round 2A DistanceZeroAndOne

以下備忘録 解法: d0,d1からグラフを構築し、それらのグラフを1つにまとめる ある辺を答えとなるグラフに追加するかどうかは次のように決定する 1. d0,d1から構築したグラフの両方がその辺を持つなら答えのグラフにもその辺を追加 2. 片方しか持たないなら…

TCO17 Algorithm Round 2A Easy FoxAndCake2

以下備忘録解法 : 与えられる整数c,sの偶奇で場合分けする。 1. cとsがともに偶数ならば Possible ( 分割しなくても gcd(c,s) != 1 なので 2. cとsがともに奇数ならば - c と s がともに 3 以上なら Possible ( (3,3) (c-3,s-3)とすればよい - そうでないな…

SRM 714 div 1 easy : ParenthesisRemoval

SRM

問題概要 : 正しい対応関係を持つ括弧の文字列が与えられる その文字列の先頭の開き括弧 ( とそれより後ろにあるいずれかの閉じ括弧 ) を削除する 削除後の文字列の括弧の対応関係も正しくなければならない このとき、括弧の消し方は何通りあるか?解法: 後…

SRM 712 DIV 1 easy : LR

SRM

問題概要: サイズがnであるような2つの数列s,tが与えられる。 数列s,tの各要素には0からn-1まで番号がふられている。 数列sに対して以下の2つの操作を任意の回数だけ適用してtにできるか。 できるならその適用した順序を1つ出力せよ。 操作1. s[i] = s[i]…

SRM 711 : ConsecutiveOnes

問題概要: 整数nとkが与えられる 次の条件を満たすような最小の整数mを求めよ: 1. m は n 以上である 2. m を2進数表記にしたとき、1が少なくともk個連続する箇所が存在する制約 : 1 1 解法: mの中で1がk個連続する箇所をループで決める このとき、mがn…

SRM 709 Div1 easy : Xscoregame

問題概要 :長さ n (1 Aの各要素A[i]は 0 以上 50 以下である この数列に対して以下の処理を行う1. 変数 X を用意し、 X に 0 を代入する 2. 数列 A のなかから、まだ使っていない要素 A[i] を選び X の値を次の式で更新する : X = X + ( X xor A[i] ) これを…

SRM 708 : Div1 easy BalancedStrings

問題概要: 1以上100以下の整数Nが与えられる。 以下の条件を満たすサイズNの文字列の集合Sを1つ見つけよ。 条件を満たすようなものは必ず存在する。条件 1. 集合Sの要素である文字列の長さは1以上100以下である。 条件 2. 集合Sの要素である文字列は英小…

SRM 704 Div1 easy : TreeDistanceConstruction

SRM

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

LiveArchive 5873 : Tree Inspections

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

CODE FESTIVAL 2016 予選B : D - Greedy customers

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

CODE FESTIVAL 2016 予選B : C - Gr-idian MST

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

CODE FESTIVAL 2016 予選B : B - Qualification simulator

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

CODE FESTIVAL 2016 予選B : A - Signboard

問題リンク : 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>…

LiveArchive 6503 : Golf Field

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

SRM 694 Div1 medium : DistinguishableSetDiv1

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

SRM 694 Div1 easy : TrySail

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

AOJ 1314 : Matrix Calculator

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

Graphviz でノード名にプライムをつけたかった

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

SRM Div1 easy : BiconnectedDiv1

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

ACM-ICPC 2016 国内予選 参加記

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

SRM 692 Div1 easy : HardProof

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

SRM 691 Div1 easy : Sunnygraphs

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

SRM 688 Div1 easy : ParenthesesDiv1Easy

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

SRM 682 Div1 easy : SmilesTheFriendshipUnicorn

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

Codeforces AIM Tech Round (Div. 2) C : Graph and String

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

Typical DP Contest J : ボール

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