問題リンク e-market 概要 取引注文のリストが時系列順で与えられる。注文には、「取引主名」「取引種類」「対象商品」「価格」の4つの情報が含まれている。 取引種類はBUY, SELLの2つがある。 BUY取引注文を受け取った時、SELL取引注文の中で買い価格より小…

問題リンク Starship Hakodate-maru 概要 宇宙船函館丸には燃料タンクが2つある。タンク1にはある整数の3乗の値の量(n^3)だけ燃料を入れられる。タンク2にはある整数のn*(n+1)*(n+2)/6の量だけ燃料を入れられる。 今ある惑星で最大Nの量の燃料を補給できる。…

Volume0で現在公開されている問題全てについて記事を書くことができました！ ICPCのアジア地区大会が近付いてきているので、これからしばらくはVol11, Vol12辺りについて書こうと思っています。

問題リンク Path on a Grid 解法 与えられる壁の情報が厄介で扱いづらいので扱いやすい形に変えます。 座標を左上から順に0〜24と番号付けし、e[i][j]の2次元配列で座標i, jの間に壁があることを示すようにします。 次に移動ベクトルを作るのですが、上、右…

問題リンク Board Arrangements for Concentration Games 概要 4x4のボードがある。ここにA〜Hのカードが2枚ずつある。これら16枚のカードを並べる方法は何通りあるかを答えよ ただし、同じ文字が書かれたカードはそれらの相対距離が、予め決められた4種類の…

問題リンク Calculation of Expressions 概要 複素数の計算式を評価せよ 計算式中には2項演算子の+, -, *しか現れないため、単項演算子の+, -は登場しない。 演算子の優先順序は通常のものと一緒である。同じ強さのものが並んだ場合左側から処理される。 計…

問題リンク A Simple Offline Text Editor 概要 テキストエディタを作成せよ。 テキストは1行のみで、'a'-'z', 'A'-'Z', '0'-'9', '.', ',', ' 'の文字のみから形成される。 エディタにはカーソルがある。カーソルの初期位置は先頭である。 このエディタのwo…

問題リンク Area of Polygons 概要 座標がN個、時計回りに与えられる。このN多角形の面積を小数点以下1位まで求めよ ・Nは必ず3つ以上 ・2つの点が同じ場所にあることはない ・2本の辺が端点以外の場所で交わることはない これらが保証されている 解法 外積…

問題リンク Chairs Where Demanding People Sit 解法 シミュレート問題です。 椅子の状態を管理しておき、A〜Dの人に対応した座らせ方を実装します。 ソース

問題リンク Trouble in Artist Shinagawa's Artifact 解法 2つのサイコロが同じものであるかをチェックできるかがカギです。 1つのサイコロは転がしたりすることで24種類の状態を持ちます。 あとは頑張って調べます。 ソース

問題リンク Greatest Common Divisor: Euclidean Algorithm 解法 ユークリッドの互除法をやるだけです。 ソース

問題リンク Baseball Championship 解法 チームについて勝ち数、負け数を数えてソートするだけです。 ソース

問題リンク What is the Most Popular Shop in Tokaichi? 解法 売上の大きいところを記憶するだけです。 ソース

問題リンク Deven-Eleven 解法 AOJの本文中に肝心の図が無いので本家の問題文を参照するといいでしょう PCK2008本選。 6角形座標なので図を見て、移動ベクトルを作ります。ただ注意すべきはy座標が偶数か奇数かで移動ベクトルは変わるということです。移動の…

問題リンク Tsuruga Parking 解法 重いシミュレート問題です。定義を読んで根気強く実装するしかないと思います。 駐車場の状態を配列で作っておき、そこに車があと何分停車しているかを入れておきます。0は空車を表すことにします。 これを使って1分毎にシ…

問題リンク Baby Tree 解法 DPです。 dp[i][j]: i日目に肥料jを与えたときの最大成長度 という表を作ることができます。 初日は何を与えても成長度1なのでdp[0][i]は全て1です。 次の日以降は直前の日の状態から算出できます。 dp[i][j]を埋めたかったら、dp…

問題リンク Eleven Puzzle 解法 素直に20ステップまで幅優先探索を行うと状態数が多すぎて死んでしまいます。 なので両側探索を使いました。 ゴールの状態から20の半分の10ステップ以内で辿りつける状態を予め調べておきます。これをmとします。 そして、与…

問題リンク Convenient Location 解法 ある頂点から、自分以外の全ての頂点までの各々の最短経路長の総和が最小となる頂点番号を答える問題です。 ある頂点から別の頂点までの最短路が欲しいので全点間最短経路を求めるワーシャル・フロイド法を使います。 …

問題リンク Search 解法 2分探索における目的の値との比較が何回行われるかを数える問題です。 アルゴリズムは問題に乗っている通りです。 自分は比較を行うという部分をメソッド化しています。 回数を数えるコードを散在させないためです。が、この問題は単…

問題リンク Stoning Fortune 解法 幾何問題です。 3本の線分に0, 1, 2と番号付けしたとして、0と1, 1と2, 2と0の線分の交点を求めます。 交点が存在しなかったら三角形は作れません。 あとは3つの交点でできる三角形の面積を求めて大きさを見るだけです。線…

問題リンク Aizu Chicken 解法 会津地鶏を買う量の解をQとすると、Qを境に言いつけどおりの買い物ができるかどうかが分かれます。よってQについての2分探索を行います。Qが0として求まった場合は買い物失敗です。 ソース

問題リンク Goldbach's Conjecture II 解法 エラトステネスの篩を作ります。 あとは2素数であるかどうかを調べます。 ソース

問題リンク Tsuruga Castle 解法 やるだけ問題です。 ソース

問題リンク Black-and-White 解法 3*3で揃っているものを探すだけなのでやりやすい方法をどうぞ。 今回は、bを1、wを-1として置き換えて、各行、各列、各斜めに対して総和をとり、絶対値が3になっているところがあるかどうかで判定しました。 ソース

問題リンク Persistence 解法 解となる幅がWだとします。すると、W' ソース

問題リンク Stellar Performance of the Debunkey Family 解法 ストレートな最小全域木問題です。 UnionFind木を用いてクラスカル法によって最小全域木を求めます。 (UnionFindクラスはwakaba.wikiのものを利用させていただいています） ソース

問題リンク Mysterious Worm 解法 虫の長さは最大10。各部分が取りうるのは3色なので、虫の全状態数は3^10に収まります。 よって幅優先探索可能となります。 虫の隣り合った色が違う部分を見つけ、それらの色ではない最後の1色で塗り替えて状態遷移とします…

問題リンク TETORIS 解法 実装問題です。 ブロックを置くロジックと、行を消すロジックの2つをがんばって作ります。 行が揃っていたら、それより上の行全てを1段下にずらします。これを続けられるだけ続けます。 ソース

問題リンク What Color? 解法 "#xxxxxx"をsubstringし、Integer.parseInt()で16を渡すことで一気に0〜255に変換できます。 あとは色全てと比較して近い色を探します。 ソース

問題リンク A King in Hawaii 解法 BigIntegerにはn進数に直すメソッドがあるので一発です。 ソース