ABC042-C (300 points) 問題 以上の整数のうち, を含まない最小の整数を求める. 入力は全て整数 方針 素直にやると... 置換が必要な桁のうち, 最大のものを求める. その桁より上で置換可能（ に含まれない数で置換してより大きい数にすることが可能）な桁を…

ABC043-C (200 points) 問題 個の整数 に対して, を最小化する整数 を求める. 入力は全て整数 方針 目的関数 を微分すると となるので, は下に凸な関数であり, で最小値を取る. は整数なので, この近くの整数だけ調べれば良い. # input n = int(input()) A =…

ABC044-C (300 points) 問題 数字が書かれた 枚のカードの中から 枚以上選び, 選んだカードに書かれた整数の平均を にする選び方の総数を求める. 入力は全て整数 方針 与えられたカードから 枚以上選んで作ることのできる和を素直に全て求める. collections.…

ABC045-C (300 points) 問題 以上 以下の数字のみからなる文字列 が与えられ, この文字列の中に を挿入して数式を作り, 和を計算すること考える. ありうる全ての数式の値を計算し, その合計を求める. に含まれる文字は全て ~ の数字 方針 が の位になる場合…

ABC046-C (300 points) 問題 高橋くんと青木くんの二人が出ている選挙で, 二人の得票数の比が表示されている選挙速報を見ている. 回目に画面を見たときに表示されている比が であるとき, 回目に画面を見たときの投票数として考えられるものの最小値を求める.…

ABC047-C (300 points) 問題 黒と白の石からなる列を, オセロの要領で両端に石を追加していくことで全て同じ色にすることを考える. このとき必要な石の最小個数を求める. に含まれる文字は または である. 方針 黒石と白石の境目を考える. 石を追加で つ置く…

ABC048-C (300 points) 問題 それぞれ 個のキャンディが入った箱が 個並んでいる. 箱に入っているキャンディを食べて, どの隣り合う箱を見ても, それらの箱に入っているキャンディの個数の和が 以下になるようにするとき, 食べなければならない最小個数を求…

ABC106-D (400 points) 問題 東西に伸びる 本の線路沿いに西から順に の 個の都市が並んでいる. 本の列車がそれぞれ都市 と の区間を走っているとき, 個の区間 に完全に含まれる列車の本数をそれぞれ求める. 方針 以下の記事に完全にお世話になりました. htt…

ABC106-C (300 points) 問題 ~ の数字からなる文字列 が以下のように変化するとき, 兆日後の文字列の左から 番目の数を求める. 日たつと, 文字列 の は , は , , は に置き換わる. 兆日後の文字列の長さは 以上. 方針 兆日後には 以外の数字は 実質的に無限…

ABC050-C (300 points) 問題 以下の条件を満たす 人の並び方の総数を で割った余りを出力する. 人 の右側に並んでいる人数と左側に並んでいる人数の差の絶対値は . 方針 人 の左に並んでいる人数を とすると, 右に並んでいる人数は となり, 全員で 人である…

ABC104-C (300 points) 問題 点の問題がそれぞれ 問, 計 問の問題が与えられ, 総合スコアを以下のように計算するとき, 点以上の総合スコアを獲得するために解かなければならない最少の問題数を求める. 基本スコア：解いた問題すべての配点の合計. コンプリー…

ABC51-C (300 points) 問題 点 間を, 途中で同じ座標を複数回通らないように 往復するとき, 最短経路を求める. 入力は全て整数. 方針 往復目は素直に行けば良い. 往復目は, 上下左右に だけ余分に移動すればOK. # input sx, sy, tx, ty = map(int, input().s…

ABC052-C (300 points) 問題 整数 が与えられるとき, の正の約数の個数を で割った余りを求める. 方針 素直に の素因数分解をするには が大きすぎるので, の順に素因数を足し上げていくことで, の素因数分解をする. 整数 の素因数分解が であるとき, 約数の…

ABC54-C (300 points) 問題 与えられた 頂点 辺の単純無向グラフについて, 頂点 を始点として全ての頂点を 度だけ訪れるパスを数え上げる. 方針 DFSで列挙. # input N, M = map(int, input().split()) G = [list(map(int, input().split())) for _ in range(…

ABC053-C (300 points) 問題 サイコロの好きな面が上になるように置き, 以下の操作を必要な回数行うとき, 点以上得るために必要な最小の操作回数を求める. 操作：サイコロを手前、奥、左、右のどれかの方向に90°だけ回転させる。その後、上を向いている面に…

ABC103-C (300 points) 問題 個の正整数 が与えられるとき, 非負整数 に対して を以下のように定義する. このとき, の最大値を求める. 入力は全て整数. 方針 の第 項について考えると の最大値は . とすると, 各項が最大値を取るので, このとき も最大値. # …

ABC054-B (200 points) 問題 の行列 と の行列 が与えられたとき (), が に含まれるかどうかを判定する. 方針 総当たり. import numpy as np # input N, M = map(int, input().split()) A = [list(input()) for _ in range(N)] B = [list(input()) for _ in …

ABC055-C (300 points) 問題 個の 's' と 個の 'c' を組み合わせて 'scc' という文字列をいくつ作れるか求める. ただし 'c' を 個組み合わせて 個の 's' を作れるものとする. 入力は全て整数 方針 ：'s' は全て使用可能 + 残った 'c' で 'scc' を作る. ：使…

ABC056-C (300 points) 問題 時刻 に座標 からスタートして, 時刻 に 動くことができるとき, 座標 に到達できる最短時刻を求める. 入力は全て整数 方針 ぐらいまで実験してみる. までに到達できる座標は まで. までの座標であれば時刻 までに到達可能. よっ…

ABC057-C (300 points) 問題 つの整数 に対して, を「 進表記における, の桁数と の桁数のうち大きい方」と定義する. このとき, 整数 に対して, つの正の整数 が を満たすように動くとき, の最小値を求める. 入力は全て整数 方針 となるとき（ が平方数）が…

ABC058-C (300 points) 問題 個の文字列 に各アルファベットが共通していくつ含まれているか求める. 入力は全て整数 方針 愚直. # input n = int(input()) S = [input() for _ in range(n)] INF = float('inf') alphabets = [INF] * 26 for i in range(n): a…

ABC059-C (300 points) 問題 長さ の数列 に対して, どれか つの項の値を 増やす（減らす）という操作を行い, 以下の条件を満たす数列にするために必要な操作の最小回数を求める. すべての に対し, 第 項から第 項までの和 でない すべての に対し, 第 項ま…

SoundHound-D (400 points) 問題 すぬけ国には 個の都市 と, 都市間をつなぐ 本の電車がある. 番目の電車は都市 と を両方向に走っている. 番目の電車の運賃は 円 / スヌークである（円とスヌークはすぬけ国の通貨）. 両替所では 円を スヌークに両替可能だ…

SoundHound-C (300 points) 問題 数列 の美しさを以下で定義するとき, 各要素が 以上 以下の整数である長さ の数列（ 通り存在）の美しさの平均を求める. 数列 の美しさ 隣り合う 項の組であって, 差の絶対値が であるものの個数 入力は全て整数 方針 けんち…

ABC0102-C (300 points) 問題 長さ の整数列 があるとき, 以下を最小にするような整数 とそのときの最小値を求める. 入力は全て整数 方針 が, のときに最小値を取ることが示せれば, と置き換えて中央値を取ることで最小値を計算可能. 証明 は昇順にソートさ…

ABC060-C (300 points) 問題 スイッチを押すと 秒間お湯が出るシャワーがある. このシャワーの前を 人の人がスイッチを押して通り過ぎていく. 番目の人は 番目の人がスイッチを押してから 秒後にスイッチを押すとき, お湯がでる時間の総和を求める. 入力は全…

ABC061-C (300 points) 問題 空の配列に対して, 整数を挿入する操作を 回行う. ただし, 回目の操作では, 配列に整数 を 個挿入する. 回の挿入操作後の配列の中で, 番目に小さい数を求める. 例えば, 配列 のとき, 番目に小さい数は である. 入力は全て整数 方…

ABC063-C (400 points) 問題 縦 ブロック, 横 ブロックの板チョコをブロックに沿った長方形に三分割するとき, 最も大きいピースの面積 と最も小さいピースの面積 の差 の最小値を求める. 方針 ↓の4つの分割について考えれば十分. 四番目の分割方法について考…

ABC063-C (300 points) 問題 集合 の部分和のうち, の倍数でないものの最大値を求める. 入力は全て整数 方針 なので, が の倍数でなければ最大値. が の倍数である場合, 集合 の要素の中に の倍数でない数があれば, そのような数の中で最小のものを として, …

ABC064-C (300 points) 問題 人のAtCoder参加者（それぞれのレートは で与えられる）がいるとき, 色の種類数の最小値と最大値を求める. ただし, レート3200以上の人は好きな色を選べるものとする. 入力は全て整数 方針 レート3200未満の人は人権がないので, …