keyword C++ 概要 2つの文字列が与えられる。順序を入れ替えることにより両方の部分文字列となるような文字列を出力する問題。 現れたアルファベットを数えて小さい方をとるだけ。10WA位とったけどそれは文字列が2つとも空とかの意地悪い入力のせい。

keyword シミュレーション C++ 概要 キーボードを１路右にずれた状態でタイプした。本来出力すべきだったものを出力する問題。 書くだけ。

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)であるこ…

keyword 動的計画法 C++ 概要 (x,y)のペアが与えられる。(x,y)>(x',y') を x>x' and y>y'で定義する。このとき、極大な元の個数を求める問題。ペアの個数は50000以下。 (x,y)を大きい順にソートする。yの最大値を覚えながら順になめていくと、yの最大値が更…

keyword 動的計画法 φ関数 C++ 概要 0

keyword 約数 包除原理 C++ 概要 n( オイラーのφ関数使えば解けるけど包除原理使って普通に実装した。

keyword シミュレーション 素数 C++ 概要 p(

keyword シミュレーション C++ 概要 グー、チョキ、パーの３状態でセルオートマトンを動かしたときnステップ後の状態を求める問題。 さすがにこれは愚直に書くしかないと思う。

keyword シミュレーション C++ 概要 曲がN( O(n^2)までいけるので特別なデータ構造を持たなくても愚直にシミュレーションすればよい。再分配のルールを勘違いしていて2WA位もらった。

keyword Dijkstra C++ 概要 2次元平面上に石が置いてある。石から石へジャンプして初期位置から目的位置まで移動したい。このとき最低限必要なジャンプ力を求めよ。 初期位置から目的位置までの最短経路とは別の問題だけど、DPちっくに書こうと思ったらDijks…

keyword 2部グラフ マッチング C++ 概要 数列a_iとb_iが与えられる。a_iとb_jは互いに素でなければペアとして選ぶことができる。最大でいくつペアをつくることができるか求める問題。 2部グラフの例題のような問題で動作確認にありがたい問題。

keyword ピタゴラス数 2部グラフ マッチング C++ 概要 200個以下の正の数字が与えられる(重複あり)。このとき、互いに素で2乗和が平方数になるようなペアがいくつ取り出せるか求める問題。 ペアは必ず偶数と奇数からなる。何故なら偶数と偶数のペアは互いに…

keyword 最大流 Ford-Fulkerson C++ 入力 流量を表す行列、sourceの番号、sinkの番号(いずれも0-base)を与える。行列については流れないとき0(実は負でも良いけど)を入れること。流量が実数の場合はアルゴリズムが終了する保証はない。 出力 sourceからsink…

keyword n進表記 Java 概要 n進表記で数numが与えられる。これをm進表記で出力せよ。ただし、n, m 書くだけ…なのにやたら時間がかかった。おまけに何か汚い。

keyword べき乗 C++ 概要 A_iとB_iとMが与えられたときsum(A_i^B_i) (mod M)を求める問題。数列の長さやMは45000以下。 AとBに関する制限は不明だけどさすがにintには収まるだろうと信じる。べき乗はO(log n)で計算できるので後は書くだけで良い。

keyword 動的計画法 Java 概要 まず1という文字列がある。1ステップ毎に、1は01に、0は10に変換される。n( 00, 01, 10, 11のペアがいくつあるかを各ステップ毎に覚えておけば良い。このとき、重複が無いようにするのと、一番右側は常に01であることに注意す…

keyword BruteForce C++ 概要 N( これまたサイズが小さいので、一々「和が一定のときは差が小さいときに積が最大に…」とか考えなくても全探索(O(n^1.5)位？)で間に合う。

keyword シミュレーション 文字列 C++ 概要 文字列が与えられたとき、任意のkに対してk字置きのcharのペアが全て異なっているかどうかを判定する問題。文字列の長さは80以下。 文字列が短いので愚直に試せば良い。書くだけ。

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か判定するだけ。