問題リンク The Tower 解法 シミュレーション問題なので注意深く実装するだけです。が、問題文を読んだだけでは曖昧さが残るところがあるような気がするのでつらっと列挙したいと思います。プレイヤーの動作直後のゲームオーバー判定処理と、プレイヤーの動…

問題リンク School of Killifish 解法 平方分割で解きました。 注目しているバケットの最小値が暫定解を更新しないなら、そのバケットに対する処理をスキップするという枝刈りを入れたらかなり高速になりました。 ソース

問題リンク School Excursion 解法 最小費用流で解けます。 駅に同時に辿りつかないという制約は次の図のような感じにすれば実現できるかと（コスト/容量） 同じ時刻に到着する電車は同じ頂点に集まるようにして、そこから容量1の辺を伸ばせば、電車が1本し…

問題リンク Mysterious Onslaught 解法 結局、答えを調べたのですが思考の変遷を少し。 状態数は明らかに2^25個なので最初にBFSをかけられなくもないんじゃないかと思い付いたが、TLEが取れそうにない。ですが、最悪の場合でも9ステップしかかからないという…

問題リンク Winter Bells 解法 交差点iの子どもがサンタを見る確率は (iを通る最短経路の数)/(全最短経路の数) となります。 iを通る最短経路の数は (0からiへの最短経路数) * (n-1からiへの最短経路数) となります。 経路の数はDPで求まります。よって、2回…

問題リンク Building Houses 解法 全探索+枝刈りで解きました。 家をどの順番で置いていくかを全通り試します。k番目に置く家は、必ずk-1番目より右に置くようにします。このままだとO(N!)かかるのでTLEします。 枝刈りのヒューリスティックス値に使えそうな…

問題リンク Crop Circle 解法 各円それぞれについて、[0, 2π)の範囲のうち、他の円に隠されていない部分はどこかを管理します。隠されていない部分の円周の和が答えとなります。 言うは易し行うは難しでこれが思ったより面倒くさいです。 次の手順を踏みまし…

問題リンク Make KND So Fat 解法 DPです。 buy[甘味セット][使える金額] -> 体重への影響の最大値 という表を前処理で作ったのち、 dp[何日目][使える金額] -> 体重への影響の最大値 という表を埋めればOKです。 ソース

問題リンク KND is So Sexy 解法 ヘロンの公式を使います。三角形ADCとBECの辺の長さは、計算すると、AD=DC、BE=ECになるような二等辺三角形にすれば面積最大になることが分かります。 ソース

問題リンク Kuru-Kuru Robot 解法 線分アレンジメントを施したのちダイクストラして解きました。 線分アレンジメントの説明はスパゲッティさんにソースコードと共にあります。ここのソースをおおいに参考にして線分アレンジメントを書きました。オーバーラッ…

問題リンク Finding the Largest Carbon Compound Given Its Longest Chain 概要 炭素だけを結合した化合物の構造の中で、最大鎖長がNであるようなもののうち、炭素の数の最大を求めよ 1 解法 Nの偶奇で場合分けすると、炭素の最大数の増え方の規則が見えて…

問題リンク Dominating Set 概要 グラフG = (V, E)の支配集合Dとは、D ⊆ V で、V-Dの全ての頂点が、少なくとも1つのDと隣接しているようなもののことを言う。 与えられるグラフの支配集合のうち、最小の要素数を答えよ。 解法 この問題、おっそろしいことに…

問題リンク Chocolate with Heart Marks 解法 当初、全探索＋枝刈りで頑張っていたのですがどうしてもTLEが解けなくて諦めていました。 何かのきっかけで「最小シュタイナー木」というものの存在を知りました。シュタイナー木とはグラフGと、頂点の部分集合S…

問題リンク Everything Starts With Your Vote 解法 上位K人の中に入れるお気に入りのキャラ数について2分探索して解きます。 キャラは人気度でソートしておきます。 need(X): 上位K人の中にお気に入りのキャラをX人食い込ませるために必要な最低投票数 とい…

問題リンク No Story 解法 分からなかったので解説を見ました(解説の「遅い解法」の方法で攻めていました）。 Lを素因数分解して、 L = p0^e0 * p1^e1 ... とします。すると、a, bはこの指数を決めて得られる整数となります。 また、LCM(a, b)がLとなるには…

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

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

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

問題リンク 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)の区間の両端のうち小さい方を、区間以外の中の最大値と置き換えればこの区間における最大の点数が求まりますが、全探索のほうが簡単にかけると思います。 ソース

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

問題リンク Huge Family 解法 ある人物からは必ず2本辺が出ています。図に起こすと、グラフは閉路がいくつか散らばっているような図になります。人物AとBの間に家族割引があったならば、clanの中でも繋がっていなければならないので、この閉路の中に登場する…

問題リンク The House of Huge Family 解法 まず、入力の制約の「Yiは重複しない」に注目すると辺の数は高々N個だと分かります。さらに、負の重みを持つ辺は取り除いた方が絶対得なので無条件で取り除くことにします。 問題の条件を満たす家の構造を考えたと…