yukicoder

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 門松もどき

問題概要 N要素の正整数列Aが与えられる。Aの部分列で門松もどきであるようなものの最大の長さを求めよ。ただし門松もどきとは 各要素の大きさが「左端→右端→左から2番目→右から2番目→...」で昇順になっているもの、または「右端→左端→右から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人交互に長方形のブロックを上から落とし、ブロックの各列は一番下か他のブロックにつくまで落下を続ける。ブロックを落とすことである列の高さ…