keyword 暗号 C++ 概要 平文が文字の置換->順序の置換で暗号化される。文字列が2つ与えられ、一方がもう一方の暗号文である可能性の有無を調べる問題。 文字の置換ではヒストグラムは変わらないので2つのヒストグラムが順序を入れ替えたものかどうかを判定す…

keyword 組合せ 動的計画法 C++ 概要 整数n( よくある、硬貨の組合せの問題。dp[支払う金額][使う最大の硬貨]とすると計算量O(支払う金額*硬貨の枚数)で求めることができて、この場合の硬貨の枚数は2^20>10^6だから2^0...2^19の20枚で十分。なので計算量2*10…

keyword 幾何 2分探索 C++ 概要 x,y,cが与えられたときに?の部分を求める問題。 相似とか使えば厳密解が出そうな雰囲気はあるけど、面倒そうなので2分探索で。?が大きくなればcは下がり、小さくなればcは増えるという単調性を利用する。幾何と2分探索ってど…

keyword 定数最適化 C++ 概要 数の集合A,B,C,Dが与えられる。それぞれの濃度はn( この問題はアルゴリズムはずっと前から分かっていたけどTLEで弾かれつづけていた。固定長配列使うとかmapを使わないとか色々手を加えてやっと通った。 a+b == -(c+d)であるこ…