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

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

しゃくとり法

AtCoder ABC 130 D - Enough Array (400 点)

超典型的なしゃくとり法そのものだった!!! 問題へのリンク 問題概要 個の整数 があたえられる。数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com この…

AtCoder AGC 033 D - Complexity (1000 点)

これを解けなかったのが強い敗北感。 DP 配列が巨大になりそうなときに、最適化する対象を入れ替えるテクは今までなんども見ているのにそれが思いつかない思考の硬さを思い知らされた。 問題へのリンク 問題概要 0 と 1 のみからなる行列の複雑度を すべて同…

AtCoder ABC 124 D - Handstand (400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

CS Academy FII Code #1 B - Sugarel and Substrings

しゃくとり法のいい感じの練習問題 問題へのリンク 問題概要 英小文字のみから成る文字列 が与えられる。 の連続する部分文字列のうち「同じアルファベットが2度以上使われることのない」ものが何個あるかを数えよ (空文字列は 1 個とみなす) 制約 考えたこ…

QUPC 2018 I - Buffalo

楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…

AOJ 0613 財宝 (JOI 2014 予選 F)

スライド最小値の練習 問題へのリンク 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテムを取ることはできず、2 人ともとらな…

AISing Programming Contest 2019 D - Nearest Card Game (500 点)

ができた。本番中に解き切りたかった 問題へのリンク 問題概要 個の整数 がある。整数 を 1 つ固定したとき、先手と後手は以下のようにしてゲームを進める: 先手は現在残っている整数のうち、最大のものを取って足す 後手は現在残っている整数のうち、 に最…

CODE FESTIVAL 2018 qual A E - オレンジとみかん (800 点)

解き切りたかった 問題へのリンク 問題概要 オレンジが 個、みかんが 個ある。これを 人で分け合う ( が の倍数であることは保証される)。 それぞれの人 について、オレンジとみかんそれぞれ 1 個あたりの満足度が で与えられる。 うまく分けて、各人の満足…

AtCoder ARC 100 D - Equal Cut (600 点)

かなり悩んだ 問題へのリンク 問題概要 (ARC 100 D / ABC 102 D) 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だ…

CS Academy 084 DIV1 B - Three Ones

treeone さん... 問題へのリンク 問題概要 0 と 1 からなる長さ N の文字列 S が与えられる。 どの連続する K 個の中にも 1 が 3 個以上含まれている という条件を満たすような最小の K を求めよ 制約 3 <= N <= 105 S の中に 1 は 3 個以上含まれる 解法 右…

AtCoder ABC 098 D - Xor Sum 2 (500 点)

こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…

CS Academy 082 DIV1 C - City Break

しゃくとり法とは違うけど、区間の左端と右端とのどちらかを伸ばしていく感じはしゃくとり法に近いかもなん CS Academy 082 DIV1 C - City Break 問題概要 円環状に 個の街がある。街 i と街 i+1 との間の距離が a[i] で与えられる (i = N のときは街 N と街…

2018 codeFlyer 予選 C 徒歩圏内 (400 点)

実装力って大事だなと。 Before: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2601840 After: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2603569 2018 codeFlyer 予選 C 徒歩圏内 問題概要 長さ の単調増加数列…