けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder300点

AtCoder ABC 122 C - GeT AC (300 点)

これも累積和!!! ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com

AtCoder AGC 013 A - Sorted Arrays (300 点)

個人的には超苦手系。。。 でもちゃんと Greedy 思考を整理すればできる。こういうのは Greedy 思考の「型」を理解することが大事そう。 問題へのリンク 問題概要 長さ の数列 が与えられる。 を何箇所かで切って、 の連続した部分であるようないくつかの数…

AtCoder AGC 012 A - AtCoder Group Contest (300 点)

これほとんど drken1215.hatenablog.com と同じ問題!!! 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…

AtCoder AGC 011 A - Airport Bus (300 点)

頭の整理がちょっと大変な問題 問題へのリンク 問題概要 人が次々とバス停に到着する ( 人の到着時刻が で与えられる)。以下の条件を満たすように乗客たちをバスに乗せていきたい。 どの乗客もバス停に到着してから 分以内に出発させる 1 台のバスには 人ま…

AtCoder ARC 085 C - HSI (300 点)

期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…

AtCoder AGC 010 A - Addition (300 点)

メッチャシンプルで大好きなパリティ問題!!! ABS 記事の最終問題の類題にも挙げてる!!! 問題へのリンク 問題概要 黒板に 個の整数 が書かれています。これらの数に対して、高橋君は以下の操作を繰り返します。 偶奇が等しい 2 つの数 を一組選び、それ…

AtCoder AGC 009 A - Multiple Array (300 点)

教育的 Greedy 問題! 問題へのリンク 問題概要 個の整数からなる数列 と数列 がある。以下の操作を好きな回数だけ行える: 以下の整数 を 1 つ選び、 の値を ずつ増やす すべての に対して が の倍数となるようにしたい。これを実現するための操作回数の最小…

AtCoder ABC 113 C - ID (300 点) (座標圧縮の教育的練習問題)

いわゆる「座標圧縮」を練習できる問題!!! 問題へのリンク 問題概要 組の 2 整数 が与えられる。 の値は のいずれかである。 各 に対して、 という値が、 の値が等しいようなものの中で何番目に小さい値なのかを求めよ。 (出力形式については特殊なので、…

AtCoder ABC 120 C - Unification (300 点)

久しぶりのカッコ列の整合判定問題!!! カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…

AtCoder ABC 116 C - Grand Garden (300 点)

整理するのがちょっと大変系。でもとても教育的だと思う! 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…

全国統一プログラミング王決定戦 エキシビジョン F - コラッツ問題 (300 点)

一発芸問題 問題へのリンク 問題概要 整数 に対し、 のとき それ以外で のとき それ以外で が偶数のとき それ以外で が奇数のとき で定義される。 整数 が与えられます。となるような 以下の正整数 をいずれか 1 つ出力してください。 ただし、 であることが…

AtCoder ABC 119 C - Synthetic Kadomatsu (300 点)

最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう!!!!! 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概…

全国統一プログラミング王決定戦 本選 C - Come Together (300 点)

こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…

AtCoder ABC 118 C - Monsters Battle Royale (300 点)

教育的!!! 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …

AtCoder ABC 117 C - Streamline (300 点)

ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…

AISing Programming Contest 2019 C - Alternating Path (300 点)

DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 H × W のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていく…

CADDi 2018 C - Product and GCD (300 点)

好き 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような 個の正の整数 の組合せをすべて考えたとき、 の最大公約数として考えられる最大値を求めよ。 考えたこと を素因数分解して、各素因子たちを に振り分けることを考える。 このとき、各…

AtCoder AGC 029 A - Irreversible operation (300 点)

一瞬罠があるのではと怖くなるやつ 問題へのリンク 問題概要 'W' と 'B' で構成された文字列が与えられる。 "BW" を "WB" に置き換える変換を好きな回数行える。最大回数を求めよ。 考えたこと 問題の操作はつまりは 'W' を左に動かす操作と読み替えられる。…

AtCoder ABC 112 C - Pyramid (300 点)

AtCoder ではとても珍しい、注意して考えることの多い、重めの全探索な問題 問題へのリンク 問題概要 ピラミッドの高さを当てたい。 ピラミッドには 中心座標 (Cx, Cy) と 高さ H が定まっており, 座標 (X, Y) の高度は max(H−|X−CX|−|Y−CY|, 0) である。 ま…

AtCoder AGC 028 A - Two Abbreviations (300 点)

そろそろまた競プロやっていくぞー!!! 問題へのリンク 問題概要 長さ n の文字列 S と長さ m の文字列 T が与えられる。以下の条件を満たす文字列 X があるかどうか判定し、あるならば X の長さ L として考えられる最小値を求めよ。 (以下において、n' = …

AtCoder ABC 110 C - String Transformation (300 点)

ごめんなさい!!!!! コンテスト中に僕が AC した解法は嘘解法でした (てんぷらさんたちに教えてもらいました)!!! 嘘解法 :https://beta.atcoder.jp/contests/abc110/submissions/3251109 S と T の各文字の個数をカウントして、それぞれ個数ベクトル…

AtCoder AGC 008 A - Simple Calculator (300 点)

もれなく正確に解くための考え方とかが問われる感じ。 問題へのリンク 問題概要 (AGC 008 A) 整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ: を 1 増やす を にする 解法 最適解は 最初に反転する (かしないか) 「1 増やす」を…

AtCoder ABC 109 C - Skip (300 点)

一瞬「訪れる順番によって状況が変わらないか...」と不安になるかもな問題だけど、よく考えたら訪れる順番を考える必要もないん。ソートしても OK だけどソートする必要もないのん (ソートして良さそうだったらとりあえずソートすること自体はとてもよさそう…

AtCoder ARC 101 C - Candles (300 点)

問題概要 (ARC 101 C) N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。 解法 …

AtCoder ABC 106 C - To Infinity (300 点)

十分多い回数重ねるとなにかが収束する系はよく見るん 問題へのリンク 問題概要 (ABC 106 C) 1 から 9 までの数字からなる文字列 S がある。以下の操作を 5000 兆回行う: 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666…

AtCoder ARC 102 C - Triangular Relationship (300 点)

editorial に載っている解法は整数論で でやっているし、僕も本番それでやったけど、この制約なら全探索でパッと書けるべきですね... 参考: ABC108/ARC102 C: 解説に書かれていませんが、制約が手加減されているので a か a % K の値を全探索できます、この…

AtCoder ABC 105 C - Base -2 Number (300 点)

難しいという噂を聞いてやってみたのん。な、なるほどなんな... 問題へのリンク 問題概要 (ABC 105 C) 整数 が与えられる。 を "-2 進法" 展開せよ。すなわち が成り立つような整数 と 0-1 整数 を求めよ。 制約 考えたこと 2 進法展開や 10 進法展開なら こ…

AtCoder ABC 104 C - All Green (300 点)

すごく教育的な「bit 全探索 + Greedy」なん!!! 問題へのリンク 問題概要 100 点問題, 200 点問題, 300 点問題, ..., 100× 点問題がそれぞれ 問ずつある。 今、精進して合計で 点以上獲得したい。ただし、100× 点問題を 問すべて解いた場合にはボーナスと…

SoundHound 2018 本戦 A - Feel the Beat (300 点)

区間の重なりを求める処理、結構久しぶりなん。 問題へのリンク 問題概要 2 で何回か割ると 140 以上 170 未満になる正の整数を「よい数」と呼ぶ。 C 以上 D 未満の整数のうち「よい数」は何個あるか求めよ。 制約 < 考えたこと まともにカウントすると間に…

AtCoder ABC 103 C - Modulo Summation (300 点)

が互いに素でない場合とか一瞬だけ怖くなるけど、信じて提出する!!!!!!! 問題へのリンク 問題概要 (ABC 103 C) 個の整数 が与えられる。 様々な非負整数 に対して を で割ったあまり を で割ったあまり を で割ったあまり の総和を考えたとき、その最…