Java
問題（外部リンク） 2441 -- Arrange the Bulls 実装の概要 空いているところに牛を配置する問題。深さ優先探索では間に合いません。 ただ、nおよびmの最大値は大きくないのでビットDPであればで求めることができます。 具体的には、例えば1101(2進数)を1、3…
問題（外部リンク） Fastest Route | Aizu Online Judge 実装の概要 ステージを経由する順序によってそれぞれのステージをクリアするための時間が変わるためグラフのアルゴリズムをそのまま使うことはできません。 また、要素数は少ないですが流石にですべて…
問題（外部リンク） 3368 -- Frequent values 実装の概要 指定された区間の中で最も長く同じ数字が続いた箇所の長さを求める問題です。要素数とクエリ数が多いためその都度ループを回すと間に合いません。 そこで今回はセグメント木を使います。ただし区間内…
問題（外部リンク） 3264 -- Balanced Lineup 実装の概要 今回の問題で重要なのはある区間における最小値と最大値なので、それぞれをセグメント木で管理することで高速に処理を行うことができます。（クエリ数が多いので、その都度ループを回して区間内を探…
問題（外部リンク） http://poj.org/problem?id=2155 実装の概要 A[x, y]が1か0かは、A[x, y]が何回長方形の内部に入ったかで判断することができます。 ただ、長方形内の全ての点を塗りつぶすように数え上げると間に合いません。 そこで、長方形の左上の座標…
A : Stack 問題（外部リンク） Stack | Aizu Online Judge 実装の概要 Java.util.Stack内に必要なメソッドは既に容易されているのでこれを利用することでACできます。要素を取り出さないときはpeek()です。 public class Main { public static void main(Str…
A : Vector 問題（外部リンク） Vector | Aizu Online Judge 実装の概要 java.util.VectorでACすることが可能です。このVectorにはremoveLast()がないのでremove(vec.size() - 1)とすることで末尾を指定することができます。速度が気になるところですが制限…
問題（外部リンク） 1759 -- Garland 実装の概要 計算式のみで正確な値を求めるのは困難なので、二分探索を用いて値を絞り込みます。正しい解の条件は「いかなる点においても座標が0以上であること」です。 両端の座標を初期値として漸化式を解くと、i番目の…
問題（外部リンク） 1703 -- Find them, Catch them 実装の概要 グループ分けの問題で、Union-Find木が非常に有効です。ですが、所属している組織でグループ分けをしようとするとうまく行きません。 そこで今回はA, Bという事実がそれぞれ共存するなら同じグ…
問題（外部リンク） 1631 -- Bridging signals 実装の概要 信号が交差しないための条件は行き先の数字が単調増加することです。問題の1つ目の入力例では行き先が{4,2,6,3,1,5}となっており、できるだけ要素数が大きくなるように増加数列を作ると{2,3,5}とな…
問題（外部リンク） 1222 -- EXTENDED LIGHTS OUT 実装の概要 30マスあるので全てのマスについてボタンを押すかどうかを考えると2^30パターンとなり、それで全部0になったかどうかのチェックも含めると間に合いません。 ですが、一番上の行だけであれば2^6=6…
問題（外部リンク） 1017 -- Packets 実装の概要 使用できる箱の大きさが6*6と決まっているので、まずはサイズが6*6である荷物の数だけ小包が増えます。 同様に5*5の場合も荷物と同じ数だけ小包が増えますが、こちらは隙間の各11マスも活用することができま…
問題（外部リンク） 3104 -- Drying 実装の概要 最大値を最小化する問題です。二分探索を利用して解を絞り込みます。 「x分で全ての洗濯物を乾燥させられるか」についてですが、直感的には最も時間がかかる洗濯物を毎分ごとに選んで乾燥機を使えばできそうで…
問題（外部リンク） 3273 -- Monthly Expense 実装の概要 1期間あたりの予算の下限を求める問題です。解を仮定して二分探索で絞り込む方法で解きます。蟻本では「最小値の最大化」として紹介されていますが、実際には「最大値の最小化」なので絞り込みの部分…
問題（外部リンク） 3258 -- River Hopscotch 実装の概要 最小値を最大化する問題です。どのm個の石を取り除くかを全探索で考えようとすると間に合いません。 そこで、最大値を仮定し二分探索を利用して絞り込みます。 仮定した解をaとすると、今回の問題は…
問題（外部リンク） 1995 -- Raising Modulo Numbers 実装の概要 問題文ではやや難しい表現を使っていますが、出力の仕様に書いてある計算式の通り累乗したものを加算してmodを求めることで解くことができます。 その際、指数部が大きく普通にループを回すと…
問題（外部リンク） 3641 -- Pseudoprime numbers 実装の概要 となっているかを判断する問題ですが、注意点がいくつかあります。 まず、pの値が大きいので乗算を普通のループで計算すると間に合いません。そのためここでは繰り返し二乗法を使います。 また、…
問題（外部リンク） 3292 -- Semi-prime H-numbers 実装の概要 この問題では数字はの形で表されるH-numberしか現れません。 H-primeかどうかの判定は通常の整数に対するエラトステネスの篩を改修することで実現できますが、H-semi-primeかどうかの判定は困難…
問題（外部リンク） 3421 -- X-factor Chains 実装の概要 例えばX=100であれば条件を満たす数列は 1,2,4,20,100 1,5,25,50,100 など計6パターンが有りえますが、ポイントとなるのはXを素因数分解した結果です。であることを考えると2つの2と2つの5をどの順番…
問題（外部リンク） 3126 -- Prime Path 実装の概要 それぞれの素数をグラフの頂点と考え、ある特定の桁だけ数字を変えれば良い場合は距離を1として初期化します。 その後はある頂点から別の頂点までの最短距離を求める問題と考えることができます。ワーシャ…
問題（外部リンク） 2429 -- GCD & LCM Inverse 実装の概要 与えられた最大公約数（GCD）と最小公倍数（LCM）からもともとの2つの整数を逆算する問題。 入力値がlong型なので全パターン試そうとすると間に合いません。また、a+bが最小になるようにという条件…
問題（外部リンク） 2395 -- Out of Hay 実装の概要 最終的に構成したいのは最小全域木ですが、今回は距離の総和ではなく全域木を構成する辺の中で最長のものの長さです。 そのため、クラスカル法の一部を変更し最大の距離を保存できるようにすることで解く…
問題（外部リンク） Save your cats | Aizu Online Judge 実装の概要 問題の条件を言い換えると、「与えられたグラフから閉路が無くなるように辺を取り除く場合、取り除いた辺の長さの総和の最小値はいくらか」ということになります。 そのため、クラスカル…
問題（外部リンク） 2377 -- Bad Cowtractors 実装の概要 今回は普段とは異なり「なるべくコストの大きい」全域木を作ることが目標です。 ただ、既にプリム法やクラスカル法を実装したことがあれば条件式を逆にすれば良いので既存のコードを再利用することが…
問題（外部リンク） 1258 -- Agri-Net 実装の概要 グラフ全体での最小コストを求める問題です。今回の実装ではクラスカル法を使いました。 クラスカル法の計算量は頂点数をE, 辺の数をVとするとです。今回は密グラフなので辺の数はそれなりに多いですが十分…
はじめに 試験の難易度 学習に使った教材 出題形式 要注意の出題範囲 パッケージ管理 アクセス修飾子 継承とインターフェース ラムダ式 代表的なAPI 当日について 終わりに はじめに 先日Oracle Java SE8 silverの試験を受験し無事に合格することができまし…
問題（外部リンク） Road Construction | Aizu Online Judge 実装の概要 条件より首都から各都市への距離が最短である必要があるので単一始点最短路問題として解きます。Nの値が大きい割に辺の数はMダイクストラ法であれば十分間に合います。 今回は距離の計…
問題（外部リンク） 3268 -- Silver Cow Party 実装の概要 （2/20 下部に追記あり） パーティー会場xまでの往復距離の最大値を求めたいので、それぞれの地点からxまでの最短距離と、xからそれぞれの地点までの最短距離を求める必要があります。 Nアルゴリズ…
問題（外部リンク） 3259 -- Wormholes 実装の概要 今回の問題ではそれぞれのfieldを行き来するのにpathとwormholeを使うことができ、後者では時間を遡ることができます。 つまり、wormholeの移動コストをマイナスとして扱い、負の閉路（移動距離がマイナス…
問題（外部リンク） 2139 -- Six Degrees of Cowvin Bacon 実装の概要 aとbが共演したことがあれば距離1、aとbは共演してはいないがcはaやbと共演したことがあれば距離2、…というようにab間の距離を定義すれば全点対最短路の問題と考えることができます。 n …
