2011-08-01から1ヶ月間の記事一覧
問題リンク Electro-Fly 解法 サンプルを見ての通り、x', y', z'を逐一計算していくと実行時間がとんでもないことになります。 まずx,y,zを個別に考えて、それぞれ何回計算を行ったら1に戻ってくるかを計算します。xについてx1回の計算で1に戻ってきたとする…
問題リンク Period 解法 除算の手順や循環の判定などは問題文にある通りです。 あとは実装するだけ。割り切れるケースなら難しくないですが、循環するケースの時は、2度目に出現した余りが最初何桁目に現れたかを調べればいいです。 ソース
問題リンク A Milk Shop 解法 i番目のお客さんは0〜i-1番目のお客さんの牛乳を注ぎきる時間の合計だけ待つ必要があります。最初の方にもの凄く注ぐのに時間のかかる人がいると、多くの人を長く待たせることになるので良くないことが分かります。最適なのは注…
問題リンク Doctor's Memorable Codes 解法 変換表を作ることが一番だるい問題です。表さえできればあとは変換していくだけです。 ソース
問題リンク Alphametic 解法 Xに0〜9の数字を入れてみて、計算式が成り立つかどうかを確かめます。 前問AOJ0109の流れを引きずって構文解析チックに書いてますが、式が「?+?=?」という形で決まっているので、splitなんかを使えば楽でしょう。 ソース
問題リンク Smart Calculator 解法 数式の構文解析問題です。 構文解析問題は1回解くことができれば他の問題でも十分応用できるかと思います。 問題文中にBNFがあればやりやすくなりますが、なければ自分で思い描くしかないです。 たぶん、この問題のような…
問題リンク Operation of Frequency of Appearance 解法 タイトルが重々しいですがただのやるだけ問題です。 配列nextを用意して、変換後の数列を格納します。 直前の配列aと異なる要素が1つも無ければ不動点となります。 ソース
問題リンク Carry a Cheese 解法 直方体は回転させてみればただの長方形になります。直方体なので3種類の長方形にすることができます。この長方形が円形の入り口に入るかどうかは、対角線が円の直径より短いかどうかでわかります。つまり、入力で縦横高さの…
問題リンク Discounts of Buckwheat 解法 A店B店C店でそれぞれ何袋買うかを決めます。入力が小さいので全探索可能です。 割引の処理がちょっと面倒です。 注意:そば粉 Xグラムをそろえるとき、Xグラムを超えてそば粉を買った時に値段がより安くなるパターン…
問題リンク Book Index 解法 Map>は語句がキーで、ページのリストがバリューです。 語句はプライオリティキューにも追加され、語句の昇順に取り出せます。 取り出したページのリストはCollections.sort()でページの昇順にできます。 ソース
問題リンク Magical Tiles 解法 現在地(x,y)をタイルの模様によって変化させ、'.'のマスに来ることができれば止まります。ループの判定は、「過去に訪れたことがあるタイルにまた訪れたらループである」ので、訪れたタイルにマークをつければいいと思います…
問題リンク Baseball Simulation 解法 進塁するときシングルヒットしかないので、2塁に人がいたら1塁にもいるし、3塁に人がいれば満塁です。なので、走者の数だけ覚えてればいいです(1と3塁だけに人がいるみたいなことは起こり得ない)。 得点は、満塁のと…
問題リンク Matrix-like Computation 解法 合計値を出すだけです。 5ケタ表示ですが、System.outにprintf()があるのでそれを使えばおkです ソース
問題リンク Aizu PR 解法 Stringのreplace()で一発です ソース
問題リンク Sale Result 解法 社員を表すクラスを作りました。社員番号、入力中の出現順、売上高のデータを持ち、出現順の昇順でソートできるようにしておきます。 int型だとオーバーフローしそうなので売上高のデータはlongです。 ソース
問題リンク Overlaps of Seals 解法 最良優先探索の方針で解きました。 空間を4分割していき、最もシールが重なっていそうなところから探索をかけます。 クラスRは探索空間を表し ・X座標の左端と右端 minx, maxx ・Y座標の上端と下端 miny, maxy ・空間の4…
問題リンク The Shortest Path on A Rhombic Path 解法 DPです。その地点に到達するときの最大値を格納します。 数字の配置がひし形で変則的なので、ひし形の半分で区切ってDPを埋めるといいと思います。 ソース
問題リンク The Code A Doctor Loved 解法 Mapで対応表を作って頑張りました。 かったるかったですが、表さえできてしまえばあとはやるだけです。 ソース
問題リンク Strange Mathematical Expression 解法 逆ポーランド記法の式を評価できれば勝ちです。Stackを使います。 ソース
問題リンク Patrol 解法 道を一筆書きできるかを判定する問題です。 頂点の次数を調べていき、次数が奇数の頂点が0もしくは2個ならば一筆書き可能です。 0個の場合にオイラーグラフと呼び、2個の場合に準オイラーグラフと呼びます。 前者は閉路を持ち、後者…
問題リンク Joseph's Potato 解法 ヨセフの問題です。 残り1人になるまでシミュレートしてもO(nm)なので間に合います。 ソース
問題リンク Search Engine 解法 "," "." " "の3文字は同じ区切り文字という意味で混在させておくと面倒です。 文字列中の",""."はreplace()を使って" "に置き換え、" "でsplit()します。 あとはsplitして得られた各文字列sの長さが3以上6以下かどうかを調べ…
問題リンク Era Name Transformation 解法 年月日を表すクラスEを作り、比較メソッドcompareToを作りました。 pre-meiji, meiji, taisho, showaについて、各年号の最終日をクラスEの配列eとしてで作っておきます。 入力された年月日fをpre-meijiから順に比べ…
問題リンク Flying Jenny 解法 乗り物の並びは4,1,4,1,2,1,2,1で固定です。先頭の乗り物を0〜7番の乗り場にしたときに何人残るかを全部試します。 乗り物を文字列で表現("41412121"など)すれば、辞書式で一番小さいものが答えになります。 ソース
問題リンク A Symmetric Point 解法 直線P1P2と直線QRの交点Pをもとめて、QPを倍伸ばしたところがRだと思ってやってみたがWAをくらい、じゃあもういいよ!って手計算で点Rを計算しました。 QRの中点はP1P2上にある QRとP1P2は直交する の2つの条件から連立…
問題リンク Leap Year 解法 0 ソース
問題リンク Square Searching 解法 右下の座標が(i,j)で1辺がwの正方形が作れるかは下準備をすればO(1)で判定できます。 sum[i][j]という2次元配列を用意します。これは(0,0)〜(i,j)の長方形に含まれる空きマスの数を表します。 このsumを使うとマップ上の任…
問題リンク Third Root 解法 3乗根を求めるための漸化式が載っているのでそれを実装します。 終了判定は q * 10^-5 未満ですが、ソースではq*10^-6になってるのは自分でもよくわかりません。 ソース
問題リンク Area of Polygon 解法 問題文にヘロンの公式が載っていますがスルーしました。 多角形の面積は外積を使って求めることができます。 ググればすぐに引っ掛かります。 ソース
問題リンク Magic Square 解法 魔方陣の作り方が問題文に載ってるのでそれを頑張って実装すれば勝ちです。 ソース