今回はリアルタイムで書き置きしておくことにする。

うろ覚えだけど覚えている分について書いてみる。

keyword 集合 C++ 概要 卵が先か鶏が先かという質問にOracleが答える。n人に答えてそのうちlie人に嘘を答える。n人の内liar人は教えられたものと反対のことを言う。n人のうちegg人が答を卵と答えた。答えは卵か、鶏か、どちらの可能性もあるか、どちらの可能…

keyword 最小全域木 C++ 概要 頂点数N( 木ではないけど最小全域木と同じ様なアルゴリズムで求められる。この辺はgreedyにいけるのでいろんなやり方があると思う。

keyword Union-FInd C++ 概要 2次元平面上の点がN( UnionFindでくっつけていくだけ。ちょっと無駄が多い感じはする。

keyword カレンダー Java 概要 2000年1月1日からの経過日数nが与えられたとき、年数、日付、曜日を答える問題。 閏年の計算方法などは与えられるので算数の問題として扱ってもいいけれど、せっかくJavaに良い機能があるのだからそれを使った。

keyword DFS C++ 概要 島の数を数える問題。 DFSで書くだけ。

keyword BruteForce C++ 概要 n(in {2,4,6,8,10})が与えられる。n桁の数字(先頭が0でも良い)のうち、前半と後半のdigit sumが一致するものがいくつあるか求める問題。 流石に10桁をBruteForceは無理だけど、前半部 or 後半部の和はたかだか9*5まで数えれば良…

keyword グラフ BruteForce C++ 概要 N( サイズが小さいのでBruteForceを考える。分割が2^19(最後の一個は固定)で和をとるのが|A|*20位といささか厳しい。取りあえず投げてみたら何とか通った。多分想定解ではないと思うけど。

keyword 2進数 動的計画法 C++ 概要 16チーム参加のトーナメントで、各チーム間の期待勝率が与えられる。各チームが優勝する確率を求める問題。 dp[チーム番号][n回戦を突破する確率]としてDP。n回戦で戦う可能性のあるチームはビットを使えば綺麗に求めるこ…

keyword 最小全域木 C++ 概要 N( 最大値の最小化は2分探索が定石らしいけど、この問題は実はMSTを作って最大の長さを答えれば良い。最小全域木はほとんどgreedyにやって大丈夫っぽい。

keyword BruteForce C++ 概要 M( サイズが小さいので全探索を考える。ただし4^20は流石に無理なので、まずは2^20通り調べて和が同じになるような分割を考える。その後に分割した両方がさらに分割できるか考えてやればよい。適当に定数倍最適化したら通ったけ…

keyword 迷路 BFS C++ 概要 3次元の迷路を解いて最短経路の長さを求める問題。 2次元でやるのと同じようにBFSで探索する。pair >とか非常に面倒なのでintにまとめる。このテクニックに名前ってついているんだろうか。前は座標圧縮ってこれを指していると思っ…

keyword 空間幾何 C++ 概要 円錐の表面上の2点が与えられる。円錐上を通る最小距離を求める問題。 定石どおり、展開図上で考えて直線の距離に落とす。

keyword greedy C++ 概要 N(区間が与えられ、1からT( 区間スケジューリング問題によく似た何か。今選べる開始時刻を持った区間の内、終了時刻が最も遅いものを選べば良い。開始時刻でソートしておけば計算量を落とせる。

keyword dijkstra 無向グラフ C++ 概要 長さ付きの無向辺が与えられる。ノードNからノード1への最短路を求める問題。 純粋なdijkstraの問題。ここぞとばかりにライブラリの実験をしてみた。一応無事AC。ちなみに同じノード間を繋ぐが長さが違う辺もあるらし…

keyword greedy C++ 概要 円の半径Rと数列x_iが与えられる。円の中心をx_iのいずれかに置いて円が全ての点x_iを被覆するようにしたい。置く円の最小個数を求める問題。 x_iをソートして小さい方から順に処理する。x_i+kに円を置いてもx_iが被覆されるならx_i…

keyword swap回数 行列 greedy C++ 概要 行列が与えられる。隣接する行を入れ替えることにより行列を下三角化したい。必要なswapの最小回数を求める問題。ただし下三角化できることは仮定してよい。 swapの回数は貪欲にやれば最小回数になるはず。それが分か…

keyword C++ 概要 同じ長さの数列が2つ与えられる。適当に順序を入れ替えてできる内積の最小値を求める問題。 小さい値の寄与を大きくして、大きい値の寄与を小さくすればいいんだから降順と昇順にしたものの内積をとれば良さそう。本当か？取りあえず書く量…

keyword 幾何 C++ 概要 平面上に犬とリスがいる。穴がいくつかある。犬はリスの2倍の速度で動く。リスが犬より早くたどり着けるような穴があるかどうか判定する問題。 距離が2倍以上離れているかどうかだけ見れば良い。出力の際にピリオド忘れてWAもらったけ…

keyword 位取り表記法 Java 概要 ローマ数字風なルールで書かれた数字が2つ与えられるのでその和をルールに則った形で出力する問題。 実装するだけ。これもソースを紛失してしまった。eclipseで毎回同じファイルを上書きしてるからこうなる。

keyword Greedy Java 概要 複数の問題があり、各問題が何分で解けるかが与えられる。ICPC形式のコンテストで、どの順番で解けば最もよいスコアがでるか、最良の値を求める問題。 簡単な問題から順に解けば良い。ソースは紛失したので略。

keyword シミュレーション Java 概要 アンケートの集計をしてソートする問題。 ソース略。

keyword Greedy C++ 概要 プログラミングコンテストチャレンジブックで解説がつくらしいので予習の意味を込めて挑戦。 文字列が与えられる。文字列の最初か最後を取り除いて、新しい文字列として取り除いた文字をつなげていく。辞書順で最小の新しい文字列を…

keyword 約数 文字列 C++ 概要 文字列s(strlen(s) 候補はstrlen(s)の約数だけ。またs=a^nであるかどうかの判定はO(strlen(s))でできる。 約数の個数が多いと怪しいけどとりあえず投げてみたら通った。

keyword シミュレーション C++ 概要 人々に2,3,...と番号が割り振られる。まず、番号2の人は仕事を免除され、それ以降の人は2ごとに仕事を割り振られて列から取り除かれる。次に番号3の人は…、番号5の人は…となる。仕事を免除される番号をlucky numberという…

keyword 平面幾何 平面走査法 C++ 概要 100個以下の長方形が与えられる。長方形がカバーする部分の面積を求める問題。 Y軸に平行なイベントラインをずらしていく典型的な平面走査法の問題。区間のカバーする長さを毎回求めてやる。

keyword 幾何 C++ 概要 直線から構成された図形が与えられる。合同な図形を判定する問題。直線はすべてX or Y軸に平行。 端点を原点に平行移動して回転させてやればよい。

概要 過去の事を思い出しながら経過を書き起こしてみる。