AtCoder300点
bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…
条件反射でいもす法をしたけれど、もっと楽にできた 問題へのリンク そして手前味噌ながら類題 atcoder.jp 問題概要 個の区間 があたえられる。 を満たしている。 この区間が 重に交わっている部分の長さを求めよ。 制約 解法 1：区間の交差 区間 と の交差…
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …
区間分割系問題 問題へのリンク 問題概要 文字列が与えられる。文字列を最小個数の連続区間に分割して、各区間の先頭文字がその区間内の他の任意の文字よりも辞書順で小さくなるようにせよ。 考えたこと Greedy に区間を分割していけば OK。 区間を分割して…
ちょっとした構築系問題という感じかな... 問題へのリンク 問題概要 二次元平面上の二点 が与えられる。 はすべて整数である。 今、 から出発して「上下左右に 1 秒に 1 だけ動く」という動作を繰り返しながら に行き、またそこから出発して に戻り、さらに…
確率を確実に 問題へのリンク 問題概要 正の整数 が与えられる。 最初に の整数値をランダムに出力する。以降コインを振って 表が出たら整数値を 2 倍する ( 以上になったら「勝ち」でゲーム終了) 裏が出たら整数値を 0 にする (こうなった時点で「負け」で…
さ、300 点！？ 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…
これでひとまず ABC 100 以降の CD 問題は全部書けた 問題へのリンク 問題概要 個のお店があって、各店 では 1 本 円のエナジードリンクを 本まで買うことができる。 全部で 本のドリンクを買いたい。最小で何円で実現できるか？ 制約 考えたこと 基本的に安…
300 点！？？？ 問題へのリンク 問題概要 '0' 〜 '9' および '?' からなる文字列 S が与えられる。 文字列のニコニコレベルとは、連続部分列であって "2525... 25" となっているものの最長の長さとして定義される。 S の '?' に '0' 〜 '9' を当てはめる方法…
また一つ、教育的 & 典型的な BFS 問が誕生した！！！ 問題へのリンク 問題概要 × のグリッドがあって、各マスは「白」「黒」に塗られている。 1 秒ごとに、各黒マスに対し、その上下左右に隣接したマスが存在するならば、そのマスを黒く上塗りしていく。全…
累積和！累積和！累積和！！！ でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…
これをもっと早く 問題へのリンク 問題概要 長さ の白黒列が与えられる。 最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。 制約 考えたこと つまりは「白白白白黒黒黒黒黒」のように 左 left 個が白 右 N …
今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…
一見複雑だけど、実質 2 通りしかないというやつ 問題へのリンク 問題概要 長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、 0 と 1 が交互に並んでいる状態 にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の…
結構難しい... 問題へのリンク 問題概要 人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。…
現代の AtCoder では少ない、再帰関数を用いると良い感じに書ける全探索問題。 すごく教育的な問題！！！！！ 問題へのリンク 問題概要 10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶこ…
これも累積和！！！ ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com
個人的には超苦手系。。。 でもちゃんと Greedy 思考を整理すればできる。こういうのは Greedy 思考の「型」を理解することが大事そう。 問題へのリンク 問題概要 長さ の数列 が与えられる。 を何箇所かで切って、 の連続した部分であるようないくつかの数…
これほとんど drken1215.hatenablog.com と同じ問題！！！ 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…
頭の整理がちょっと大変な問題 問題へのリンク 問題概要 人が次々とバス停に到着する ( 人の到着時刻が で与えられる)。以下の条件を満たすように乗客たちをバスに乗せていきたい。 どの乗客もバス停に到着してから 分以内に出発させる 1 台のバスには 人ま…
期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…
メッチャシンプルで大好きなパリティ問題！！！ ABS 記事の最終問題の類題にも挙げてる！！！ 問題へのリンク 問題概要 黒板に 個の整数 が書かれています。これらの数に対して、高橋君は以下の操作を繰り返します。 偶奇が等しい 2 つの数 を一組選び、それ…
教育的 Greedy 問題！ 問題へのリンク 問題概要 個の整数からなる数列 と数列 がある。以下の操作を好きな回数だけ行える: 以下の整数 を 1 つ選び、 の値を ずつ増やす すべての に対して が の倍数となるようにしたい。これを実現するための操作回数の最小…
いわゆる「座標圧縮」を練習できる問題！！！ 問題へのリンク 問題概要 組の 2 整数 が与えられる。 の値は のいずれかである。 各 に対して、 という値が、 の値が等しいようなものの中で何番目に小さい値なのかを求めよ。 (出力形式については特殊なので、…
久しぶりのカッコ列の整合判定問題！！！ カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…
整理するのがちょっと大変系。でもとても教育的だと思う！ 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…
一発芸問題 問題へのリンク 問題概要 整数 に対し、 のとき それ以外で のとき それ以外で が偶数のとき それ以外で が奇数のとき で定義される。 整数 が与えられます。となるような 以下の正整数 をいずれか 1 つ出力してください。 ただし、 であることが…
最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう！！！！！ 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概…
こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…
教育的！！！ 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …
