E - デフレゲーム 問題概要 面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。 前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。 解法 期待値の線型性より （サイコロを 回振ったときの目の総和） （ 回目で初めて目が…

C - Cheating Nim 問題概要 2人でNimをする。 はじめに 個の山があり、 番目の山には石が 個ある。 ゲームが始まる前に、それぞれの山から石を0個または1個取り除く。 後手が必ず勝つために取り除く石の数の最小値を求めよ。 制約 解法 Nimで後手が勝つため…

A - Uncommon 問題概要 個の異なる整数 と整数 が与えられる。 以上 以下のそれぞれの整数 について、 のうち と互いに素であるものの個数を求めよ。 制約 解法 ある数 について、 のうち と互いに素であるものの個数を求めるとき、愚直に1つずつ試して でや…

C - Fountain Walk 問題概要 東西方向と南北方向にそれぞれ本の道路があり、となりあう道路間の距離は メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を 、東西方向の通りの番号…

問題概要 はじめジュースの在庫が 本ある。 毎日 本購入され、購入後 本以下になると夜に 本補充する。 永遠にジュースを 本購入され続けるか。 クエリは 個。 制約 解法 まず、 の場合は、初日に 本購入できないので、必ず No になる。 また、そうでなくて…

問題概要 個の箱が与えられる。 番目の箱は縦 cm × 横 cmで、縦と横を入れ替えることはできない。 ある箱は縦・横ともにより大きいサイズの箱にのみ入れることができ、ある箱は1つまでしか他の箱を入れることはできない。 このとき、箱を最大で何重の入れ子…

B - 異世界数式これ自力で思いつけたの嬉しい。 問題概要 数式 が、単なる数字の列か、もしくは演算子 （+, -, *, / のいずれか） の直後で括弧（(） を開き、その中に数式をいくつかカンマ （,） で区切って並べ、その後括弧 （)） を閉じるという形式で表…

A - YahooYahooYahoo 問題概要 文字列 が与えられるので、 'yahoo'の繰り返しの文字列にするための編集距離を求めよ。制約 解法 dp[ ][ ] := ] を「 'yahoo' の繰り返し + 'yahoo' の先頭 文字」の文字列にするための編集距離としてDPする。dp[0][0]は0、そ…

C - 広告 問題概要 縦 マス 横 マスのグリッドがあり、それぞれのマスには ' * ' か ' . ' が書かれている。 ' . ' のマスに、それぞれがとなり合わないように広告を打つとき、打てる広告の最大数を求めよ。制約 解法 ' . ' のマスを頂点とし、となり合う ' …

D - すぬけ君の塗り絵 / Snuke's Coloring 問題概要 縦 マス 横 マスの盤があり、すべて白く塗られている。 この状態から マスを黒く塗りつぶした。 番目の黒いマスは上から 行目で左から 列目のマスである。を満たす全ての について、盤の中に完全に含まれ…

D - いろはちゃんとマス目 / Iroha and a Grid 問題概要 縦 マス 横 マスのグリッドの左上のマスから、右と下の移動を繰り返し右下のマスに移動する。 下から マス以内かつ左から マス以内のマスには移動できない。 移動する方法が何通りかを で割った余りを…

D - Score Attack 問題概要 頂点 辺の有向グラフが与えられ、 番目の辺は 頂点 から頂点 をコスト でつないでいる。 頂点1から頂点 に行くときの合計コストの最大値を求めよ。なお、合計コストをいくらでも大きくできるときはinfを出力せよ。制約 解法 コス…

D - 大ジャンプ 問題概要 スタート地点の座標は で、ゴール地点の座標は とする。 1回のジャンプで、それぞれ の確率で以下の4つのうちどれかを行う。 軸方向に だけ移動する 軸方向に だけ移動する 軸方向に だけ移動する 軸方向に だけ移動する ちょうど …

D - 経路 問題概要 縦 横 のマス目があり、それぞれのマスには整数 が書かれている。 このグリッドの中の好きなマスから開始し、今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができる（移動しなく…

B - Inscribed Bicycle幾何。 問題概要 三角形の頂点が与えられる。 三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。制約 解法 まず、三角形の内部に半径 の円がかけるとはどういうことかを考えてみる。 円の中心と…

D - 塗り絵はじめての木DPです。 問題概要 頂点の木が与えられる。 両端の頂点が黒で塗られるような辺がないように、頂点を白または黒でぬるとき、塗り方の通り数を で割ったあまりを答えよ。制約 解法 漸化式を立てて木の上でDPをしましょう。 := 頂点 を親…

A - 不完全迷路 問題概要 高さ 幅 の迷路が与えられる。 壁のマスを1マスのみ道のマスに変えたとき、スタートのマスからゴールのマスへの最短経路長が最長となるようにしたい。 そのときのスタートからゴールまでの最短経路長を求めよ。制約 TLE解法 それぞ…

C - Time Gap 問題概要 人の都市について、高橋君の都市との時差が与えられる。 高橋君を含めた 人の都市のうち、すべての2つ都市の時差の最小値を としたときの、 の最大値を求めよ。制約 解法 num[ ] := 高橋君との時差が 時間の人数 とする。num[ ] とな…

D - すぬけそだて――トレーニング―― 問題概要 スタミナの上限が で、 スタミナを全て消費する時間の候補が 個ある。 時刻 のときにスタミナが で、 単位時間にスタミナが 回復するとき、 回スタミナを消費する場合の消費したスタミナの合計の最大値を各 につ…

D - 食塩水 問題概要 個の食塩水があり、 番目の食塩水は グラムで濃度が である。 この中から 個選んで混ぜるときの濃度の最大値を求めよ。 制約 解法 濃度が の食塩水を作れるかで二分探索していく。 それぞれの食塩水について、濃度を にするために必要な…

A - 1D Matching 問題概要 一次元の世界に 個のパソコンと 個の電源がある。 番目のパソコンの座標は であり、 番目の電源の座標は である。 それぞれの電源は一つのパソコンにのみつなぐことができるとき、ケーブルの長さの合計を最小化する場合の数を で割…

B - 大事な数なのでZ回書きまLた。 問題概要 2つの文字列が与えられる。同じアルファベットは同じ数字を表し、異なるアルファベットは異なる数字を表す場合と同じ数字を表す場合がある。2つの文字列が同じ 桁の数を表すとき、その数は何通りあるか。制約 解…

C - HSI 問題概要 プログラミングコンテストの 'YES' か 'NO' で答える問題でTLEした。 テストケースは ケースあり、そのうち ケースでTLEしていた。 そこで、 ケースではそれぞれ実行に ms かかって の確率で正解し， 残りの ケースではそれぞれ実行に ms …

D - FT Robot 問題概要 2次元平面の原点にロボットが置かれていて、はじめは 軸の正の方向を向いている。 'F', 'T' のみからなる文字列 が命令として与えられ、先頭から順に実行される。 'F' : 今向いている向きに1すすむ 'T' : 時計回りまたは反時計回りの…

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c 問題概要 以上 以下の整数を0個以上選ぶ。 選んだ整数のうちすべての整数が互いに素であるように選ぶとき、何通りの選び方があるか。制約 解法 より、それぞれの整数が35以下のど…

D - Built? 問題概要 個の街があり、 番目の街は座標 にある。 座標 にある街と座標 にある街の間に道をつくるのに、コストが 円かかる。 任意の2つの街の間を道を通って行き来できるようにするための最低コストを求めよ。制約 解法 3つの街が にあるとする…

B - Palindrome-phobia 問題概要 'a', 'b', 'c' の3種類の文字からなる文字列 が与えられる。 文字列 を自由に並び替えて、部分文字列に2文字以上の回文を含まないようにできるかどうか判定せよ。制約 解法 2文字以上の回文が含まれないとき、並べ替えた文字…

C - ロト2 問題概要 個の整数があり、 番目の整数は である。 が の倍数となるような と の組み合わせ が何通りあるか求めよ。制約 解法 積が の倍数になればいいのだから、 それぞれの において必要な情報は、 の約数のうちどれが含まれているか。 よって、…

B - Hamiltonish Path 問題概要 頂点 辺の、連結な単純無向グラフが与えられる。 頂点には から までの番号がついており、辺には から までの番号がついている。 辺 は、頂点 と頂点 を結んでいる。 次の条件を満たすパスを つ見つけて出力する（あり得る答…

D - Recording 問題概要 個のテレビ番組を録画したい。 テレビが受信できるチャンネルが 個あり、1から までの番号がついている。 録画したいテレビ番組のうち、 個目のテレビ番組は、時刻 から時刻 までチャンネル で放送される（時刻 を含み時刻 を含まな…