keyword 幾何 C++ 概要 点M_0とA_0,A_1,…,A_(n-1)が与えられる。このとき点列M_iをA_(i-1 mod n)に関してM_i-1と対象な点として定めるときM_jの座標を求める問題(n jが大きいので、きっとMは周期を持つか回転をするんだろうなと予測。とりあえずサンプルで点…

keyword シミュレーション C++ 概要 コンテスト(複数)の結果が与えられる。各コンテストでは1位から順にp[i]ポイントが与えられる。ここでポイント、1位の回数、2位の回数、…で順位付けしたときのトップと1位の回数、ポイント、2位の回数、…で順位付けしたと…

keyword グラフ 有向グラフ C++ 概要 n個の都市と有向の辺があり、環状に繋がっている(向きは考慮しない)。各辺の向きを逆にするのに必要なコストが与えられる。任意の都市から別の任意の都市まで行けるようにするには最小でどれだけのコストが必要か求める…

keyword 多項式 行列 分割統治 C++ 概要 行列A(30*30以下)とk( kが大きいのでO(log k)は必須。まさか公式一発ということもないだろう。そう考えると分割統治の発見は容易で、{A+…+A^(k/2)} + A^(k/2){A+…+A^(k/2)}で求まりそう。分割統治はなかなか書けない…

keyword シミュレーション C++ 概要 金額と、金利と毎年の手数料の組と年数が与えられる。決められた年数で最大お金がどれだけ増やせるかを求める問題。 問題文が長いけど、ひねりは無い。読めたら後は書くだけ。調べるの面倒で変数名にtanriとかhukuriとか…

keyword シミュレーション C++ 概要 長方形のケーキを何度かに分けて切った。各ピースの面積を小さい順に出力する問題。 入力の渡され方がとても面倒くさいけど基本的には実装ゲー。毎回番号を振りなおすというよく分からないことをしているのでmultisetで何…

keyword 二分木 C++ 概要 根が(1,1)の二分木があり、(a,b)の左の子は(a+b,b)、右の子は(a,a+b)である。(x,y)が与えられたとき、根から左右にそれぞれ何回落ちたらその頂点にたどり着けるかを求める問題。 TopCoderのSRMだったかTCOだったかで似たような問題…

keyword 互除法 Nim C++ 概要 2つの数a,bがある。プレイヤーはaとbの大きい方から小さい数の何倍かを交互に引いていく。最初に数を0にした方が勝つ。最善を尽くしたとき先手と後手のどちらが勝つか求める問題。 ユークリッドの互除法でgcd(x,y)を呼んだときx…