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

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

茶色diff

AtCoder ABC 167 D - Teleporter (茶色, 400 点)

回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…

AtCoder ABC 169 D - Div Game (茶色, 400 点)

久しぶりに素因数分解する問題が来た!!!!!!!!!!! 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…

AtCoder ABC 169 C - Multiplication 3 (茶色, 300 点)

誤差は怖い!!!!!!! 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…

AtCoder ABC 165 D - Floor Function (茶色, 400 点)

気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない... 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数 に対する - の値の最大値を求めよ。 制約 考えたこと 全探索すれば だけど、それでは間に合わない。さて、式の…

AtCoder ABC 144 D - Water Bottle (茶色, 400 点)

これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う!! 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…

AtCoder ABC 149 D - Prediction and Restriction (茶色, 400 点)

ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…

AtCoder ABC 162 D - RGB Triplets (茶色, 400 点)

落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…

AtCoder AGC 019 A - Ice Tea Store (茶色, 300 点)

丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…

AtCoder ABC 159 D - Banned K (茶色, 400 点)

差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…

AtCoder ABC 158 D - String Formation (茶色, 400 点)

先頭と末尾の両方から push できるデータ構造といえば、deque!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1: 文字列 を左右反転する type 2: 値 F と文字 c が与えられ、F = 1 のと…

AtCoder ABC 157 C - Guess The Number (300 点)

全探索した! 整数を string 型にするのに手こずってしまった。 問題へのリンク 問題概要 以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。 ちょうど 桁である 左から数えて 桁目は である。() 制約 考えたこと 存在しない場…

AtCoder ABC 154 D - Dice in Line (茶色, 400 点)

期待値の線形性!!! 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…

キーエンス プログラミング コンテスト 2020 C - Subarray Sum (茶色, 400 点)

結構ギャグ要素強めな問題だった 問題へのリンク 問題概要 3 つの整数 が与えられる。 長さ の整数列 であって、以下の条件を満たすものを構築せよ: を満たすような の組がちょうど 個ある 制約 考えたこと とりあえず一つ思うこととして、 は全部 1 以上な…

AtCoder ABC 150 C - Count Order (茶色, 300 点)

next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…

AtCoder ABC 146 C - Buy an Integer (茶色, 300 点)

二分探索の教育的問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ!!!という雰囲気があ…

AtCoder ABC 143 D - Triangles (茶色, 400 点)

教育的ないい問題!!!!! 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか? 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…

AtCoder ABC 064 C - Colorful Leaderboard (茶色, 300 点)

あるあるあるある。 問題へのリンク 問題概要 人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。 今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 人の中に存在す…

AtCoder ABC 133 C - Remainder Minimization 2019 (茶色, 300 点)

高校数学で 「 を整数として は 3 の倍数であることを示せ」 という問題はよくあったと思う。これは「連続する 3 整数には 3 の倍数が含まれる」というのが理由になっている。今回こんな感じのことを考える。 問題へのリンク 問題概要 2 つの整数 があたえら…

AtCoder AGC 015 A - A+...+B Problem (茶色, 200 点)

確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。 問題へのリンク 問題概要 個の整数であって、最小が 、最大が であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。 制約 考えたこと この手の問題で重要…

AtCoder ABC 131 D - Megalomania (茶色, 400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題!!! 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべて…

AtCoder ABC 131 C - Anti-Division (茶色, 300 点)

「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では (B 以下の整数のうちの〜を満たすものの個数) から (A-1 以下の整数のうちの〜を満たすものの個数) を引く とすると、すごくやりやすい!!!!! このテクニックは大昔の topcode…

AtCoder ABC 130 C - Rectangle Cutting (茶色, 300 点)

長方形を直線で真っ二つに割る方法について 直線が長方形の対角線の交点を通る 直線が長方形を二等分する というのは同値だという話。結構、中学受験の算数では定番の話だったりする。 問題へのリンク 問題概要 二次元平面上で を頂点とした長方形と、その内…

AtCoder ABC 129 C - Typical Stairs (茶色, 300 点)

いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …

AtCoder ABC 126 C - Dice and Coin (茶色, 300 点)

確率を確実に 問題へのリンク 問題概要 正の整数 が与えられる。 最初に の整数値をランダムに出力する。以降コインを振って 表が出たら整数値を 2 倍する ( 以上になったら「勝ち」でゲーム終了) 裏が出たら整数値を 0 にする (こうなった時点で「負け」で…

みんなのプロコン 2019 C - When I hit my pocket... (茶色, 400 点)

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…

diverta 2019 B - RGB Boxes (茶色, 200 点)

これと大体一緒かな。 むしろ合計枚数に関する制約がない分、やや難しくなっているかもしれない。 問題概要 を正の整数とする。 を満たすような 0 以上の整数 の組が何通りあるか求めよ。 制約 考えたこと 愚直に探索しようと思うと int res = 0; for (int r…

AtCoder ABC 123 C - Five Transportations (茶色, 300 点)

結構難しい... 問題へのリンク 問題概要 人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。…

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 番目に大きい値の総和で決まる。ペアリングのスコアを…