hitoare日記

たまに書きます

競技プログラミング

E - Shorten ABC(AtCoder Regular Contest 110)

解説とは若干違う解法。 問題リンク atcoder.jp 問題概要 A,B,Cからなる長さNの文字列が与えられる。 この文字列に、次の操作を0回以上繰り返して得られる文字列は何通りか。 連続する2文字で、文字が異なっているものを選び、そのどちらとも異なる文字1つに…

B - Bracket Score(AtCoder Grand Contest 048)

問題リンク 問題概要 '(', ')', '[', ']'からなる文字列で、括弧が正しく対応しているものを「良い括弧列」と呼ぶ。 偶数\(N\)と、長さ\(N\)の整数列\(A,B\)が与えられる。 長さ\(N\)の良い括弧列\(s\)に対し、\(i\)文字目が'('または')'ならば\(A_i\)点、'[…

F - Unbranched(AtCoder Beginner Contest 180)

問題リンク 問題概要 頂点にラベルが振られている\(N\)頂点\(M\)辺の無向グラフであって、以下の条件を満たすものはいくつあるか求めよ。 自己ループを持たない 全ての頂点の次数が2以下 連結成分のサイズの最大値が\(L\) 解法 2番目の条件より、各連結成分…

project euler550問解くまでにやったこと+おすすめ問題

Project Euler lv22(550問)達成 pic.twitter.com/M1nMuPSKlo — ひとあれ (@hitoare1) September 3, 2020 本来は500問の時に書こうと思っていた。 限界が見えてきて精神的に一区切りついたタイミングで書いています。 Project Eulerとは About - Project Eule…

E - Coprime(AtCoder Beginner Contest 177)

問題リンク atcoder.jp 問題概要 N個の自然数からなる集合\( \{A_i \}\)が与えられる。 この集合が「pairwise coprime」「setwise coprime」「そのどちらでもない」のどれかを判定せよ。 ただし、「pairwise coprime」とは、どの相異なる2要素もそのGCDが1で…

F - I hate Shortest Path Problem(AtCoder Beginner Contest 177)

問題リンク atcoder.jp 問題概要 \(H+1 \times W \)マスのグリッドがある。 グリッド上は右か下に移動できる。 ただし、上からk行目からk+1行目に移動する時、左から\(A_k\)マス目から\(B_k\)マス目の区間で下方向に移動するのは禁止されている。 一番上のW…

F - Range Set Query(AtCoder Beginner Contest 174)

問題リンク atcoder.jp 問題概要 \(N\)要素の数列\(c_1,...,c_N\)が与えられる。 以下の\(Q\)個のクエリを処理せよ。 クエリ\(i\):\(c_{l_i}\)から\(c_{r_i}\)までの要素の種類数を答える。 解法 要素数は\(r_i - l_i + 1\)なので、これから同じ要素が重複…

E - M's Solution(M-SOLUTIONS プロコンオープン 2020)

解説と異なる解法でした。 問題リンク atcoder.jp 問題概要 平面上にN個の集落があり、各集落iは座標\( (X_i,Y_i) \)にあって重み\(P_i\)が与えられている。 また、X軸とY軸には線路がある。 この時、X軸またはY軸に平行な線路をK本追加して、「重み×最も近…

E - Multiplication 4(AtCoder Beginner Contest 173)

問題リンク atcoder.jp 問題概要 \(N\)個の整数\(A_1,A_2,...,A_N\)が与えられる この中から、ちょうど\(K\)個の要素の積としてありうる値の最大値を求め、 10^9+7で割った余りを答えよ。 制約: \(1 \leq K \leq N \leq 2 \times 10^5\) \(|A_i| \leq 10^9\…

F - Intervals on Tree(AtCoder Beginner Contest 173)

問題リンク atcoder.jp 問題概要 \(N\)頂点の木が与えられる。各頂点には\(1,...,N\)の番号が振られている。 \(1 \leq L \leq R \leq N\)に対し \(f(L, R)\) を、「番号\(L\)以上\(R\)以下の頂点と、両端の番号が\(L\)以上\(R\)以下の頂点であるような辺から…

F - Strivore(AtCoder Beginner Contest 171)

問題リンク atcoder.jp 問題概要 英小文字からなる文字列\(S\)と自然数\(K\)が与えられる。 \(S\)に「好きな位置に好きな英小文字を1つ挿入する」という操作をちょうど\(K\)回繰り返して得られる文字列の総数は何通りか。 解法 \(S\)の文字数を\(N\)とおく。…

C - Shift(AtCoder Grand Contest 046)

問題リンク 問題概要 \(0\)と\(1\)からなる文字列\(S\)が与えられる。 「\(1 \leqq i < j \leqq|S|\)かつ\(S_i=0,S_j=1\)となる\(i\)と\(j\)の組を選び、\(S_j\)を削除して\(S_i\)の直前に挿入する」という操作を考える。 この操作を0回以上\(K\)回以下繰り…

E - Count Median(AtCoder Beginner Contest 169)

問題リンク atcoder.jp 問題概要 長さ\(N\)の整数列\(A_i\)と\(B_i\)が与えられていて、\(A_i \leqq B_i\)が成り立つ。 各iに対して\(A_i \leqq X_i \leqq B_i\)となる整数\(X_i\)をとった時、\({X_i}\)の中央値として有り得る値はいくつあるか。 解法 まず\…

F - Knapsack for All Subsets(AtCoder Beginner Contest 169)

問題リンク atcoder.jp 問題概要 省略 解法 Knapsack for All Segmentsの類題。 \(dp[i][j] =\) {\(A_1,...,A_i\)の各部分集合に対する、和がjとなる部分集合の数} と置いてDPする。 遷移は \(dp[i+1][j] = 2dp[i][j] + dp[i][j-A_{i+1}]\) となる。 右辺の…

解けなかった問題集

個人的に コンテスト中に解ききれなかった 解法が思い浮かばず解説ACした などの理由で特に悔いが残る問題をまとめておく。 ABC F - Zebraness E - NEQ E - ∙ (Bullet) E - Active Infants E - Payment F - Xor Sum 3 F - Permutation Oddness D - ロボット …

F - Three Variables Game(AtCoder Beginner Contest 166)

未証明です。 問題リンク atcoder.jp 問題概要 3つの非負整数A,B,CとN個の文字列(AB,AC,BCのいずれか)が与えられる。 \(1\leqq i \leqqN\)に対し、i番目の文字列がABならば「Aに1足しBから1引く」「Bに1足しAから1引く」のいずれかを選ぶ(AC,BCについても同…

E - This Message Will Self-Destruct in 5s (AtCoder Beginner Contest 166)

問題リンク atcoder.jp 問題概要 \(N\)要素の数列\(A_i\)が与えられる。 これらのうち2つを選んで得られる\(N(N-1)/2\)個のペアのうち、iとjの差の絶対値が\(A_i + A_j\)に等しいものはいくつあるか。 解法 \(|i-j|=A_i+A_j\)を変形すると \(i > j\)のとき\(…

D - I hate Factorization (AtCoder Beginner Contest 166)

本番中は勘で解いた。 問題リンク atcoder.jp 問題概要 1以上\(10^9\)以下の整数Xが与えられる。 整数A,Bの組で\(A^5-B^5=X\)を満たすものを1つ示せ。 ただし、答えとなる(A,B)が存在することは保証されている。 解法 \(A \neq B\)としてよい。 因数分解する…

F - LIS on Tree (AtCoder Beginner Contest 165)

問題リンク atcoder.jp 問題概要 N頂点の木グラフと、各頂点に対して整数\(a_i\)が与えられている。 \(1 \leqq k \leqq N\)の全ての整数に対して、次の問題を解け。 問題k: 頂点1から頂点kまでの最短経路上にある頂点の整数をこの順に並べた数列の、最長増加…

F - Select Half (AtCoder Beginner Contest 162)

想定と違う解法っぽい。 問題リンク atcoder.jp 問題概要 N要素の数列Aが与えられる。このうち互いに隣り合わないfloor(N/2)個の要素の和の最大値を求めよ。 解法 取る要素のうちほとんどは1つおきに並ぶことがわかる。 Nの偶奇によって場合分けをする。 あ…

E - Sum of gcd of Tuples (Hard) (AtCoder Beginner Contest 162)

問題リンク atcoder.jp 問題概要 正整数\(K,N\)が与えられる。 1以上\(K\)以下の自然数からなる数列\(A_1,...,A_N\)は\(K^N\)通りあるが、それらに対し \(gcd(A_1,...,A_N)\)の総和を求めよ。 解法 自分は約数包除を使った。 \(f(d)\)を1以上\(K\)以下の自然…

E - Yutori (AtCoder Beginner Contest 161)

問題リンク atcoder.jp 問題概要 連続するN日間のうち、次のルールでK日を選んで働くとする。 働いた日から次に働くまでC日以上空ける。 あらかじめ指定された働かない日は働かない。 働く日をどのように選んでも、必ず働くことになる日を全て求めよ。 なお…

F - Division or Substraction (AtCoder Beginner Contest 161)

問題リンク atcoder.jp 問題概要 正整数Nが与えられる、2以上N以下の整数Kを選んで次の操作を行う。 NがKで割り切れるならば、NをN/Kで置き換える。 割り切れなければ、NをN-Kで置き換える。 NがK未満になったら終了する。 最終的なNの値が1になるKはいくつ…

F - Knapsack for All Segments (AtCoder Beginner Contest 159)

問題リンク atcoder.jp 問題概要 長さNの数列\(A_1,,,A_N\)が与えられる。 \(1 \leqq L \leqq R \leqq N\)に対し、\(f(L,R)\)を\(A_L\)から\(A_R\)までの数を使って和をSにする組み合わせの総数とする。 \(f(L,R)\)の総和を求めよ。 解法 各組み合わせに対し…

E - Dividing Chocolate (AtCoder Beginner Contest 159)

問題リンク atcoder.jp 問題概要 縦H、横Wマスのチョコレートがあり、一部のマスはホワイトチョコレートである。 このチョコを縦または横に一直線に切ることを何回か繰り返して、各部分に含まれるチョコレートがK個以下になるようにしたい。 切る回数の最小…

F - Removing Robots (AtCoder Beginner Contest 158)

問題リンク atcoder.jp 問題概要 数直線上にN体のロボットがいる。i番目のロボットは座標\(X_i\)にいて、起動させると正の方向に\(D_i\)動いた後、取り除かれる。 動いている途中に他のロボットに接触すると、そのロボットも起動する。 いくつかのロボットを…

E - Divisible Substring (AtCoder Beginner Contest 158)

問題リンク atcoder.jp 問題概要 0~9からなる文字列Sと素数Pが与えられる。 Sの連続部分列で、10進数の数とみなした時にPの倍数となるものはいくつあるか。 解法 P=2とP=5は一番下の1桁を見て数えられるので除いておく。 Pが10と互いに素な場合を考える。考…

E - Roaming (AtCoder Beginner Contest 156)

問題リンク atcoder.jp 問題概要 n個の部屋に1人ずつ人がいる。 「ある部屋から1人、別の部屋に移動する」という操作がちょうどk回行われた後の人数の組み合わせとしてありえるのは何通りか。 解法 \(n\geqq3\)なので無駄打ちが可能。 たとえば部屋1→部屋2と…

F - Silver Fox vs Monster (AtCoder Beginner Contest 153)

問題リンク atcoder.jp 問題概要 数直線上に\(N\)体のモンスターがいる。それぞれのモンスターは座標\(X_i\)にいて、体力は\(H_i\)である。 次の操作を好きなだけおこなう。 好きな座標\(x\)を選び、爆弾を使用する。このとき座標が\(x-D\)以上\(x+D\)以下の…

E - Flatten (AtCoder Beginner Contest 152)

問題リンク atcoder.jp 問題概要 \(N\)個の正整数\(A_1,…A_N\)が与えられる。 正整数列\(B_1,…B_N\)であって、\(A_iB_i = A_jB_j\) が全ての\( (i,j)(1\leqq i < j\leqq N)\)にして成り立つ物のうち、\(B_1+B_2+ \ldots +B_N\)の最小値を\(10^9+7\)で割った…