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

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

グルーピング(算数)

AtCoder ARC 109 D - く (黄色, 600 点)

僕はめっちゃめんどい言い換えをして、めっちゃめんどい場合分けして無理矢理通した... 問題へのリンク 問題概要 二次元平面上の点 (0,0),(1,0),(0,1) に石がひとつずつ置かれています。 3 つの石が次の条件を満たしているとき、くの字に並んでいるといいま…

Codeforces Global Round 12 F. The Struggling Contestant (R2400)

こういう個数合わせ系の問題は実は得意かもしれない 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して の順列 であって、 のどの隣接する二項も同じ数値でないようなものを考える。 そのような順列 のうち、 を満たさない の個数の最小値を…

AtCoder ARC 110 B - Many 110 (茶色, 400 点)

本番 14 分かけたのは反省。 問題へのリンク 問題概要 "110" という文字列を 10000000000 個連結してできる文字列を とする。 長さ の文字列 が与えられる。 の中に が連続する部分文字列としていくつ含まれるかを求めよ。 制約 考えたこと こういう、端の処…

AtCoder AGC 039 A - Connection and Disconnection (茶色, 300 点)

区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…

AtCoder AGC 034 A - Kenken Race (茶色, 400 点)

場合分けやコーナーケース回避がエグい問題! 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …

CPSCO2019 Session4 E - ox Concatenation (600 点設定)

これすごく好き!!!普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…

Codeforces Round #598 (Div. 3) E. Yet Another Division Into Teams (R2200)

DP 復元非本質>< 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…

AtCoder AGC 003 B - Simplified mahjong (水色, 400 点)

微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか? ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…

Codeforces Round #609 (Div. 1) B. Domino for Young (R2000)

半分エスパー 問題へのリンク 問題概要 列目の高さが であるようなヤング図形が与えられる。 これを 1 × 2 のドミノを重ならないように敷き詰めたい。最大で何個置けるか? 制約 考えたこと ドミノ敷き詰め系の問題は、市松模様に塗るのが基本ではある。そし…

Educational Codeforces Round 73 C. Perfect Team (R1200)

ペアリング系の問題 問題へのリンク 問題概要 以下の問題が 問出題されるのでそれぞれ答えよ: コーダーが 人、数学に強い人が 人、なんでもない人が 人いる ここからコーダー 1 人以上、数学強い人が 1 人以上を含む 3 人チームを最大何組できるか求めよ 考…

Codeforces Round #584 (Div. 1 + Div. 2) D. Cow and Snacks (R1700)

面白かった! 問題へのリンク 問題概要 組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。 「これまでに登場した整数」を表す集合を とする 各 i について、 がとも…

AtCoder AGC 008 C - Tetromino Tiling (青色, 600 点)

ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…

AtCoder AGC 012 A - AtCoder Group Contest (茶色, 300 点)

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

AOJ 3052 Milk (RUPC 2019 day2-B)

難しかった 問題へのリンク 問題概要 ちょうど 本の牛乳の空き瓶を持っていくと新たに 本の牛乳の入った瓶と交換できる。 最初に 本の牛乳の入った瓶を持っているとき、最大で何本分の牛乳を飲めるかを 1000000007 で割ったあまりを求めよ。 制約 < 考えたこ…

AtCoder AGC 030 A - Poisonous Cookies (灰色, 200 点)

慎重に 問題へのリンク 問題概要 解毒剤入りのまずいクッキー A 枚 解毒剤入りの美味しいクッキー B 枚 毒入りの美味しいクッキー C 枚 が与えられる。毒入りクッキーを 2 枚連続で食べることはできない。毒入りクッキーの後に一度解毒剤入りのクッキーを食…