問題リンク Ohgas' Fortune 解法 N種類の運用方法で得られるお金を全部計算して最大値を出すだけです。 ソース

問題リンク Water Tank 解法 実装問題です。 ある仕切りの場所に水を量V流していき、溢れた水の量V'を隣へ流すという処理を再帰的にします。水が溢れ、水位が隣と同じになったら以降その2つは同じ水槽として扱う、など面倒な処理が多いです。 気合いで乗り切…

問題リンク Circle and Points 解法 この問題、実は AOJ0090 Overlaps of Sealsとやりたいことは全く一緒です。なのでこちらを参照してください。平面を4つに区切って行き、解がよさそうなところを探していく最良優先探索で解けます。 ソース

問題リンク Unit Fraction Partition 解法 全探索＋枝刈り問題です。 求めたい値がp/qで有理数となるのですが、浮動小数点で扱うと結構厄介なので分数の形で扱った方がいいと思います。 a/bとp/qが等しいかどうかはa*q = b*pが成立するのと同値なので、結局…

問題リンク Red and Black 解法 深さ優先探索、幅優先探索、なんでもいいと思います。 とてもシンプルな探索問題だと思います。 ソース

問題リンク Hanafuda Shuffle 解法 シミュレート問題です。シャッフルを頑張って実装します。 ただ、最終的な山の一番上のカードさえ分かればいいので、シャッフルの手順を逆順に追って、一番上のカードがどこから来ているかを調べる方法があります。こちら…

問題リンク Square Carpets 概要 W*Hのグリッドにタイルがあり、汚れているものと汚れていないものがある。全ての汚れているタイルを正方形のカーペットで覆って隠すとき、必要なカーペットの最小個数を求めよ。ただし、カーペットは汚れていないタイルを覆…

問題リンク The Genome Database of All Space Life 解法 構文解析を行いつつ、長さ i の文字列を作っていきます。 解いたのは結構前なのですが、今見るとBNFは次のようなノリでしょう（あくまでノリです。どうせ正確な記法じゃないのです） Exp = ( NumFact…

問題リンク Curling 2.0 解法 深さ優先探索です。最大でも10回しか潜らないので4^10 ≒ 10^6くらいしか探索空間がありません。 これに、今の深さが現在の最適解を更新しないならば枝刈りという処理を加えれば大丈夫です。 ソース

問題リンク Hexerpents of Hexwamp 解法 方針は幅優先探索なのですが、ある蛇の状態から次の遷移先を作るのが非常に厄介です。その都度遷移先を計算していたら時間が厳しくなるので、最初に一括で遷移先状態を計算しておき、幅優先探索中はキャッシュされた…

問題リンク Organize Your Train part II 解法 列車を2つに分割し、それぞれに対して「逆さまにする」「順序を逆にする」の選択肢があり、8通りのパターンがあります。 分割する個所は高々72箇所なので全てを試すことができます。 ソース

問題リンク Dirichlet's Theorem on Arithmetic Progressions 解法 大きさ1000000のエラトステネスの篩を作って、n番目の素数を探すだけです。 ソース

問題リンク Building a Space Station 概要 N個の球状のスペースステーションの3次元座標(x,y,z)と半径rが与えられる。 あるスペースステーションから全てのスペースステーションに移動できるように橋を架けるとき、架ける橋の長さの合計を最小にせよ。 スペ…

問題リンク The Secret Number 概要 W*Hのボードに、数字もしくはアルファベットが書いてある。あるマスの数字はその下、もしくは右にある数字と繋げて読むことができる。このとき、ボードの中で最も数が大きくなる数字の列を答えよ。 W+H 解法 DPです。マス…

問題リンク Get Many Persimmon Trees 概要 W*Hの大きさの土地にN個の木がある。S*Tの大きさの長方形で囲むことができる最大の木の本数を答えよ。 1 1 1 解法 問題のサイズが小さいので全探索できます。 ソース

問題リンク When Can We Meet? 概要 N人のメンバーがいる。N人は会議に出席できる日にちを申告している。 会議はQ人以上いないと成立しない。Q人以上出席し、最も人数の集まる日を答えよ。そのような日が複数ある場合は日が近いものを答えよ。Q人以上集まれ…

問題リンク What is the Number in my Mind ? 概要 L桁のヒットアンドブローゲームを行う。H個のヒントが与えられるので、正解の数列を求めよ。そのような数列が無かったり、2つ以上存在する場合は"NO"とせよ。 H個のヒントにはL桁の数列tryとそれに対するhi…

問題リンク Kanglish:Analysis on Artificial Language 概要 Kanglishという言語は26個のアルファベットに加え、さらに2文字で1文字を表す語12個を加えた38文字からなるものである。 今文章が与えられる。38個の文字それぞれについて、右隣にきている語の中…

問題リンク Pile Up! 概要 1〜Nの番号が書かれたブロックがある。最初は全て床に転がっている。 2つの整数の命令リストが与えられ、ロボットはそれに従ってブロックを動かす。最終的にできたブロックの塔全ての高さを昇順に答えよ。 命令はX, Yの整数で構成…

問題リンク Exploring Caves 概要 最初(0, 0)の点にいる。移動量のリストが与えられる。これらの移動の中でスタート地点からの距離が最も遠かった点の位置を答えよ。そのような点が複数ある場合はx座標のより大きいものを答えよ。 解法 入力で与えられた通り…

問題リンク Jigsaw Puzzles for Computers 概要 9個のジグソーパズルのピースが与えられる。これらを使って3*3のパズルを完成できるような置き方は何通りあるかを答えよ。 ピースにはW,R,G,Bとこれら小文字の計8文字のうち4つが書かれている。ピースを並べた…

問題リンク Multi-column List 概要 文章がいくつか与えられるので、それをmulti-column listとして出力せよ。 このリストは1ページにつき、高さplen、横幅widthのカラムがcnum個続いている。カラムの間にはcspace個の空白が入る。文章が1行に入り切らない場…

問題リンク Get a Rectangular Field 概要 5*5のマスに0か1が書かれている。1のみを含む長方形を作るとき、できる最大面積を答えよ。 解法 問題のサイズが非常に小さいので、(i, j)を左上のマスとして幅w, 高さhの長方形が作れるかというのを全て試すことが…

問題リンク Cyber Guardian 概要 N個のパケットフィルタとM個のパケットが与えられる。M個のパケットの中で送信が許されるものを答えよ。 パケットは送信元アドレスと送信先アドレスと本文からなる。アドレスは'0'〜'9'と'?'の文字からなる8文字の文字列で表…

問題リンク Patience 概要 Patienceというゲームをする。1〜5が書かれたカードが各4枚あり、それを5*4に並べる。あるカードに注目し、その隣接8マスのカードの中に同じものがあればその2枚を取り除くことができる。取り除けるペアが複数あっても1度に取り除…

問題リンク Fermat's Last Theorem 概要 整数zが与えられる。z^3を超えないx^3+y^3を見つけ、z^3-(x^3+y^3)を計算せよ。xとyは0より大きい整数とする。 1 解法 iを1, jをzとします。 i^3+j^3がzを超えたならjを1つ減らし、そうでないならばiを1つ増やします…

問題リンク A Long Ride on a Railway 概要 N個の駅とM個の路線がある。路線には長さがある。路線の最長パスの長さとその経路を答えよ。 経路は辞書順比較で一番小さいものを答えよ。 1 1 解法 グラフにおける最長パスを求めるのは普通は困難ですが、グラフ…

問題リンク Spiral Footrace 概要 座標(0, 0)に北を向いて立っている。N個の点が与えられる。N個の点を順番に辿り、最後の点についた時の総距離を答えよ。 点を辿る順番は、向いている方向とその点のある方向との角度が一番小さいものとする。 1 0 解法 幾何…

問題リンク Factorization of Quadratic Formula 概要 2次方程式の整数係数a, b, cが与えられる。これを因数分解し、(px+q)(rx+s)としたときのp, q, r, sを答えよ。 但し、p, q, r, sは全て整数であること。また、0 解法 まず、2次方程式の解の公式の判別式D…

問題リンク Unable Count 概要 3つの整数N, a, bが与えられる。1〜Nの整数の中で、a*i+b*jの形で表現できるもの(i, jは非負整数)の個数を答えよ。 N, a, b 解法 DPです。整数xはx-a, x-bのいずれかが表現できれば表現できることになります。 ソース