土下座しながら探索中

主に競技プログラミング

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メモ化再帰) まだ倒れていないものがある場所に対応す…

herokuでカスタムドメインを使いたい

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

第2回 ドワンゴからの挑戦状 予選 D : 庭園

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

herokuのサーバー上に一時ファイルを作ったこと

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

Typical DP Contest I : イウィ

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

Typical DP Contest H : ナップザック

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

Typical DP Contest G : 辞書順

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

UVa 1577 : Low Power

問題リンク : https://uva.onlinejudge.org/external/15/1577.pdf問題概要 : n台のマシーンがある 各マシーンは2つの回路を持っていて、 各回路はk個のバッテリーを持っている つまり、全てのマシーンにバッテリーをセットするためには2*n*k個のバッテリー…

UVa 13039 : Fibonacci Triangle

問題リンク : https://uva.onlinejudge.org/external/130/13039.pdf問題概要 : 1番目のフィボナッチ数を2, 2番目のフィボナッチ数を3とする i番目のフィボナッチ数と同じ長さの線分がそれぞれa[i]個存在する これらの線分を使って作れる三角形の本数の最大…

UVa 13036 : Birthday Gift to SJ - 2

問題リンク : https://uva.onlinejudge.org/external/130/13036.pdf問題概要 : フィボナッチ数の積として表されるような数で、a以上b以下のものの最大値を求めよ解法 : laycrsさんの解説を読んで解いた フィボナッチ数のうち2から89までを前半、それ以降を後…

Typical DP Contest F : 準急

問題リンク:F: 準急 - Typical DP Contest | AtCoder 解法: dp[i] := i番目の駅に停まらない数 = dp[max(0,i-K)] + ... + dp[i-1] 初期値は dp[0] = 1, dp[1] = 0 また、dp[N] = 0 dp[1]=dp[N]=0は、必ずその駅にとまることを意味する dp[i]は max(0,i-K)…

Typical DP Contest E : 数

問題リンク : E: 数 - Typical DP Contest | AtCoder解法 : 桁DP dp[桁][余り][現在の桁までがNのこの桁までと一致しているか] := 総数コード : #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

AOJ 2607 : Invest Master

問題リンク : Invest Master | Aizu Online Judge問題概要: n日間の株価の情報が与えられる 初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ 株の売買に手数料はかからないものとする また、最終日の所持金の最大値は高々10^5で…

SEERC 2015 A : Equivalence

問題リンク : https://icpcarchive.ecs.baylor.edu/external/71/7173.pdf問題概要 : 2つの論理式が与えられる それらが等価か判定せよ論理式は論理変数、論理和、論理積、否定から構成される 論理演算の優先度は気にしなくても良い(適切に括弧がつけられ…

Typical DP Contest D : サイコロ

問題リンク : D: サイコロ - Typical DP Contest | AtCoder解法 : Dを素因数分解したとき、その素因数に2、3、5以外のものが存在するのであれば求める確率は0となる (サイコロの目が1から6までしかないので、例えば7は2、3、5の積ではどうやって…

Typical DP Contest C - トーナメント

問題リンク : C: トーナメント - Typical DP Contest | AtCoder解法 : DP全然思い浮かばなかったので愚直に計算した 他の人のコード見て勉強しますコード: #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

Typical DP Contest B - ゲーム

問題リンク : B: ゲーム - Typical DP Contest | AtCoder解法 : dp[i][j] := 左の山の残りがi個、右の山の残りがj個の時の(すぬけのターン)最大or(すめけのターン)最小値両方の山が0を初期状態とし、1手1手戻りながら計算するコード : #include<bits/stdc++.h> #defin</bits/stdc++.h>…

Typical DP Contest A - コンテスト

問題リンク : A: コンテスト - Typical DP Contest | AtCoder解法 : bool dp[i] := i が作れるならtrue, otherwise falseコード : #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; int n; bool dp[10001]; int main() { dp[0] = true; cin >> n; rep(i,n) { int tmp; cin >>…</n;i++)></bits/stdc++.h>

ACM-ICPC 2015 Tsukuba Regional Contest : つくば大会 参加記

ACM-ICPC 2015 つくば大会に参加したので記録チーム情報 コーチ : 先輩 研究が忙しい中つくばまで来て頂き有難うございました 「あのシャワー水しかでなかったんだけど」 コンテスタント1 : 後輩T 競プロ歴2日 英語マスター バンバン訳してバンバン伝える …

LiveArchive 6582 : UVa 1642 : Magical GCD

問題リンク:https://icpcarchive.ecs.baylor.edu/external/65/6582.pdf問題概要: 長さn(1 数列の各要素a[i]は1以上10^12以下 数列の連続した部分列を取り出し、(部分列全体のgcd) * (部分列の長さ) を値とする 値の最大値を出力せよ解法: 部分列の最も右と…

AOJ 1350 : There is No Alternative

問題リンク:There is No Alternative | Aizu Online Judge問題概要: 重み付き無向グラフが与えられる これに対する最小全域木は複数存在しうるが、それら全ての最小全域木に共通して存在する辺の数とそれらの総和を求めよ解法: Kruskal法を用いてMSTを構築す…

LiveArchieve 6804 : Group of Strangers

問題リンク:https://icpcarchive.ecs.baylor.edu/external/68/6804.pdf問題概要: 無向グラフが与えられる 3点を選んだとき、それらの間に1本も辺が存在しないようなものの数を数えろ解法: 公式解説の通りコード: #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

SRM 655 Div1 easy : LuckySum

問題概要 : 4と7から構成される正の整数をLucky Numberと呼ぶ [0-9]と?から構成される文字列が与えられる ?には何の数字が入っても良いので、2つのLucky Numberの和がその文字列と等しくなるようなもののうち最小の和を求めよ解法 : 動的計画法 dp[桁][値][…

UVa 12923 : The Island

問題リンク : https://uva.onlinejudge.org/external/129/12923.pdf問題概要 : n * n のマトリックスが与えられる マトリックスの(i,j)はi番目の人が武器jを使った時に得られる力を表す n人の人がそれぞれ1つ武器を持った際に得られる力の総和の最大値を求…