keyword n進表記 C++ 概要 数字を表す文字列がa,b, cが与えられたときa*b==cが成り立つのは基数(10^6以下)をいくつにすればよいか求める問題。 基数変換はO(log n)でできるので愚直に実装すれば間に合う。基数の下限には注意しておくこと。

keyword 数式処理 C++ 概要 多項式を多項式で割ったときの余りを求める問題。次数は10000以下。 筆算でやるのと同じようにすればよい。書くだけの問題。

keyword MST C++ 概要 辺と重みが与えられたとき最大重み全域木を求める問題。 符号を逆にして最小重み全域木に帰着させるとかわざわざしなくても重みの大きい辺から貪欲に付け足していけば良い。むしろこっちの方がpriority_queueのデフォルトがそのまま使…

keyword Warshall-Floyd C++ 概要 3660:Cow Contestとほとんど同じ内容。 A

keyword 動的計画法 丸め誤差 C++ 概要 [0..k](k 末尾の数字と文字列の長さでDPすれば該当する文字列の個数が分かる。計算量は最大で10*100だから余裕。ただし全ての文字列の作り方が10^100だったりして精度に不安がある。JavaでBigIntegerとかBigDecimal使…

keyword 有理数 格子点 C++ 概要 原点から[0,n]*[0,n](n 有理数ライブラリから引っ張ってきてsetに突っ込んでも良さそうだけど、x座標とy座標が互いに素であるものだけをカウントすれば良い。

keyword Nim C++ 概要 Nimで、各山にいくつ石があるかが与えられる。先手勝ちか後手勝ちかを求める問題。 純粋にNimそのものなのでxorとって0か1か判定するだけ。