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( そんなに多くないだろうから埋め込みしようと思っていたけど全然終わらなかった。どうもスミス数は思っていたより密らしい。それならば探索する量は小さいので素直に実装する。

keyword C++ 概要 問題名：字母旋转游戏 アルファベットを渦巻き状に出力する問題。 実装ゲー。方向とか考えるのは面倒なので、何らかの座標変換して完全に線形にしてしまいたい。

keyword C++ 概要 チェスの盤面を出力する問題。 実装ゲー。「,」で分割とかはスペースに置換してstreamに流しているのをcodeforcesあたりで見かけた記憶がある。実際ポインタ使って云々とかするよりは楽だった。

keyword 行列 C++ 概要 サイズ500以下の正方行列A,B,Cが与えられる。AB = Cが成り立つかどうか調べる問題。 合宿のときに何か話してるのを聞いた気がする。行列の積は順序を入れ替えるだけで早くなるらしい。2次元配列を舐めるとき縦に走るより横に走った方…

keyword C++ 概要 改行タグと水平線タグを含んだhtmlのコードが与えられる。1行80字以下になるように出力する問題。 実装ゲー。トークンの分割とかは相変わらず苦手。stream使えば楽なんだろうけど。

keyword 動的計画法 C++ 概要 長さn(自然数である。いくつかの要素を取り除いて全ての要素が連続する様にしたいとき(111332444など)、最小でいくつ取り除く必要があるか求める問題。 kが小さいのでビットDPが思い浮かぶ。dp[n][既に置かれている要素][直前の…

keyword 動的計画法 C++ 概要 100*100以下のボードがあり、各セルに高さが設定される。自分のセルより低い4近傍に移動できるとき、最も長いルートの長さを求める問題。 4近傍で極小(or 極大)の高さのセルから開始すれば素直なDP。 今考えると適当な点から幅…