AOJ Volume21
問題リンク Dial Lock 概要 K桁のダイヤルロックがある。範囲[s, t](0 1 解法 DPの方針で考えていましたが、DFSで解きました。 ダイヤルの左側の数字sから考えていき、S_sとT_sの数字が違えば、数字を合わせるように回します。このとき、回す範囲の右端t (s …
問題リンク Text Justification 概要 N個の単語長と幅Wが指定される。単語は入力の順に並べる。このとき、1行の文字幅がWに近付くように、改行を挿入できる。単語の途中に改行を入れることはできない。以下の方法にのっとって、単語の並べ方のコストを算出す…
問題リンク Can I go there? 解法 長らく悩んでいた問題なんですが、折れて答えを調べました。 次のすげぇ性質を使うようです行列A^kの(i, j)成分を、頂点iから頂点jへkステップで到達できるなら1、そうでないなら0、と決めると A^1 = グラフの隣接行列 A^m …
問題リンク Addition Game 解法 気づいたら簡単系の問題です。 少なめの桁数だと全ての通りをシミュレートできるので色々試してみました。すると、どんな取り方をしても勝者が必ず一方にだけ偏りました。そこで、「どんな取り方をしても勝者は変わらない」と…
問題リンク Finding the Top RPS Player 概要 N人の人を集め、じゃんけんを行う。 N人は最初0勝である。ゲームは1ターンに同時に任意の数だけ試合が行われる。ただし、試合は連勝数の等しい人同士のみ行う事が出来る。k連勝同士の人が試合をすると勝った方が…
問題リンク Angel Stairs 解法 逆向きに考えます。 まず、N+1段目に降り立つには、直前にNかN-1段目にいることになります。 N段目にいたとします。このN段目にいるには、Tnを踏んでSmの音を出さないといけないです。そして、TnをSmの音で出すためにどう踏む…
問題リンク Champernowne Constant 概要 Champernowne定数とは、"0."の後ろに正の数を連続で並べたような無理数の事である。 0.1234567891011121314... 2つの正の整数NとKが与えられる。Champernowne定数の小数点以下N位からK文字を求めよ。 1 1 解法 区間分…
問題リンク Reverse a Road 概要 1〜Nまでの番号がついた街と、M本の有向路(番号1〜M)がある。街SからTまでの最短距離を求めよ。 ただし、M本の辺のうち1本だけ向きを逆向きにすることができる。最短距離を得るために変えた辺の番号も答えよ。そのような辺が…
問題リンク Eleven Lover 概要 '0'〜'9'の文字からなる文字列Sが与えられる。Sの連続部分文字列で、それが11の倍数で正の数であるものがいくつあるかを答えよ。ただし、0が先頭に続いているものはカウントしないこと。 以下のことが保証されている S 答えは3…
問題リンク Whist 概要 トランプのホイストを、南北チームと東西チームに分かれて行う。切り札の柄と、4人のカードの出し方が与えられるので勝利チームとその得点を答えよ。親は西にいる人なので、一番最初の台札は北の人が出す。 解法 Wikiのルールを読みそ…
問題リンク Card Game 解法 ジャッキーのカードを出す順番は入力のまま固定、ゲイツの手札について9!通りの出し方を試してみよう → あれ？サンプルと答えが合ってるんですけど・・・？ → まさかと思って提出 → Accepted → うをっ！？ 確率とは不思議なものﾃﾞ…
問題リンク Rhythm Machine 解法 N個それぞれのリズムの最短表現を作った後、それらを合わせた最短表現を作る、というステップで解けます。 各リズムの最短表現は最大公約数を使って作ることができます。[和音の個数]と[音が鳴る小節k]全てのGCDをとります(0…
問題リンク Colored Octahedra 概要 8枚の色のついた正三角形が与えられる。これらを使って作れる正八面体は何種類か答えよ。 1つの八面体を回転させて別の八面体と一致したとき、これらは同じ種類であるとする。 解法 全探索です。 Setにこれまで作った八面…
問題リンク Time Trial 概要 W*Hのマップがある。 マップには岩とパネルが3つずつあり、全ての岩をパネルの上に運びたい。 人は1ステップにつき、上下左右に動ける。進んだ先に岩があった場合、その先が壁や別の岩でなければ押すことができる。 このパズルを…
問題リンク Deadly Dice Game 概要 長さNの円形のボードがある。ボードの各マスは黒色か赤色である。 初期位置を任意に選ぶことができる。サイコロを振って出た目の数だけ時計回りに進む。サイコロをT回振ったとき最終的に赤色のマスに停まる確率の最大値を…
問題リンク Left Hand Rule 概要 W*Hの長方形の壁の状態が与えられる。長方形の周囲には1か所だけ長さ1の穴が空いているが他の箇所は全て壁になっている。この穴が入口となる。入口から入って左手伝いに進んで行ったとき、目標のマス目に到達するのは何ステ…
問題リンク Luigi's Tavern 概要 H人の勇者、W人の戦士、C人の僧侶、M人の魔法使いがいる。彼らを招いてパーティーを開きたい。パーティーが成立するための条件は以下の通り ・勇者は必ずいなければならない ・パーティーに参加している勇者と戦士は親しくな…
問題リンク Strange String Manipulation 概要 N個の整数Ii(1 ここで、擬似乱数Riを次のようにとる。 R0 = S Ri = (A * R_i-1 + C) MOD M (1 入力数列Iから次の数列Oを得る。 Oi = (Ii + Ri) MOD M 数列OのエントロピーHを最小にするようなパラメータS, A, C…
問題リンク Ninja Legend 概要 H*Wの大きさのマップがある。マップは '%': 出入り口 '#': 壁 '.': 床 '^': 落とし穴 '*': 宝 で構成されている。忍者は出入り口から侵入し、出入り口から脱出する。 忍者は1単位時間に1マス進むことができる。落とし穴に進入…
問題リンク Erratic Sleep Habits 概要 長さTの起床時間tiのサイクルとN個の仕事リストが与えられる。仕事はDi日にMi時から始まる。Di日にMi時以前に起きればこの仕事をすることができる(ti 薬を飲むことで起床時間のサイクルを強制的に最初に戻すことができ…
問題リンク Adaptive Time Slicing Quantization 概要 N個の[0.0, 1.0]の実数値列と整数M, Lが与えられる。 実数値列をM個の区間に分割する。ただしどの区間も最低2つ以上の要素を持たなければならない。更に、各区間毎に以下のようにして二乗誤差を計算する…
問題リンク Bitwise Kingdom 概要 [0, 2^N)の整数を表すN文字のビット文字列の中でM番目に小さいものを求めよ。 ただし、文字列の比較順序は次の順序で行われる 1. 文字列中に含まれる1の数が多い方が大きい 2. 1の数が同じならば辞書式で大きい方が大きい 1…
問題リンク Girls' Party 概要 ある整数Nと円形に並んだBチームとGチームの人たちが入力で与えられる。時計回りに数えていき、N人目の人が輪から外れる。輪から外れた次の人から再びN人目が輪から外れる。円がBチームのみ、もしくはGチームのみになるまでこ…
問題リンク Differential Pulse Code Modulation 解法 DPです。 dp[i][x]: i番目の信号を数xで復号化したときの最小値 という表を作れば解けます。配列が2本あれば十分です。 ソース
問題リンク Moonlight Farm 解法 収入: F*S*M-P 時間: A+B+C+(D+E)*M 変数が沢山ありますが要はこういうことです。 ソース
問題リンク Sum of Consecutive Integers 解法 連続する列の先頭の数字を決めて、和をとってみるだけです。 ソース
問題リンク A Book Shop With a Frequent Greetings 解法 シミュレート問題です。 店員iに時間tに唱和を開始させるというイベントを管理します。 各店員には最後に唱和を終了した時刻last[i]を持たせます。 (i, t)のイベントが発生したとき、店員iが唱和する…
問題リンク Unit Converter 解法 数値を文字列Tと見なします。Tから'.'を除いておきます。 0でない数値が初めて出現するインデックスをkとすると、有効数字KはT.length - kとなります。 また、pを小数点が右側につく桁のインデックスだとします(入力に小数点…
問題リンク Mirror Cave 解法 (Linの位置, Renの位置)をノードにした幅優先探索で解けます。状態数は50^4なのでメモリもなんとか大丈夫です。 どちらか一方だけがゴールを踏んだ場合、それから先の状態を探索してはならないということに注意してBFSを書くだ…
問題リンク Restrictive Filesystem 解法 区間の集合の管理を頑張る問題です。 空いているセクタの区間の集合をL、識別子kの区間の集合をL_kとします。 コマンドRのとき、全てのL_kの中にセクタ番号を含むものがあるかを探します。 コマンドWのとき、Lの先頭…
