keyword 有向グラフ C++ 概要 有向非巡回グラフをなすクライアント群とクライアントと繋がっているサーバ群が与えられる。クライアントCからサーバSへの経路が存在するとき少なくとも一つの経路上にゲートがあるようにしたい。ゲートを置く最小個数を求める…

keyword C++ 概要 サイトのアドレス名、各サイトが含んでいるキーワード、危険ワード、閾値が与えられる。閾値以上の危険ワードを含むサイトは危険であると判断され、そのサイトが含むキーワードは危険ワードに追加される。危険なサイトのアドレスを返す問題…

keyword C++ 概要 五目並べの盤面が与えられる。どちらが勝っているか、どこに5連があるかを答える問題。ただし5連は多くても1つしか存在しない。 長連になっていないことさえ注意すれば得に問題は無い。番兵を置いておけば楽できる。

keyword union-find C++ 概要 2492:A Bug's Lifeと似た問題。 2つのチームがあり、aとbは所属が異なる、という情報とaとbの所属が同じかどうかというクエリが与えられる問題。 前と同じでUnion-Find使って実装。

keyword 線形合同法 シミュレーション C++ 概要 線形合同法の係数と種が与えられたとき、全ての数が表れるかどうかを判定する問題。 gcd使って簡単にO(1)で求まりそうな気もするけどシミュレーションで間に合うので愚直に試した。

keyword 動的計画法 整数分割 C++ 概要 整数N( 数列が偶数と奇数の場合をそれぞれ別個に求める。dp[N][数列の上界][偶数か奇数か]の3状態で、計算量はO(n^2)位。

keyword 幾何 シミュレーション C++ 概要 ダーツの得点と勝敗を判定する問題。的の中心を原点とした座標が与えられる。 書くだけ。

keyword シミュレーション C++ 概要 適当に数を選ぶと全ての組合せの内互いに素である確率は6/π^2に収束するらしい。実際に数字が50個程度与えられるときπの値を見積もる問題。ただし互いに素である数が一組もなかったらその旨出力すること。 サイズが小さい…

keyword 2進数 Java 概要 S = {3^i | i >= 0}の部分集合を要素の和で昇順に列挙したとき、n( nを2進数に直してビットの立っているものだけ拾ってくればよい。多倍長必須なのでJavaで。

keyword BruteForce C++ 概要 3279:Fliptileと殆ど同じ。 ソース略。

keyword 文字列処理 C++ 概要 文字列が与えられたとき、次の3条件を満たすかどうか判定する。 母音が1文字以上含まれている。 母音や子音が3文字以上続かない。 ee、oo以外に同じ文字が続かない。 書くだけ。

keyword 素数 C++ 概要 整数N(

keyword 有向グラフ 探索 C++ 概要 牛がk(

keyword 幾何 C++ 概要 2526:Center of symmetryと殆ど同じ問題。 前に書いたのを貼り付けてちょこっといじってみたらサンプルが通らない。あれっ、これ間違ってるじゃないか。何であれでACされてたんだろう、と疑問に思いつつ修正して無事AC。実はこのコー…

keyword 動的計画法 C++ 概要 整数n(素数の和がnになるような組合せの総数を求める問題。 硬貨の支払い方の問題のバリエーションの一つに過ぎない。1120以下の素数表を作っておき、dp[和がn][使った中で最大の素数(の番号)][使った素数の個数]で順に求める。…

keyword 最小全域木 C++ 概要 MSTを求める問題。 書くだけ。

keyword C++ 概要 n(t_iならロープiは千切れる。持ち上げることができる最大の物体の重さを求める問題。 weakest linkよろしく一番弱いものが耐えきればよいので強度の高い順にソートしてk本使うときの最大値を順に調べていけばよい。

keyword 幾何 C++ 概要 図の情報と燃料yが与えられる。1単位燃料で5単位距離進むことができる。自分の位置から目標まで辿り着いて戻ってくることができるか判定する問題。 zが180度より大きい場合に注意するだけで後は書くだけ。 これでAC300個目。200台はそ…

keyword BruteForce C++ 概要 5*5のボードが与えられて、各セルはHかJである。連続する7つのセルで、Jが4つ以上あるような選び方は何通りあるか求める問題。 (25,7)は4*10^6位なので全探索が間に合うはず。連続しているかどうかはBFSで判定。手元で最大ケー…

keyword BruteForce C++ 概要 正の数Tとn( サイズが小さいのでBruteForce。重複を取り除くためにsetvector > とか使ってるけど0msでAC。

keyword 有向グラフ 木 C++ 概要 有向グラフが与えられたとき、それが木であるかどうかを判定する問題。 これもサイズに関する記述が無かったのでとりあえず愚直に実装してみる。根の検出が頭悪かったり変数名は明らかにfromじゃなくてtoだよねとか色々問題…

keyword prefix C++ 概要 文字列が幾つか与えられたときどの文字列も他の文字列のprefixになっていないかどうか判定する問題。入力のサイズに関する記述が見当たらなかったので愚直に実装してみるとAC。計算量はO(文字列の個数^2 * 文字列の長さ)位だからま…

keyword 多倍長整数 Java 概要 CDをD枚(重複なし)持っている。これらをN人の甥に分け与えるときの総数を求める問題。 NのD乗を求めるだけ。

keyword 幾何 C++ 概要 3432:Count Squaresと殆ど同じ。 ソース略。

keyword 幾何 C++ 概要 2次元平面上の点が与えられたとき(2000個以下)、正方形がいくつできるか求める問題。 2点決めて正方形をなすような残りの2点があるかどうか2分探索すればよい。重複に注意。

keyword BFS Python 概要 N mod Nだけ考えて枝刈りしつつ探索すればよい。答えが小さいのと多倍長の可能性があるのでPythonで書いてソースに埋め込む。結果的に全てlong longで何とかなっていた。

keyword C++ 概要 素数p1,p2,p3が与えられる。素因数がp1,p2,p3以外を含まないような数を小さい順に並べたときN番目の数を出力する問題。答えは10^18以下になる。 総数はそんなに多くならないので数列を全部作る。オーバーフローが起きるかどうかまずlogをと…

keyword C++ 概要 str[i] C++で提出したら何故か無事AC。何だったんだろう…。

keyword 2分木 C++ 概要 上のような2分木がある。x( 2進数に書き直すとルールが見えてくる。実装は簡単。

keyword BruteForce 素数 素因数分解 Java 概要 K(素数リストは作っておく必要がある。