keyword Dijkstra C++ 概要 有向グラフが与えられる。ある目的地に行って戻ってくる(最短経路を使って)までの合計時間が最大になるものをみつけ、その合計時間を求める問題。ノード数は1000以下。 ダイクストラするだけ。帰りは辺を逆に張ればよい。

keyword 2部マッチング C++ 概要 P( 生徒と委員会を2部グラフに見立てて2部マッチングの最大個数が委員会の数と一致するか見れば良い。

keyword 最大流 C++ 概要 最大流の問題。 ソース略。

keyword 探索 C++ 概要 2次元の迷路が与えられる。右手則、左手則でゴールにたどり着くまでの時間と最短の時間を求める問題。 愚直に書くだけ。右手則でゴールにたどり着けることは保証してよいらしい。

keyword 探索 C++ 概要 2次元のボード上に石がいくつかある。この上でカーリングをして滑るヤツを目的地に持っていきたい。滑るヤツは石に当たるまで止まらないし、石に当たるとぶつかった石を破壊する。最短で何回滑らせれば良いか求める問題。ただし10回以…

keyword Dijkstra C++ 概要 2次元平面上に、現在地と目的地と、電車の路線図が与えられる。電車と徒歩の速度は一定の値をとる。電車を自由に使ってよいとき、目的地までの移動にかかる最小の時間を求める問題。 ダイクストラの練習問題。

keyword Warshall-Floyd C++ 概要 有向グラフが与えられる。自分以外のノードへの距離の最大値が最小になるようなノードとその値を求める問題。ノード数は100以下。 ノード数が小さいのでWarshall-Floydが間に合う。

keyword 確率 C++ 概要 n組のデッキを使ったブラックジャックでディーラーのopenになっている1枚と自分の2枚の数字が与えられる。現状態で（補充などを考えない）勝っている確率を求める問題。 実装するだけ。よく考えたらA2枚の場合を除いて21を越える場合…

keyword 動的計画法 C++ 概要 2479:Maximum sumと同じ問題。ソース略。

keyword 動的計画法 C++ 概要 長さn( 数字を1個も拾っていない。 一つ目の区間の中にいる。 一つ目の区間は終えていて二つ目の区間に入っていない。 二つ目の区間の中にいる。 二つ目の区間を抜けた。

keyword C++ 概要 1はSの元であり、x in Sならば2*x+1, 3*x+1 in Sである。Sの元を昇順に並べたときのN( いもす先生に教えてもらった。ハミング数を列挙する時の手法でハミングDPというらしい。この方法はxから定数個のxより大きい元が生成されるときに適用…

keyword 動的計画法 C++ 概要 T( dp[n番目まで処理した][変更の回数]としてDP。デバッグをはし先生に協力してもらった。

keyword 動的計画法 ナップザック問題 C++ 概要 01ナップザック問題を解く。サイズは個数3500以下、重さ400以下、価値100以下、容量13000以下。 dp[n番目まで見た][現在の容量]でDP。

keyword BruteForce C++ 概要 n( いもす先生にうまい解き方が無いか相談したら全探索でいけるんじゃないか、とのこと。確かにMを大きくするのは難しいように思われる。

keyword C++ 概要 長さn(再帰的に変換する。変換された後の列が与えられるので元の数列を復元する問題。 前から順に復元すれば良い。

keyword 平面幾何 二分探索 C++ 概要 1939:Diplomatic Licenseの入出力を逆にした問題。 普通にやると連立1次方程式を解くことになる。係数行列が複雑でないので多分普通に解けるけど、面倒なので2分探索で解く。nが奇数なので、1ヶ所固定して1周した後戻っ…

keyword 平面幾何 C++ 概要 n角形(nは奇数)が与えられる。中点を結んだ多角形を出力する問題。 単に中点を順に出力するだけ。

keyword n進表記 C++ 概要 A,B,...,Z,AA,...,AZ,BA,...,ZZ,AAA,...という順に文字列を列挙する。n( 26進数のように見えるけどちょっと違う(位取り記数法の0と1の役割がごちゃ混ぜになっているせい)。文字列を紙に縦に書いてみると解き方が見えてくる。 気分…

keyword C++ 概要 n(=nとしたプレイヤーの勝ちである。両者が最善を尽くしたとき、先手が勝つか後手が勝つか判定する問題。 いもす先生とはし先生に教えてもらった。 log scaleの数直線を書いて移動できる範囲を書くと、2と9を交互に掛けたところが境界にな…

keyword BruteForce 尺取り法 C++ 概要 2次元平面(100*100以下)が与えられて、各セルは0 or 1である。指定されたサイズの長方形で平面を切り取るとき、その長方形の中にある1の最大個数を求めよ。 サイズが固定だし、尺取り法(というか、区間をスライドさせ…

keyword 平面走査法 平面幾何 C++ 概要 長方形が複数与えられるのでカバーする面積を求める問題。 Problem 1202 : Mobile Phone Coverageの類題。

keyword greedy C++ 概要 プログラミングコンテストチャレンジブックを参考にして解いた。

keyword C++ 概要 格子状に川が流れていて、各川間の距離が与えられる。全ての川に触れるように移動するのに最小必要な距離を求める問題。 格子点状しか移動できないわけではないので長方形の対角線の長さが答え。 ストーリーが問題に全く関係なかったり、つ…

keyword C++ 概要 n( 実装ゲー。

keyword 迷路 DFS C++ 概要 2次元平面でドア、鍵付きの迷路が与えられる(20*20以下)。クリアできるかどうかを判定する問題。 ドアを開ける度に行動範囲が広がるのでドアを開ける度に探索をやり直す。効率は悪いけどサイズが小さいので余裕を持ってAC。

keyword 最小全域木 C++ 概要 無向グラフが与えられる。最長辺が最小の木を作る問題。 木はgreedy。最小全域木を作ればよい。

keyword 2部グラフ 累積和 C++ 概要 2部グラフ(1000*1000以下)が与えられる。ノードを番号順に並べたとき、辺の交点がいくつできるか求める問題。 いもす先生に教えてもらった。2次元配列a[n][m](a[i][j] = exist (i,j) in E)とする。その後各辺に対して、 …

keyword 半順序集合 C++ 概要 [0,10^4]^2に(x1,y1) x1

keyword 動的計画法 C++ 概要 n(スワップしてsum(x)とsum(y)の差を最小にしたい。その値を達成するのに必要な最小のスワップ回数を求める問題。 dp[n][(xの部分和)-(yの部分和)]で解く。計算量は6*2*n^2位。多分適当に順番入れ替えたりすればもうちょっと計…

keyword スミス数 素因数分解 C++ 概要 n( そんなに多くないだろうから埋め込みしようと思っていたけど全然終わらなかった。どうもスミス数は思っていたより密らしい。それならば探索する量は小さいので素直に実装する。