問題リンク Illumination 解法 建物があるマスにおいて、隣接している屋外のマスの数だけ飾りが必要になります。よって、屋外であるかどうかの判定表を先に作ります。適当な屋外のマス( (0,0)など )から幅優先探索をかければ作れます。あとは、建物マスにつ…

問題リンク Pasta 解法 DPもといメモ化探索です。 dp[v][s][c]: V日目からパスタSを厳密にC日間続けたときのV〜N日目の予定の組み合わせ数 という表を埋めることで解けます。 各パスタを1日続ける場合、2日続ける場合から予定が始まるので、最終的な答えは (…

問題リンク Best Pizza 解法 DPです。 dp[i][p]: i番目までのトッピングとpドルを使って得られる最大カロリー という表を埋めれば解けます。 ピザには生地を必ず使わなければならないので、表を埋めるときに、トッピングだけからなるカロリーを計算してしま…

問題リンク Soccer 解法 勝ち点計算してから順位付けするだけです。 クラスを作るとすっきり書けると思います。 ソース

問題リンク Lunch 解法 パスタの最小 + ジュースの最小 - 50 を求めるだけです。 ソース

問題リンク Shopping in JOI Kingdom 解法 ある1本の道に着目し、この道の上でショッピングモールからもっとも離れている場所はどこかを考えるのが方針です。そのためには、道の両端にある町それぞれについてショッピングモールとの最短距離が求まっていない…

問題リンク Books 解法 「ジャンルGの本の中からX冊を売るときの最大売値」は売値が高いものから売った場合になります。そのときの売値は 売値の大きいX冊の総和+(X-1)*X です。この値を全てのジャンル、売り冊数について求めておきます。 これを求めておく…

問題リンク Planetary Exploration 解法 sj[i][j]: (1, 1)-(i, j)の区画に現れる'J'の総数 という意味の表を'O'と'I'についても作ります。 (a, b)-(c, d)のクエリについて、この長方形に表れる'J'の個数は sj[c][d] - sj[a-1][d] - sj[c][b-1] + sj[a-1][b-1…

問題リンク Dice 解法 サイコロをきちんと実装できればやるだけ問題となります。 自分は手元にライブラリがあったのでそれを使うだけでした。 ソース

問題リンク Data Conversion 解法 変換表はMapで作りました。 作る文字列の長さは最大で10^8近くなってStringを+で連結していくとまずTLEするでしょう。 StringBuilderを使えば高速です。 ソース

問題リンク Card Game 解法 ルール通りに得点を計算します。 ソース

問題リンク Whist 概要 トランプのホイストを、南北チームと東西チームに分かれて行う。切り札の柄と、4人のカードの出し方が与えられるので勝利チームとその得点を答えよ。親は西にいる人なので、一番最初の台札は北の人が出す。 解法 Wikiのルールを読みそ…

問題リンク Missing Numbers 概要 (p+1)行(s+1)列からなる売上表がある。各行のs+1列目はその行の売上合計、各列のp+1行目はその列の売上合計を表す。 売上表の一部が欠損しており復元したい。復元の仕方がただ1通りに求まるならば復元し、復元方法が複数あ…

問題リンク Space-Time Sugoroku Road 解法 マスiに停まったら最終的にどのマスへ行くのか、もしくはループに陥るのかを前計算します。あとは、これを使って幅優先探索します。 ソース

問題リンク My friends are small 解法 強引気味なメモ化探索で解きました。 まず思いついた方針は、重さwiを降順でソートし、 mem[i][j][k]: リュックの残り重量j、i番目以前の重さで使用しなかったものの最小値がkのとき、i番目以降を使ってリュックにつめ…

問題リンク Dessert Witch 解法 問題文の通りにシミュレーションを行うだけです。 位置(i, j)にクッキーcを置いたときに8方向それぞれについて何個のクッキーが取れるかを返すメソッドを作ると少しはやりやすくなると思います。 ソース

問題リンク Divisor is the Conqueror 概要 1〜13の数字が書かれたカードをN枚持っている。 最初は手札のうち任意の1枚を場に出す。2枚目以降は、場に出ているカードの総和Sを割り切る数字が書かれたカードしか出せない。このルールの下でN枚のカード全てを…

問題リンク Kaeru Jump 概要 H*Wの大きさの池に葉っぱと1匹のカエルがいる。カエルは上下左右へ飛ぶ方向を決めたら、その方向の一番近い葉っぱに飛ぶ。このとき、飛ぶ前に乗っていた葉っぱは消えてなくなる。また、カエルは自分が向いている方向の真反対の方…

問題リンク UTF-8 解法 DPです。 dp[i][j]: iバイト目をjバイト文字の先頭と解釈したときのiバイト目以降の解釈の組み合わせ数 という表を後ろのバイトから埋めていけば解けます。 iバイト目をjバイト文字と解釈する方法を説明します。 まず、マスクが0や1の…

問題リンク Amazing Graze 解法 Rがそれなりに小さいのと、2つの円が重なり合ってることがないという制約があるので、1つのエネルギー弾にグレイズしている戦闘機はごく限られた数しかないことが予想できます。弾の近辺にある戦闘機のみを調べたいので、平面…

問題リンク Card Game 解法 ジャッキーのカードを出す順番は入力のまま固定、ゲイツの手札について9!通りの出し方を試してみよう → あれ？サンプルと答えが合ってるんですけど・・・？ → まさかと思って提出 → Accepted → うをっ！？ 確率とは不思議なものﾃﾞ…

問題リンク Rhythm Machine 解法 N個それぞれのリズムの最短表現を作った後、それらを合わせた最短表現を作る、というステップで解けます。 各リズムの最短表現は最大公約数を使って作ることができます。[和音の個数]と[音が鳴る小節k]全てのGCDをとります(0…

問題リンク Colored Octahedra 概要 8枚の色のついた正三角形が与えられる。これらを使って作れる正八面体は何種類か答えよ。 1つの八面体を回転させて別の八面体と一致したとき、これらは同じ種類であるとする。 解法 全探索です。 Setにこれまで作った八面…

問題リンク Authentication Level 解法 a[i] (0 という表を２つのマップについて作って解を調べる、というのが方針です。 マップの大きさが最大500*500と大きめなので少し工夫しないとTLEに引っかかると思います。 入り口を訪れたら、次の訪問先の候補は隣接…

問題リンク Geometric Map 概要 N本の線分で表現された平面の地図がある。 線分には道路の意味を持つものと標識の意味をもつものがある。 道路はその両端点が交差点となっており、他の道路と接続している。道路同士が交差したり、オーバーラップすることはな…

問題リンク Cubic Eight-Puzzle 概要 図3のようなサイコロと、3*3のグリッドがある。グリッドの初期状態は図4のような形であり、空マスとなる座標は入力で与えられる。1ステップにつき、サイコロを1つだけ空マスへ転がすことができる。入力で与えられる目標…