問題（外部リンク） B: Postal Code - AtCoder Beginner Contest 084 | AtCoder 実装の概要 模範解答ではループで１文字ずつ数字かどうか（あるいはハイフンかどうか）をチェックしていました。 前後の数字の桁数がはっきりa,bと決まっているため特に正規表…

問題（外部リンク） Parallelism | Aizu Online Judge 実装の概要 2直線の平行を判定するAPIが標準では備わっていないので自力実装を行います。（2線分の交差判定であれば存在します） 2直線が平行ということはそれぞれの傾きが等しいということなので、入力…

問題（外部リンク） Capitalize | Aizu Online Judge 実装の概要 文字列に含まれる小文字を全て大文字に変換するだけならStringクラスのtoUpperCase()が便利です。Characterクラスにも同様なメソッドがありますが、そちらは一文字ずつなのでループが必要にな…

問題（外部リンク） Factorial | Aizu Online Judge 実装の概要 が成り立つので再帰を用いて解きます。スタックオーバーフローについてはnが20以下となっているため特に気にする必要はありません。 終了条件についてはきちんと定義しておく必要があります。…

問題（外部リンク） Sorting Five Numbers | Aizu Online Judge 実装の概要 今回は単純な並び替えの問題なので、Arrays.sort()を使いました。仮に自分でソート部を実装する場合は、数字は5個と決まっているため書きやすいバブルソートなどでも大丈夫です。 …

問題（外部リンク） Caesar Cipher | Aizu Online Judge 実装の概要 問題の制約に「thisかthatかtheのいずれかを含む」と書いてあるので、若干強引ではありますが「試しに各文字をiずつずらした文字列を作る」→「前述のキーワードを含むかチェックする」とい…

問題（外部リンク） Treasure Hunt | Aizu Online Judge 実装の概要 中途半端な角度の移動も有り得るため、移動後の座標の計算に三角関数を用いる必要があります。与えられる角度は今向いている向きからの相対的な角度なので、現在向いている角度も常に保持…

問題（外部リンク） National Budget | Aizu Online Judge 実装の概要 long型でも表せないような桁数の足し算なのでBigInteger型を使います。 桁数チェックはBigIntegerを文字列に変換して文字数を取得することでシンプルに行うことができます。 public clas…

問題（外部リンク） Integral | Aizu Online Judge 実装の概要 高校の教科書にも出てくる区分求積法に近いことを行う問題です。とは言っても、高さがであるような短冊型の図形の面積をひたすら足していく処理なのでプログラムにすると比較的シンプルになりま…

問題（外部リンク） Switching Railroad Cars | Aizu Online Judge 実装の概要 0が入力された際に出ていくのは「現在停まっている中で最後に行き止まりに入ってきた車両」なのでスタックを使うと簡単に記述することができます。即ち、車両が行き止まりに入る…

問題（外部リンク） A Point in a Triangle | Aizu Online Judge 実装の概要 今回はあまり計算式とかを考えずにシンプルに済ませたかったので、java.awt.Polygonクラスを使用しました。これを使えば、三角形に限らず任意の多角形について同様に解くことがで…

リアルタイム参戦ではありませんがA〜D問題まで一通り解いてみました。AとBは大体解説と同じようなコードになると思うので省略しますが、特にD問題は解説と違う方法が真っ先に浮かんだのでその方法について紹介します。 問題（外部リンク） AtCoder Beginner…

問題（外部リンク） Kakezan | Aizu Online Judge 実装の概要 任意の桁で区切りを入れて計算する処理は記述を簡単にするためにあえて文字列のまま処理をしてみました。実行時間に不安はありましたが無事に制限時間内に実行が終了しました。 今回の問題では「…

問題（外部リンク） Drawing Lots | Aizu Online Judge 実装の概要 Sample Inputの場合、時刻0で(2,4)間に入れ替え発生、時刻1で(3,5)間に入れ替え発生…と解釈することができます。まずは入れ替えに関わるデータを配列に保存しておきます。このとき、a→bだけ…

問題（外部リンク） Circumscribed Circle of a Triangle | Aizu Online Judge 実装の概要 三角形ABCの外接円の中心は、AB,BC,CAの交点にあります。もちろんこの中の2つの直線を選んで計算すれば十分です。 この実装では方程式そのものを表すクラスと連立方…

問題（外部リンク） 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 解法の概要 公式の解答にあるよう…