問題（外部リンク） Prime Number | Aizu Online Judge 実装の概要 あるnが素数かどうかだけでなく、nまでの素数の個数を求める問題なので2,3,...nのように1つ1つ素数かどうかをチェックしていると間に合いません。 そのため、事前に「その数が素数かどうか…

問題（外部リンク） Sum of 4 Integers | Aizu Online Judge 実装の概要 使う数字の数が4つ、かつ全ての数字が1ケタと分かっているので全探索でも十分間に合います。 4重ループで解くのが自然だと思いますが、この実装ではあえて1重ループで記述し、各ケタの…

問題（外部リンク） Debt Hell | Aizu Online Judge 実装の概要 一週間ごとに5%の利子、さらに1000円未満を切り上げという、問題文にも書いてありますが本当にとんでもない闇金です。 複利計算なのでループを回しながら計算を行います。端数切り上げのタイミ…

問題（外部リンク） 1631 -- Bridging signals 実装の概要 動的計画法を用いて解きます。 配線が交わらないための条件は目的地のポート番号が{1,2,4,8,,,,}のように単調増加することです。そのためこの問題は最長増加部分列（LIS）の長さを求めるのと同じ方…

問題（外部リンク） Reverse Sequence | Aizu Online Judge 実装の概要 文字を逆順に出力する問題。実装例1ではループを逆方向に回すことによって実現しています。 一方、StringBufferのインスタンスを作成すればメソッドで逆の文字列をを生成できるので、実…

問題（外部リンク） 1065 -- Wooden Sticks 実装の概要 動的計画法を用いて解きます。 それぞれの棒には長さと重さが与えられていますが、分かりやすくするためにまず長さについて昇順にソートします。これによって「前の棒よりも重さが大きいか等しいならセ…

問題（外部リンク） GCD and LCM | Aizu Online Judge 実装の概要 GCD（最大公約数）とLCM（最小公倍数）の求め方については高校の教科書の通りなので特に説明は不要かと思いますが、手計算とは異なり剰余だけ求めれば計算可能です。 GCDとLCMは他の問題で使…

問題（外部リンク） 3181 -- Dollar Dayz 実装の概要 動的計画法で解きます。 決まった合計金額における品物の買い方のパターン数を問う問題ですが、例えば合計が$5なら「$1 $1 $1 $2」のように必ず安い順に購入すると決めると考えやすくなります。そこでdp[…

問題（外部リンク） 3046 -- Ant Counting 実装の概要 動的計画法を用います。 問題にあるように{1,2}と{2,1}などを重複して数えないように気をつける必要がありますが、そのためには「数字は必ず小さい順に並べる」と考えると分かりやすくなります。そしてd…

問題（外部リンク） Simultaneous Equation | Aizu Online Judge 実装の概要 連立方程式を解くために今回はガウスの消去法を使いました。 ガウスの消去法 - Wikipedia 行列の基本変形をやや強引な方法で進めているので、読みにくくなって申し訳ありません。 …

問題（外部リンク） Is it a Right Triangle? | Aizu Online Judge 実装の概要 与えられた3辺で直角三角形が作れるということは三平方の定理（最長辺の2乗=他の辺の2乗の和）が成り立つことと同値です。入力をソートしておけば最長辺が必ず一番後ろになるの…

問題（外部リンク） Digit Number | Aizu Online Judge 実装の概要 aとbの和をひたすら10で割り続け、ループの回数で桁数を判断します。 なお、実装例2のように和を文字列に変換してからその長さを出力するという方法でも解けます。 実装例1 public class Ma…

問題（外部リンク） List of Top 3 Hills | Aizu Online Judge 実装の概要 今回の場合は入力が整数かつ10個と決まっているため、ソートした上で配列の後ろから見れば高い順に表示できます。降順ソートのためにComparatorを使うこともできますが今回はそこま…

問題（外部リンク） 3616 -- Milking Time 実装の概要 「ある時点までに採れるミルクの量」を保存しつつ動的計画法で解きます。事前にインターバルを搾乳開始時を基準にソートし、その時間になったら直前までのミルクの量と新たに採れるミルクの量を足して「…

だいぶ前に参加したコンテストの問題ですが、しばらく解説を見ても作れないでいたのがようやくACになったので載せておきます。 問題（外部リンク） AtCoder Beginner Contest 065 - AtCoder Beginner Contest 065 | AtCoder 解法の概要 公式の解答にあるよう…

問題（外部サイト）QQ | Aizu Online Judge概要九九の式を順番に出力する問題。実装二重ループで実装しましたが、明確に81行の出力と分かっているのでいっそ全部ソース内に直書きして出力というのもありだったかもしれません。 public class Main { public s…

はじめまして。WrongAnsと申します。 趣味でよくオンラインジャッジなどに挑戦するので、その際に書いたコードや気づいたことなどについて記事を書いていきたいと思います。