yukicoder

yukicoder No.956 Number of Unbalanced

https://yukicoder.me/problems/no/956 問題概要 N要素の正数列Aが与えられる。Aのすべての連続する部分列のうち、ある種類の要素が部分列の過半数を占めているものが何通りあるか求めよ。 N <= 105 解法 想定解はO(NlogN)だったが、O(N)で解いたので書き残…

yukicoder No.951 【本日限定】1枚頼むともう1枚無料!

https://yukicoder.me/problems/no/951 問題概要 N枚のピザがあり、ピザには値段Pi円と美味しさDiがそれぞれ設定されている。またピザを1枚買うたび、そのピザ以下の値段のピザを1枚無料で買うことができる。K円まで使えるとき、買ったピザの美味しさの総和…

yukicoder No.765 ukuku 2

https://yukicoder.me/problems/no/765 問題概要 文字列Sが与えられる。Sから任意の1文字を削除するとき、削除後の文字列において回文となる最長連続部分文字列の長さを求めよ。 |S| <= 2 * 105 解法 回文の中心となる場所を総当たりしていく。最終的な回文…

yukicoder No.776 A Simple RMQ Problem

https://yukicoder.me/problems/no/776 問題概要 N要素の数列Aに対して以下の2種類のクエリがQ個飛んでくるので順次処理せよ。 set(i, x): Ai の値を x に変更する。 max(l1, l2, r1, r2): l1 <= l <= l2, r1 <= r <= r2, l <= r を満たすすべての整数の組l,…

yukicoder No.719 Coprime

https://yukicoder.me/problems/no/719 問題概要 2〜Nの数の集合から、「どの相異なる2つの要素を取り出してもそれらは互いに素である」という条件を満たすように部分集合を作る。このような部分集合のうち、要素の合計が最大になるときの値を求めよ。 2 <= …

yukicoder No.95 Alice and Graph

https://yukicoder.me/problems/no/95 問題概要 N頂点M辺の無向グラフが与えられる。グラフの頂点には0~(N-1)の番号が付いている。はじめプレイヤーは頂点0にいて、一度の移動で一辺で繋がれた2頂点間を移動できる。また頂点nをはじめて訪れたとき(2n - 1)…

yukicoder No.529 帰省ラッシュ

https://yukicoder.me/problems/no/529 問題概要 N頂点M辺の単純無向連結グラフとQ個のクエリが与えられる。クエリには以下の2種類が存在する。クエリを順に実行した結果を出力せよ。 クエリ1. 頂点uに価値wの獲物が出現する クエリ2. 頂点sからtに、同じ辺…

yukicoder No.584 赤、緑、青の色塗り

https://yukicoder.me/problems/no/584 問題概要 1×Nのグリッドを以下のルールを守って赤、緑、青で彩色するとき、ありうる塗り方は何通りか。 R個のマスが赤、G個のマスが緑、B個のマスが青になるようにし、残りのマスは未彩色のまま残す 3マス以上連続して…

yukicoder No.96 圏外です。

https://yukicoder.me/problems/no/96 問題概要 N個の中継局が二次元平面上の相異なる整数座標上に存在する。中継局と中継局は距離10以下であれば通信でき、無線機と中継局、無線機と無線機は距離1以下であれば通信できる。加えて、同じ中継局と通信できるも…

yukicoder No.127 門松もどき

https://yukicoder.me/problems/no/127 問題概要 N要素の正整数列Aが与えられる。Aの部分列で門松もどきであるようなものの最大の長さを求めよ。ただし門松もどきとは 各要素の大きさが「左端→右端→左から2番目→右から2番目→...」で昇順になっているもの、ま…

yukicoder No.97 最大の値を求めるくえり

問題概要 xorshiftによって生成される要素数Nの擬似乱数列Aがある。Q個のクエリqiが与えられるので、それぞれにおいて {qi * a mod 100003 (a ∈ A)} の最大値を求めよ。 1 <= N, Q <= 100003 0 <= qi < 100003 解法 この問題の肝は、Aが乱数列であることから…

yukicoder No.614 壊れたキャンパス

問題概要 K階建ての棟がN個あり、棟a_iのある階と棟(a_i+1)のある階を結ぶ渡り廊下がM個ある。「コスト0で渡り廊下を渡る」「コスト1で同じ棟の1つ上または1つ下の階に移動する」の2種類の移動が行えるとき、棟1のS階から棟NのT階へ移動するために必要なコス…

yukicoder No.109 N! mod M

https://yukicoder.me/problems/no/109 問題概要 T個の数の組(N, M)が与えられるので、それぞれでN! mod Mを求めよ 1 <= T <= 100 1 <= M <= 109 max(0,M−105) <= N <= 109 解法 まず自明なケースとして、NがM以上の場合答えは0である(N!で掛ける数の中に必…

yukicoder No.387 ハンコ

https://yukicoder.me/problems/no/387 問題概要 Nマスが横に連なったハンコがあり、マスiには色Aiのインクがついている。(2N-1)マスの紙に対し、はじめこのハンコを左端が合うように置き、「ハンコを押すor押さない」→「ハンコを右に1マスずらす」という操…

yukicoder No.511 落ちゲー ~手作業のぬくもり~

https://yukicoder.me/problems/no/511 問題概要 無限行W列のグリッドで、2人ゲームが行われる。このゲームでは2人交互に長方形のブロックを上から落とし、ブロックの各列は一番下か他のブロックにつくまで落下を続ける。ブロックを落とすことである列の高さ…