問題リンク Area Separation 解法 直線を1本引くたびに面がいくつ増えたかを数えていきます。 直線を1本引いたら増える面の数は 境界線上でない場所で登場する交点の数 + 1 です。交点の数というのはユニークな交点の事を指し、複数の直線と同じ場所で重なっ…

問題リンク Ben Toh 解法 DPです。 dp[ n ]: n日間に得られる弁当の個数の期待値 の表を埋めて解きます。 n日間の期間があり、初日から連続してk日間弁当を獲得できている場合を考えます、またこの状態になる確率をp、次の弁当獲得確率をwinとします。ここで…

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

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

問題リンク Search of Concatenated Strings 概要 N個の文字列Ei と文字列Sが与えられる。Eiの各要素を1回ずつ連結した文字列が現れる箇所はSの中にいくつあるか答えよ。Eiの連結する順番は任意でよい。例えば、Eiが"a"と"b"であれば、"ab"もしくは"ba"が探…

問題リンク Eleven Lover 概要 '0'〜'9'の文字からなる文字列Sが与えられる。Sの連続部分文字列で、それが11の倍数で正の数であるものがいくつあるかを答えよ。ただし、0が先頭に続いているものはカウントしないこと。 以下のことが保証されている S 答えは3…

問題リンク Dividing Snacks 解法 DPです。 dp[ i ][ j ][ k ]: 左からiミリメートルまでを考えて、k個分のお菓子を得るための最小コスト。j = 0なら、場所 i を切らない場合で、j = 1なら場所 i を切ることを表す という表を埋めて解きます。 初期値はdp[0]…

問題リンク Malfatti Circles 概要 三角形の頂点が反時計回りに与えられる。この三角形の中に円を3つ内接させる。その条件は、 円は2本の三角形の辺と接していて且つ他の2つの円と接している である。この条件を満たす3つの円の半径を答えよ。誤差は10^-4よ…

問題リンク Concert Hall Scheduling 概要 コンサートホールが2つある。N個の利用申請があり、各申請の内容は、ホールを1つ期間[i, j]の間だけ費用wで借りたいというものである。ホールを[i, j]の間貸し出している期間中、他の利用者はそのホールを一切利用…

問題リンク Long Distance Taxi 概要 ガソリンが最大capまで積めるタクシーがある。タクシーはガソリン1毎に10km走ることができる。タクシーが町SからTまでガス欠を起こすことなく走るとき、その最短距離を答えよ。辿りつけない場合は-1とせよ。 道路がN本あ…

問題リンク Shuffle 解法 数字が連続しているカードをまとめて区間としてシャッフル毎に区間を管理するのが方針です。 最終的に意味のあるカードの山はp〜q番目の部分だけなので、この部分のみを区間の初期値とし、シャッフルを逆に辿るようにしていきます。…

問題リンク String With Rings 解法 ? えー、先に言っておきますと真っ当な方法でAcceptに辿りついていません。 真面目なプログラムで解きたい方の疑問には答えられません、よしなに。以下、自分の思考の変遷をつらっと書きます。1. 反復深化法でいこう 到達…

問題リンク JOI Flag 解法 ビットDPで解きました。 旗の種類は3^(?の数)だけあります。求めたいのは良い旗ですが、その余事象である悪い旗を数えても、解が求まります。 左上からマスを決定するとして、(i, j)のマスXについて考えます。もしNマス前に、"JO"…

問題リンク Zig-Zag Numbers 解法 DPもといメモ化探索で解きました。 扱う数値の範囲が異常に広く、更にその中のMの倍数にしか興味がないというのが厄介なところです。500桁近いある値がMの倍数かを判定するのもままならないかもしれません(自分がそうでした…

問題リンク Bug Party 解法 「X匹の虫をシャーレに入れることができるか」というXについて２分探索して解きました。 各Xについてのチェックについて説明します。 まず、虫をX匹選んだとして、許容量の一番小さい虫がボトルネックとなります。その虫の放出量…

問題リンク Reindeer with no sense of direction 解法 プレゼントの置き順をそのまま追おうとすると４方向＋その中のどこに置くかで遷移先が多いですが、置いたプレゼントを逆に辿ろうとすると、最初にぶつかったプレゼントを取るしか選択肢がないので探索…

問題リンク Squid Multiplication 解法 a0を頑張って特定します。a0が決まると、数列Bの中の偶数のものをa0で割ることで数列Aの奇数が作り出せます。 数列Bの2つの偶数のものbi, bjは bi = a0 * ai bj = a0 * aj となっています。また、Bの中の奇数の中にはa…

問題リンク Alien Messages 解法 全探索+枝刈りで解けました。 ある方向から進入して別のある方向へ出て行くと考えられるので、その動き方は6通りあります。 石像のないマス全てにいずれかの動き方をセットし、1つの閉路ができるかをチェックします。 単純に…

問題リンク Cosmic Market 解法 最終的に立っている人の数が求めたい答えとなります。 同じ1列、1行に複数個のクエリが来た場合、答えに影響するのは一番最後のクエリだけです。なのでQ個のクエリを最初に全て読み込んでしまって、逆から処理していきます。…

問題リンク The Morning after Halloween 概要 W*Hの大きさのオバケ屋敷がある。オバケはN匹存在する。 オバケはアルファベット小文字で表され、それぞれ定位置へ移動したい。各オバケの定位置は対応するアルファベットの大文字で表される。オバケは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に置き換えたらなんか解けました。 確率とか期待値とかいつも適…

問題リンク Usaneko Matrix 解法 各行、各列、＼のライン、／のライン上に登場した数字の数を記録します。各ライン上のカウントがnになったら「直線状に並んでいるもの」が1つできたことになります。 注意としてこの方法だと、n=1のとき、カードの数字xが登…

問題リンク Dimensional Analysis 解法 各組み立て量は A^a * B^b * C^c * D^d * E^e の形になるので指数部を並べた配列で表せます(基本量は5個まで)。 X * Yなら指数の和、X / Yなら指数の差をとります。 X + Y、X - Yのとき、双方の配列が全く同じかどうか…

問題リンク Live Schedule 解法 DPです。 dp[D][W][X]: 残りD日で、残りの体力がW、残り連続ライブ回数がXのときの最大利益 という表を埋めれば解けます。 dp[D][W][X]の値は以下のどれかのmaxになります。 D日目にはライブを行わない場合 dp[D+1][W][X] 場…

問題リンク Spellcasters 解法 魔力iを持つ人物が何人いるかカウントし、Sを超えるような魔力の組み合わせを考えます。 S となります。 ソース

問題リンク K Cards 解法 全探索で調べれば解けます。一応、[x, x+k)の区間の両端のうち小さい方を、区間以外の中の最大値と置き換えればこの区間における最大の点数が求まりますが、全探索のほうが簡単にかけると思います。 ソース