euler全埋め維持、AtCoderアルゴ赤維持で一応目標は達成 pic.twitter.com/MS4UAyfCeH— ひとあれ (@hitoare1) 2023年12月31日 現時点でProject Eulerの問題を全て解いているので、今回はdifficulty 100%の問題27個について解説をします。 ProjectEulerは101番…

Alien DPの自分なりの理解をメモ。 アルゴリズムの説明 を広義で上に凸であることがわかっている未知の数列とする。 与えられたに対してを求めることを目指す。 とおくと、が広義で上に凸であることからは広義単調減少である。 この時関数を、 で定義すると…

数え上げはそこそこ得意だと思っていたのに、解けなくて解説を見たので。 問題リンク 問題概要 R×Cのマス目に好きな順番でコマを1マスに1つずつ置いていく。いくつかのマスには最初からコマが置かれている。 コマが置かれたマスが長方形をなす回数を最大化す…

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

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

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

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

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

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

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

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

問題リンク 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\…

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

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

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

問題リンク 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}\)の中央値として有り得る値はいくつあるか。 解法 まず\…

問題リンク 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 - Negative Traveling Salesman F - Usual Color Ball Problems F - Virus 2 F - Square Subsequence G - Increasing K Times…

未証明です。 問題リンク 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についても同…

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

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

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

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

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

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

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

問題リンク 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)\)の総和を求めよ。 解法 各組み合わせに対し…

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

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

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