問題原文 atcoder.jp 問題要旨 頂点からなる木の各頂点を、距離が２以下の頂点の色が異なるように 色の中から１色を選んで塗り分けるような方法は何通りあるか？ 解法 根つき木として、根から塗り分けていくことを考える。 図などを書けば、ある頂点とその直…

問題原文 atcoder.jp 問題要旨 頂点 辺 の有向グラフが与えられる。このグラフ上での移動は、「ケンケンパ」によって行う。 具体的には、隣接する頂点への移動は常に３回連続で行う。この条件の元、 頂点 から 頂点 にたどり着くまでの最小のケンケンパの回…

問題原文 atcoder.jp 問題要旨 枚のカードが裏向きに置かれている。各カードには 1 または 2 が書かれている。 また「 番目のカードと 番目のカードに を加えた値は偶数」という情報が 個与えられる。 最低何枚のカードをめくれば、全てのカードについて書か…

問題原文 atcoder.jp 問題要旨 個の宝箱があり、 宝箱 を開けるためには、鍵 が必要になる。 また、 個の鍵セットが売られており、 番目の鍵セットは 円で、 個の鍵のセット を販売している。 鍵が何度でも再利用できるとき、全ての宝箱を開けるのに必要な最…

問題原文 atcoder.jp 問題要旨 人のメンバーと、 種類の食べ物がある。 番目のメンバーの消化コストは で、 食べ物 の食べにくさは である。 一人のメンバーに対して、一つの食べ物を割り当てる。 この時、そのメンバーが食べ物を完食するのには、 (そのメン…

問題原文 atcoder.jp 問題要旨 長さ の、 0と1からなる相異なる数列 , を考える。また、長さ の数列 が与えられる。 に対して以下の操作を繰り返し行い、 にすることを考える。 のある項を0なら1に、1なら0に変える。この時コストとして、 （その時点で とな…

問題原文 atcoder.jp 問題要旨 底面が一辺 の正方形であり、高さが であるような直方体に、 の水が入っている。 この直方体を底面の一辺を軸として傾けたとき、水が溢れ出す時の角度を求めよ。 解法 解説放送を丸パクリします（） 立体の問題 → 平面の問題に…

問題原文 atcoder.jp 問題要旨 となるような , を選び、 を最小化せよ。 解法 は、 としてよい。 つまり、どっちかが 2019の倍数なら答えは0になる。 また、 なら、 から までの間に2019の倍数が存在することになり、答えは0。 そうでない場合には、とりうる…

問題原文 atcoder.jp 問題要旨 体のモンスターが一列に並んでいる。左から 番目のモンスターは座標 にいて、体力は である。 以下の操作をモンスターが全滅するまで繰り返す。 座標 で爆弾を使う。すると、 以上 以下の範囲のモンスターに、 のダメージが入…

問題原文 atcoder.jp 問題要旨 体力が のモンスターがいる。 種類の魔法が使えて、魔法 は、モンスターの体力を 減らすことができるが、 魔力を 消費する。 同じ魔法を何度でも使える時、モンスターの体力を0以下にするためには、最小でどのぐらいの魔力がい…

問題原文 atcoder.jp 問題要旨 体力が のモンスターがいる。モンスターが全滅するまで、以下の操作を繰り返す。 モンスター一体を倒す。このとき、倒したモンスターの体力が１より大きければ、その半分の体力を持つモンスターが２体増える。（小数点以下切り…

問題原文 atcoder.jp 問題要旨 互いに区別できる 本の棒がある。 番目の棒の長さは、 である。 これらの棒から３本の棒を使って、三角形を作る時、作れる三角形は何種類あるか。 ただし２つの三角形は、ある棒が一方にのみ使われているときに異なるとする。 …

問題原文 atcoder.jp 問題要旨 , の公約数からなる集合であって、どの２数についても互いに素が成り立つようなものの最大の大きさを求めよ。 解法 ４とか選んじゃうと、結局素因数に２を持つような数がもう選べなくなってしまう。結局これは２を選ぶのと変わ…

問題原文 atcoder.jp 問題要旨 値段がそれぞれ 円であるような商品が 個あり、あなたは 枚の割引券を持っている。 ある商品に割引券を 枚使うと、その商品を （小数点以下切り捨て）円で買うことができる。 割引券を適切に使った場合、全ての商品を買うのに…

問題原文 atcoder.jp 問題要旨 一列に 人の人が並んでおり、各人は右か左を向いている。どの人も、目の前の人と同じ方向を向いていれば幸福を感じる。 以下の操作を 回以上 回以下繰り返して、幸福な人の数を最大化せよ。 ある範囲の人の列を180度回転させる…

問題原文 atcoder.jp 問題要旨 長さ の正整数列 が与えられる。 以下の条件を満たすような正整数列 を構築した時の、 の最小値を [tex: 109 + 7] で割ったあまりを求めよ。 任意の について、 が成り立つ。 解法 少し実験すると答えは、 になる。 あとは LCM…

問題原文 atcoder.jp 問題要旨 以下の正の整数の組 であって、 の末尾の桁が の先頭の桁に等しく、 の先頭の桁が の末尾に等しいようなものの個数を求めよ。 解法 とすると、 となる。(xは存在しないこともある) じゃあ を固定して、とりうる間のパターンを…

問題原文 atcoder.jp 問題要旨 を並べ替えた数列 が与えられる。 これらを適切に並び替えることで、 を最大化せよ。 解法 という感じに並び替えるのが最適。 実際の答えは等差数列の和の公式を使えばいい。 (証明的なの) 答えは、 の形をしてる。 各modの最…

問題原文 atcoder.jp 問題要旨 頂点１を根とする、 頂点の木が与えられる。各頂点にはカウンターが設置されており、最初その値は０である。 また以下のような操作が 回行われる。 頂点 を根とする部分木の頂点全てのカウンターの値を 増やす。 全ての操作終…

問題原文 atcoder.jp 問題要旨 の仕事があり、 仕事 は 日後に の報酬をもらえる。 １日にこなせる仕事は１件である。 日後に手にしている報酬の額を最大化せよ。 解法 ソートして貪欲したくなるが。。。？ ギリギリ報酬がもらえるような仕事をやる？ これは…

問題原文 atcoder.jp 問題要旨 数字と ? からなる文字列 が与えられる。 ? を好きな数字に置き換えてできる整数のうち、 13で割って5余る数はいくつあるか？ ただし、先頭の0は許可される。 解法 すごいDPっぽいのでDPを考える。 まず「何番目までみたか？」…

問題原文 atcoder.jp 問題概要 L と R からなる、横一列に並んだ 個のマス目がある。１マス目は R で マス目 はL である。 各マスには最初子供が１人ずついる。各子供たちは、以下のルールにしたがって、 回移動する。 自分がいまいるマスが R なら右、 L な…

問題原文 atcoder.jp 問題要旨 有限個の整数からなる集合 に対し、 とする。 個の整数 が与えられる。このうちから 個選び、それを とする。 全ての 個 の選び方について、 を計算し、その総和を で割ったあまりを求めよ。 解法 こういうのは、「各数が最大…

問題原文 atcoder.jp 問題要旨 . と # からなる迷路が与えられる。（# は通れない） スタートとゴールを好きに選ぶことで、移動距離を最大化せよ。ただし、スタートからゴールへは最短距離で移動する。 迷路は必ず . を２つ以上含む 任意の道のマスから任意…

問題原文 atcoder.jp 問題要旨 匹のスライムが一直線上に並んでいる。左から 番目のスライムは、座標 にいる。 ニワンゴ君は以下の操作を 回繰り返す。 番目（一番右）じゃないスライムの中からランダムに１匹選ぶ。 選ばれたスライムは、他のスライムにぶつ…

問題原文 atcoder.jp 問題要旨 長さ の 偶数 からなる正の整数列 と、 正の整数 が与えられる。 の全ての要素 に対して、以下の条件を満たす正の整数 を の「半公倍数」と呼ぶことにする。 を満たす 負でない整数 が存在する。 以上 以下の整数のうち、 の半…

問題原文 atcoder.jp 問題要旨 個の箱が横一列に並んでおり、それぞれの箱には か「tex: 1」 が書かれている。 それぞれの箱につい玉を１つ入れる or 入れないを適切に選ぶことで、 を満たす任意の整数 について、 の倍数が書かれた箱に入っているボールの個…

問題原文 atcoder.jp 問題要旨 円形に 個の山が、並んでいて、各山の間にはダムが１つずつある。 ある山に リットルの雨が降ると、その両隣のダムに リットルずつ雨が流れ込む。 ある日、各山に正の偶数リットル雨が降ったあとのダムに貯まった雨量が与えら…

問題原文 atcoder.jp 問題要旨 個の玉がある。そのうち 個が青い玉で、 個が青い玉である。 これら 個の玉を横一列に並べることを考える時、 を満たす全ての について、「青い玉が１個以上連続する区間がちょうど 個」であるような玉の並べ方の総数を求めよ…

問題原文 atcoder.jp 問題要旨 所要時間が 、 締め切りが であるような仕事が 個与えられる。 １度に１つしか仕事ができない時、順番を工夫することで全ての仕事を締め切りに間に合うように終わらせることは可能か？ 解法 よく見るスケジューリング問題。 締…