keyword 多倍長整数 n進数 Java 概要 p進数の数a,mが与えられたとき、a%mをp進数で表記せよ。 aは大きいので、多倍長必須。こんなときのために練習していたJavaなので当然のように使います。Java使うと一瞬で実装できます。

keyword BruteForce DFS C++ 概要 5*5のボードが与えられる。各セルには1桁の数字が入っている。牛がその上を歩いて通過したセルの数を連結して6桁の数字を作る。このとき何通りの数字が作れるか求める問題。 6桁の整数だけ考えればよいのでBruteForceが使え…

keyword 幾何 C++ 概要 長方形が幾つかの線分によって分断されている。長方形内に点をいくつか打ったとき、どの領域に入ったか判定する問題。 本当は出力の形式がややこしい。領域に入っているかどうかのチェックは二分探索でもよかったけどサイズが小さいの…

keyword BruteForce C++ 概要 5*6のボードが与えられる。各セルはライトがonかoffになっている。あるセルを押すとそのセルと上下左右のセルのon、offが切り替わる。全てのセルをoffにするにはどのセルを押せばよいか。 最初の1列に対して押す、押さないを決…

keyword 幾何 複素数 C++ 概要 平行四辺形の3点が与えられる。最後の1点の座標を求めよ。 入力が非常に嫌らしい(4点与えられてうち1組は同じ点)けど、それ以外は単純です。ベクトルで足し引きしてれば答えが出ます。

keyword MST Kruskal Union-Find C++ 概要 複数の点の座標が与えられたとき、点をすべて結ぶにはどれだけのインクの量が必要か求める問題。 何のひねりもないMST。Kruskalで実装。

keyword 素数 部分和 二分探索 C++ 概要 10000以下の整数nが与えられる。このとき、連続する素数の和がnに等しくなるのは何通りあるか求める問題。 10000以下の素数はそんなに数が多くないので、素数表を作ってからm^2(mはn以下の素数の数)で全ての連続する…

keyword 数列 BruteForce Java 概要 2つの数列が与えられる。このときどの2枚を交換すればそれぞれの和が等しくなるか求める問題。ただし、複数あるときは和が最小になるものを選ぶ。 どちらの数列もサイズが100以下なので全探索が間に合う。

keyword BruteForce Java 概要 数列が与えられたとき、総和の差が最小になるよう2つのグループに分ける。このときの差を求める問題。 数列のサイズが20以下なので全探索が間に合う。いつものビットで。

keyword ソート Java 概要 長さ10の配列の得点の高い3つの合計を求める問題。 書くだけ。なんですが最初配列全体の合計値と間違えてWA。修正したら実は入力読み取るときの変数も間違っていてWA。こんな問題で2WAもとるなんて…

keyword 動的計画法 素数 Java 概要 商品の値段のリストが与えられる。それらから幾つかを組み合わせて注文するとき、予算以下で素数であるような合計金額を求める問題。 典型的DP。まずDPで可能な合計金額を予算以下まで列挙してその中で最大の素数を求めれ…

keyword ソート バブルソート Java 概要 数列が与えられてバブルソートするとき、swapは何回行われるか求める問題。 隣接する要素をswapする回数は確か挿入ソートでもバブルソートでも変わらなかった記憶があるけど、別にわざわざ挿入ソートで書くのもアレな…

keyword Java 概要 長さ4の数列が2つ与えられる。数値と位置が一致している数などを求める問題。 書くだけの単純な問題。

keyword 約数 BruteForce Java 概要 a, bが与えられたときa=a_1*a_2, b=b_1*b_2となるa_i, b_iをソートして隣接する要素の差の2乗和の最小値を計算する問題。 a, bがともに大きくないのでBruteForceで間に合う。

keyword 約数 素数 C++ 概要 数列が与えられたとき、その中で最大の素因数を持つものを求める問題。 最大の素因数が正確に計算できれば何てことはない問題です。

keyword 約数 combination C++ 概要 二項係数(n,k)の約数の個数を計算する問題。 サイズはそこまで大きくないけどとにかくinputが多い。n!の約数を覚えておけばよい。Fenwick-Treeの出番かと思ったけど更新がないので累積和を覚えておくだけでよかった。

keyword BFS C++ 概要 迷路と箱と人とゴールが与えられる。箱は人が後ろから押さないと動かない。箱をゴールに動かすまでに最低何回箱を押さなければならないか求める問題。 迷路のサイズが小さい(7*7以下)ので箱と人のペアを状態としてBFSすればよい。ただ…

keyword 素数 数論 Java 概要 互いに素な整数a,dが与えられたとき、初項a,公差dの等差数列でn番目に現れる素数を求める問題。 サイズが大きくないので愚直にやって間に合う。素数表はエラトステネスで。

keyword 最大公約数 Java 概要 2つの数の最大公約数を求める問題。 書くだけ。

keyword 時間表記 Java 概要 出社時刻と退社時刻がh m sで与えられる。勤務時間をh m sで返す問題。 全部秒に落とすと楽。

keyword 迷路 DFS Java 概要 w*hのセルに色付きのブロックがくっついている。同じ色のブロックだけを歩けるときスタートからゴールへの経路が存在するかどうかを調べる問題。 最短距離を求める必要すら無い定番の迷路。Javaだと一々オブジェクト作らないとい…

keyword C++ 概要 単語と出現したページのペアが入力として与えられる。それに対して索引風な出力をする問題。 実装するだけ。なんだけどJavaのHashMapってunsortedだから面倒だなあ、とか思ったのでC++で実装しました。それとgeditで書いたらタブとか改行と…

keyword Java キャスト 概要 ビルからボールを自由落下させる。地面に激突する際の速度がv以上になるには何階から落とせばよいか求める問題。 運動量保存則から簡単に計算できる。答えを最終的に切り上げて整数に落とす必要があるが、微小量を加えたりしてin…

keyword C++ 概要 n匹の牛にはレーティングが一意に割り当てられている。2匹の牛の対戦では必ずレートの高い方が勝つ。対戦結果がいくつか与えられるとき、レートの順位が確定するのは何匹か求める問題。 順位が確定するには自分よりレートが高い(低い)と分…

keyword BruteForce ビット C++ 概要 長さ20のビット列が与えられる。1回の操作で連続する3ビットをフリップさせる(端は2ビット)。全てのビットを0にするのに必要な最小のフリップ回数を求める問題。 XORを繰り返すのでフリップの順序は関係なく、同じ部分を…

keyword 動的計画法 C++ 概要 n*nマスのボードに数字が書かれており、現在のマスに書いてある数字の分だけ右か下のマスに移動できる。左上から右下に移動する経路は何通りあるか求める問題。 DPの例題みたいな問題。マスに書いてある数が0のときの処理さえ間…

keyword 幾何 複素数 包含 回転 C++ 概要 点の座標がN個と、半円の中心と半径が与えられる。半円を最も多く点を含むように配置するときの最大数を求める問題。 パラメータは角度だけなので、半円の中心が原点に来るように平行移動して回転させるだけ。

keyword C++ 概要 座標AからBまで歩く。一歩の間隔は直前の間隔と誤差1以内であり、最初と最後の一歩は間隔1である。最小のステップ数を求める問題。 一番効率が良いのは1,2,...,r-1,r,r-1,...,2,1となるとき。このときの移動距離はr^2。余りsがsrなら+2すれ…

keyword MST グラフ Union-Find Kruskal C++ 概要 街がN個あり、各街間の距離が与えられる。このとき、各街をケーブルでつなぐには最低どれだけの長さが必要かを求める問題。 MSTそのもの。Kruskalで実装。ループの検出はUnion-Findで。

keyword C++ 概要 最初にn本タバコを持っている。1本のタバコから1つの吸殻が手に入る。k個の吸殻から1本のタバコを作ることができる。最終的にタバコを何本吸えるか求める問題。 シミュレートするだけの問題。ひょっとしたら定数で求められるのかもしれない…