問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替え が与えられる. 以下の操作を 回以下行って, にできるか? となる整数 を選び, を入れ替える. 可能ならばその一例をあげ, 不可能ならばその旨を報告せよ. 制約 この問題は以下の問題と同じである. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を 正確に 求めよ. 制約 解法 まず, は の下から 桁を取り除いた整数である. これらの和を求めたい. そこで, 筆算で求める方法を考えると, 以下のような方法が思い浮かぶ. で の上から 桁目の数字が表す整数…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たすような整数の組 の個数を求めよ. 制約 解法 であるから, に対して, とすると, 求めるべきは となる の個数になる. とおくと, となる組の個数を求めることになる. よって, 以下のようにして正解で…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 次を満たすような整数の組 の個数を求めよ. に対して, 制約 解法 なので, に対して, を満たすような を全探索できる. よって, 深さ優先探索や, 直積集合を生成することにより, 実際に計算して かどうかを判…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 文字列 の第 文字目から第 文字目までの部分を反転させた文字列を求めよ. 制約 は英小文字からなる文字列 解法 文字列 の第 文字目から 文字目を抜き出した文字列を , 文字列 を反転させた文字列を , 文字列…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 封筒に 円の切手が1枚貼られている. 円のサービスを利用するためには 円切手を何枚最低何枚貼る必要があるか? 制約 解法 のときは既に 円以上なので切手を貼る必要はない. のときは, 枚貼れば良い. なお, こ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 2つの整数列 が与えられる. 列 に対して, 以下の操作を任意回できる. 円払い, を選び, の値を 増やすか, 減らす. 円払い, を選び, を入れ替える. この操作によって, を に一致させるために, かかる合計費用…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 マスからなるチェス盤とルークがある. このルークは最初, マス にある. ちょうど 回移動の後, このルークが にあるような移動の方法の数を求めよ. ただし, 回の移動では必ず違うマスに移動しなければなら…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 縦 行, 横 列の マスからなるグリッドがある. 各マスは空きマスか, 壁である. 空きマス にいるとき, のうち, 空きマスが存在するならば, その空きマスから1つ選んで移動できる (場外禁止). 空きマス から移…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 とする. 頂点 頂点の単純無向グラフ は同型か? ただし, とする. 制約 グラフ は単純無向グラフ 解法 一般的に, グラフ が同型であるとは, 以下を満たす写像 が存在することである. :全単射 任意の に対して,…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さが等しい英小文字の列 が与えられる. に対して, 以下を1回行う. 非負整数 を決める. の各文字を 個後ろにずらす. 以上の操作で を に一致できるか? ただし, 以外の英小文字の1個後ろの文字は辞書式の順…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 文字列 は, 以上 以下の整数 を用いて, の形で表される. の積を求めよ. 制約 は問題文の条件を満たす. 解法 はそれぞれ の 文字目, 文字目を担っているので, それぞれの文字を見てそれに対応する整数を に代…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 個の変数 があり, 最初は全て である. ここで, 以下を計 回実行する. 以上 以下の整数 を等確率 (各回ごとで独立) で選び, に を加算する. この操作後の の期待値を求めよ. 制約 入力はすべて整数 解法 とな…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 長さが の2つの列 が与えられる. 以下を満たす整数の組 はいくつか? かつ 制約 入力はすべて整数 解法 まず, かつ という条件については順序だけを見ていることから, 座標圧縮を行うことで, としてもよい. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 ある国の通貨は 円通貨のみがある. この硬貨を使って, 円支払うとき, 支払う硬貨の枚数と, お釣りでもらう硬貨の枚数の和の最小値を求めよ. 制約 に対して, は の倍数 入力はすべて整数 解法 お釣りとしてあ…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 の並び替えで, 以下の 個の条件を全て満たすような並び替えは存在するか? と は隣接している. 制約 入力はすべて整数 解法 条件を満たすような並び替えが存在することと, 以下は同値である. 無向グラフ を …

問題 atcoder.jp 提出解答 解答1 (二分探索) atcoder.jp 解答2 (クエリ先読み) atcoder.jp 問題の概要 正の整数の列 が与えられる. それぞれに対して, 以下の問に答えよ. の要素のうち, 以上の要素はいくつか? 制約 入力はすべて整数 解法 解法1 (二分探索) …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 のうち, 最も多く現れる文字列は何か? ただし, この問題ではこのような文字列が一意に定まるような入力のみ与えられる. 制約 は英小文字からなる長さ 以上, 以下の文字列 は整数 最も多く現れる文字列は一意…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 水深 [m] 地点でかかる水圧は [MPa] であることが知られている*1. では, 水深 [m] 地点でかかる水圧は何 [MPa]か? 制約 は整数 解法 問題文から, [m] 地点でかかる水圧は [MPa] なので, を出力すれば良い. …

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 重複がない正の整数の列 があり, 以下のゲームを行う. ただし, 正の整数の列 に対して, で, の全ての要素における XOR とする. 先手から次の行動を交互に行う. から1要素取り除く. そのとき, ならば, その人…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 行 列マスからなるマスがある. この 個のマスそれぞれに対して, 色 のいずれかで彩色する. ただし, 上下左右に隣り合うマス同士は同じ色で塗ってはいけない. いくつかのマスで塗る色が決まっている時, 条件…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 に対して, 以下の条件を全て満たす正の整数 を1つ見つけよ. の十進表記を文字列とみなすと, 連続する部分文字列に が存在する. の十進表記を文字列とみなすと, 連続する部分文字列に が存在する. 制約 解法 …

初めに 2021/05/15 に開催された マイナビプログラミングコンテスト2021 (AtCoder Beginner Contest 201) において, Performance 2274 を獲得した結果, Rating が 2006 になり, 黄色になりました. 1. 自分なりの心得 心得 1: 集中できないことが確定している…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 グラフ の最大マッチングの大きさを とする. 木 に対し, を満たす頂点の数を求めよ. 制約 グラフは木 解法1: を求める. まず, を求めることにする. 木DP で求めることにする. を適当な頂点 を根とする根付き…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を求めよ. 制約 解法 この問題は, 以下の事実が本質的である. 証明 とする. このとき, ならば, である. よって, である. よって, の場合と, 商が の場合をまとめて計算することで, 計算量 で計算できる. た…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 2つの整数 に対して, で, 以上 以下の整数全体の集合とする. また, で 以下の正の整数の全体の集合とする. 以下を満たす のうち, 濃度の最小値を求めよ. 任意の に対して, である が存在する. 制約 解法 次…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 のマス目があり, 最初は全て白マスである. が固定されており, 以下の操作を行う. (操作1) を満たす全ての整数 に対して, マス を黒く塗る. (操作2) を満たす全ての整数 に対して, マス を黒く塗る. を満たす…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 を を 個結合させた文字列とする. は の連続する部分列か? 制約 は からなる長さ 以上 以下の文字列 解法 速度を気にしないのであるならば, 文字列 が文字列 の連続する部分列であるかどうかを判定する方法…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 回目に開催された AtCoder Grand Contest の略称を表示せよ. ただし, AtCoder Grand Contest 042 は社会的情勢 *1 により欠番になっている. 制約 解法 を 回目に開催されたAGC のナンバリングとする. このと…

問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 外周が 頂点からなる車輪グラフ がある. ただし, ユニバーサル頂点は頂点 , 外周はある頂点から反時計回りに頂点 と名付けられている. 各辺に以下のように重みが設定されている. 辺 の重みは である. 辺 の…