きままにものづくり

日々の気付いたことなんかを書いてます。

2015-01-01から1ヶ月間の記事一覧

SRM641Div1Easy

問題 N個の頂点が与えられる。これらの頂点を用いて内側に原点を含む三角形の数を求めよ。 解法 はじめに、三角形の総数Sを以下の式で計算する。 原点を含まない三角形の総数を求め、Sから引く。 原点を含まない三角形は、外積を用いて求める。まず、頂点iを…

SRM640Div1Easy

問題 V個の色を持つ頂点と、E個のエッジが与えられる。同じ色の頂点を結ぶには1のコストがかかり、それ以外はコスト無しで貼れる。全ての頂点を用いてツリーを構成するのに必要な最小のコストを求めよ。 解法 最小全域木に帰着できるので、プリム法を用いて…

SRM616Div1Medium

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13061 解法 TopCoder SRM 616 Div1 Medium ColorfulCoins - kmjp's blog TopCoder SRM 616 Div1 Medium ColorfulCoins - kmjp's blog kmjpさんの記事のお陰でようやく解法を理解できた。 最…

SRM597Div1Easy

問題 サイズNの文字列AとBが与えられる。A内のある文字を選び、それを先頭に持ってくるという操作だけができる。AからBにするのに必要な操作数の最小値を求めよ。AからBにできない場合は-1を返す。 解法 AとBの後ろの要素を比較する。同じだった場合は、次の…

dwango2015C

問題 C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder 解法 n回ラウンドを行い、引き分けが続くときの期待値は以下となる。 ここで、dは引き分けとなる確率を示し、(1…

SRM441Div1Easy

問題 サイズNの数列Aが与えられる。この時、もうひとつの数列Bは以下のように定義される。 B[0] = 0 B[i] = A[B[i-1]] () Aには0~N-1までの数字が重複無く含まれている。Bに0~N-1までの数字が重複無く含まれる時の数列Pを求め、AとPの要素の位置の違いの最小…

SRM598Div1Easy

問題 サイズNの数列が与えられる。300の値を格納できる箱がある。与えられた数列の全ての要素を箱に格納するのに必要な箱の数の最小値を求めよ。 解法 少し、制限を設けた貪欲法で解ける。 数列を昇順にソートし、左側(小さい値)と右側(大きい値)を足し合わ…

SRM599Div1Easy

問題 現在の値をXとした時、以下の2つの操作が可能である。 素数pをXにかける Xの約数dをXにかける AとBの2つの数字が与えられる。 を計算するのに必要な最小のステップを求めよ。 解法 Aを素因数分解する。素因数の数と、素因数の出現回数の最大値にBをかけ…

SRM600Div1Easy

問題 サイズNの数列と整数Xが与えられる。数列内の要素をORしていき、Xを作成する。Xが作成できないようにするために必要な要素の削除数の最小値を求めよ。 解法 Xが持っているビットだけの数字(i.e. X=6(110)の場合は2,4,6)を探索し、各ビットの出現回数を…

SRM601Div1Easy

問題 サイズNの2つの数列appleとorangeが与えられる。任意の数字xを選び、i番目のappleとorangeから合計x個を取り出す。これをNまで行う。この操作を行った時のappleの合計とorangeの合計の組み合わせの数を求めよ。 解法 appleとorangeの和の最小値Xを求め…

SRM602Div1Easy

問題 サイズNの数列と初期値Xが与えられる。与えられた順番のままで、現在の値に要素を足したり、引いたりすることができる。はじめの値はXとなる。2200以上の値を連続させることはできない。2200以上になる回数と2200より小さくなる回数の合計の最大値を求…

SRM635Div1Medium

問題 サイズNの数列placeとcutoffが与えられる。全ての要素でとなるために、place内で要素を入れ替える。入れ替えが必要な要素の最小数を求めよ。不可能な場合は-1を返す。 解法 二部マッチングで解こうとすると、となり間に合わない。 貪欲法で解く。 すで…

最小費用流(O(F V^2))

コード 関連問題 SRM619Div1Midium

SRM634Div1Medium

問題 二次平面上のn個の点が与えられる。各点は赤か青に染めることができる。同じ色の点は同じ色の線で結ぶことができ、同じ色の線は交差することができる。違う色の点は線で結ぶことができず、同じ色の 線は交差することができない。ある点同士を赤で結んだ…

最小費用流(O(F|E||V|))

コード 関連問題 SRM619Div1Medium

最大流(Dinic)

コード 関連問題 SRM633 SRM634

SRM646Div1Easy

問題 サイズNの数列が与えられる。ある要素に対して1を足したり引いたりする操作のコストを1とする。k個の連続した数字を得るための最小のコストを求めよ。 解法 与えられた数列を昇順にソートする。 数列のある要素を選択し、その要素を中心にk個の連続した…

SRM633Div1Medium

問題 ノード数N、エッジ数N-1の2つのツリーが与えられる。各ノードにはスコアを持っている。ノードの集合Sを定義する。S内のノードはツリー1にもツリー2にも含まれている。この時の集合Sのスコアの最大値を求めよ。 解法 任意のノードxを取り出し、そのノー…

SRM632Div1Medium

問題 N個のノードとM個の無向エッジが与えられる。各エッジにはの容量が与えられる。ノード0からN-1までの最大流を求めよ。ただし、答えは1000000007でmodをとる。 解法 Ford-Fulkersonは計算量的にも、エッジの最大容量的にも使用することができない。Ford-…

SRM631Div1Medium

問題 直線上のにの猫がいる。ひとつのpositionに複数の猫がいるのはよくないことである。猫は1秒に左右どちらかに1だけ移動できる。移動しないことも可能である。t秒後において、複数の猫が存在しなけばならないpositionの数を答えよ。 解法 貪欲法で解ける…

SRM639Div1Easy

問題 2人で行うゲームを考える。i回戦目で勝つと2*i-1ポイントがもらえる。両者の最終的なスコア(x, y)が与えられる。xとなるスコアを得るのに必要な最小勝利回数を求めよ。与えられたスコアを満たせない場合は-1を返す。 解法 ゲームの合計のスコアはx+yと…

SRM603Div1Easy

問題 コストを持つN個のノードとN-1個のエッジを持つツリーが与えられ、二人のプレイヤーで行うゲームを考える。プレイヤーは1つのエッジを選び、そのエッジとそれにより2つに分割されるどちらかのサブツリーを削除する。最後に残ったひとつのノードのコスト…

SRM604Div1Easy

問題 無限の平面を考える。k=0から始まり、四方向のどれかに必ず毎回移動するロボットが存在する。このロボットは(x, y)に到達することが可能か求めよ。 解法 到達可能な場合を考える。この時、(x,y)は以下となる。 は+,-の符号を、は0,1を示す。 指数が0の…

SRM605Div1Easy

問題 味と型があるハンバーガーがN個渡される。満足度Sはハンバーガーの型の種類Yと味の総量Tを用いてS=Y*Tと表される。ハンバーガーが与えられた時の最大の満足度を求めよ。 解法 型ごとの味の総和の最大値を計算し、味により降順にソートする。型をひとつ…

SRM606Div1Easy

問題 1から1,000,000,000までで1つだけ選び、その数字を当てるゲームを考える。guessは予測の数字であり、answerは予測の数字からの差分の絶対値を示す。選ばれた数字を求めよ。複数候補がある場合は-1を、嘘をつかれてる場合は-2を出力する。 解法 解の候補…

ARC031 C問題

問題 C: 積み木 - AtCoder Regular Contest 031 | AtCoder C: 積み木 - AtCoder Regular Contest 031 | AtCoder 解法 解説に載っている方法と同じ。BITを用いて計算する。 計算量 コード

AtCoder

AtCoderの問題を解いていきます。 解いたコードはgithubで公開しています。ARC033 A B C D ARC032 A B C D ARC031 A B C D ARC030 A B C D ARC029 A B C D ARC028 A B C D ARC027 A B C D ARC026 A B C D ARC025 A B C D ARC024 A B C D ARC023 A B C D ARC0…

SRM607Div1Easy

問題 長さNの文字列が与えられる。文字の要素は小文字のアルファベットか?である。?はランダムに小文字のアルファベットになる。回文となる部分文字列の個数の期待値を求めよ。 解法 ?に対して全探索をすると、となる。ある部分文字列が回文になるためには、…