問題リンク Revenge of Champernowne Constant 概要 チャンパーノウン定数とは、"0."に続いて、正の整数を昇順に連続で並べたような無理数である。 "0"-"9"の文字で構成された文字列Sがチャンパーノウン定数の中で最初に出現する位置はどこか答えよ。答えは1…

問題リンク Save Your Privacy! 解法 ある人物iが犯人になりえるかを調べるためには、この人物が、情報漏洩したK人について知っていなければなりません。全ての人物についてこのチェックを行い、犯人となりえる人物がただ1人ならばその人物が犯人です。それ…

問題リンク Memory Leak 解法 構文解析+シミュレーションです。 Javaでは型がクラスの変数は全て参照なのでそれを流用することにして解きました。 確保した領域クラスRを作ります。メンバーにはメモリ量を持っています。 大きさ26のRの配列rを作り、変数A〜Z…

問題リンク Chicken or the Egg 解法 まとめると、次のように答えを求められます。 同じ単語が続いてる箇所で切る。 切ってできた文字列の中で一番単語数が多いものを選ぶ。複数ある場合は最初のものを選ぶ。 その文字列の最後の単語が答え。 eggとchickenを…

問題リンク Roads on Towns 解法 実は、答えとなるような道の結び方は、トタタとツテテの少なくとも一方が目的の街同士を直接結んだ形となります。よって、トタタを直接結んで、ツテテの頂点に対してダイクストラし、その逆も同様にやれば解が求まります。 …

問題リンク Elevator 解法 シミュレーションのようなDPのような解き方です。 エレベータの動かし方は、「荷物が存在する最上階の荷物を1つ下のフロアに最適に運ぶ」というのを繰り返せば答えとなります（解説の記憶が残っていました）。よって、ある解の荷物…

問題リンク CatChecker 解法 BNFの通りに解析を進めていき、解析を終えたときに正常に全ての文字を読むことができたらCatとなります。解析が途中で終わったり、読みのこしの部分が残っていたらRabbitです。 ソース

問題リンク Sort 解法 順列の状態は最大で 8! ＝ 40320 通りあります。最初に順列の各状態に対して番号付けを行います。次に、ソートの完了状態から各状態への最短コストをダイクストラで求めます。全ての状態の中の最短コストの最大値が解となります。 ソー…

問題リンク A-B Problem 解法 桁iで繰り下がりを忘れるかどうか2通りの選択肢があり、桁は高々10桁までしかないので、繰り下がりを忘れる箇所の選び方を全部試すことができます。 ソース

問題リンク Lucky Dip 解法 マップの各マスを領域と考えます。移動することができる領域同士は同じ領域だとみなすことができます。壁が1つ取り払われると、異なる領域同士だったものが互いに移動できるようになり、同じ領域になりえます。結局、領域をUnionF…

問題リンク Unequal Dice 解法 もう1回チャレンジできる面があるというのが面倒です。 そこで、数字が書かれている面が出る確率Rを求めます。 そして数字が書かれている面が出る各確率riをri/Rに置き換えたらなんか解けました。 確率とか期待値とかいつも適…

問題リンク Palindromic Anagram 解法 登場する各アルファベットの個数を数えます。次に文字列の長さNの偶奇によって場合わけします。 Nが偶数のとき、奇数個登場するアルファベットが1つ以上あったら回文は作れないので答えは0となります。そうでない場合、…

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

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

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

問題リンク A Way to Invite Friends 解法 X人の友達を誘える ⇔ X+1を含む区間[ai, bi]がX個以上ある となるので、区間の重なりの個数に注目します。 aiとbi+1の値でソートして重なっている区間をカウントします。aiの値なら+1、biの値なら-1となります。カ…

問題リンク Earth Invasion Diary of Miyabi-sensei 解法 F(n)をn人のドラキュラの中から本物を見つけるための比較回数とします。 n ここで、n人の中からx人だけ1つの皿の上に乗せると考えると、n人の集団が(x, x, n-2*x)の集団に分かれます。この集団に分け…

問題リンク On or Off 概要 大きさR*Cのグリッドのオフィスがある。任意の部屋の対について、それらの部屋間を移動する方法は必ず1通りしかない。 M個の仕事をする必要があり、その仕事をするための部屋(r, c)が決まっている。仕事はその部屋についた瞬間終…

問題リンク Butterfly 概要 後回し 解法 時間が[6〜22]の17通りしかないのでビットを立てることで2^17までの整数で時間帯を表現することができます。 デートに使う時間は[S, E)という半開区間であることに注意してビットを立てます。 各男性のデートに使う時…

問題リンク Infinity Maze 概要 後回し 解法 u[H][W][D]: (H, W)に向きDで最初に到達したときのステップ数 という表を作って行きます。 10^18もステップがありますが、ボード上の状態は40000しかないので、必ずどこかでループが生じます。 長さKのループに入…