yukicoder No.803 Very Limited Xor Subset

この手の問題は最近割と見る印象がある。 No.803 Very Limited Xor Subset - yukicoder 問題 長さNの整数列Aがある。以下の条件を満たす部分列Sの個数をmod 10^9 + 7で求めよ: Sのxor和はX Sは以下のM個の条件(i = 1, ..., M)を満たす L[i]番目からR[i]番目…

yukicoder No.802 だいたい等差数列

こういうのはかなり得意だと思っている。 No.802 だいたい等差数列 - yukicoder 問題 以下の条件を満たす長さNの整数列Aの個数を数え、10^9+7で割った余りを求めよ。 1 i = 1, ..., N - 1に対して D1 制約 2 1 0 解法 まず愚直DPを考える。DP[i][j] := (Aの…

早稲田大学プログラミングコンテスト2019 D - Choose Your Characters

さすがにこれが解けないのは反省。 D - Choose Your Characters 問題 N種類のキャラクターがいるゲームで対戦を行う。N種類のキャラクターには1からNまでの番号がついている。またそれらの間には相性という概念が定まっており、「キャラクターaはキャラクタ…

Mujin Programming Challenge 2017 C - Robot and String (解説を見た)

自分で考察したときは手掛かりが何もなかった。 C - Robot and String 問題 英小文字からなる文字列Sが与えられる。以下の形のクエリにQ回答えよ。 Sの部分文字列S[L[i]...R[i] + 1] (半開区間、L[i]文字目からR[i]文字目までを抜き出した文字列)について、…

CODE FESTIVAL 2017 Elimination Tournament Round 2 A - Colorful MST

あさぷろで解いたときは解けなかった。面白い問題。 A - Colorful MST 問題 N頂点M辺のグラフがある。各頂点には色1から色Kまでのどれかの色が塗られているか、あるいはまだ色が塗られていない。 以下の操作を行ったときにできるグラフの最小全域木の重みの…

CODE FESTIVAL 2017 Exhibition A - Awkward

当時Code Festivalに参加していた時は、何をすればいいのか見当もつかず、出題陣のライブ解説も理解不能だったが、今解き直したらかなり簡単に思えた。A - Awkward 問題 N頂点の木が与えられる。木の頂点の並べ方はN!通りあるが、その中で以下を満たすものの…

CODE FESTIVAL 2018 Final I - Homework

F問題は解説を見ないとわからなかったがI問題は自力で解けた。 I - Homework 問題 荷物がN個ある。i番目の荷物はコスト2^A[i]、価値B[i]である。合計価値をK以上にするために必要なコストの合計を求めよ。制約 入力は全て整数 1 0 1 1 解法 二分探索をするこ…

全国統一プログラミング王決定戦本戦 F - Flights (他人の解法を見た)

20位以内に入りたければ、A問題からE問題は自明問題として高速に処理し、この問題かG問題のどちらかを解く必要があった。 F - Flights 問題 XY平面上にN個の点がある。i番目の点の座標は(X[i], Y[i])であり、どの2点の座標も異なる。この点たちの間に、以下…

全国統一プログラミング王決定戦本戦 D - Deforestation

本番は平面走査で通したけど、セグメント木で殴る解法にもちゃんと気付くべきだった。 D - Deforestation 問題 N本の竹がある。各竹の時刻0における高さは0で、毎秒1ずつ伸びる。 以下の行動をi = 1, ..., NのN回行うとき、総得点を求めよ。 時刻T[i]に、L[i…

NJPC2017 F - ダブルス (解説を見た)

何もわからなかったので解説を見た。 F - ダブルス 問題 無限に伸びる数直線上に2人の人間が立っている。2人の初期位置は0である。この2人は協力して以下の条件を満たしたい: 時刻0以降に散発的に光点が現れるので、2人のうちのどちらかがその光点を叩く。光…

「みんなのプロコン 2019」E - Odd Subrectangles

この問題まではムーブが完璧だった。 E - Odd Subrectangles 問題 N行M列の、要素が0と1からなる行列Aが与えられる。行と列の部分集合(U, V)の組は2^{N+M}通りありえるが、その中で以下を満たすものを数え上げよ。 Aを(U, V)に制限したときにできる行列に含…

「みんなのプロコン 2019」 D - Ears

E問題まではほぼ完璧に近いムーブができていたんだけどなあ。 D - Ears 問題 長さLの数列a[i]が与えられる。以下の規則で長さLの数列b[i]を作る時、\sum abs(a[i] - b[i])を最小化し、その最小値を求めよ。 b[i]の要素をすべて0で初期化する。0からLまでの番…

Codeforces Round #536 (Div. 2) F. Lunar New Year and a Recursive Sequence

暗号とか勉強したことがあれば実家。 https://codeforces.com/contest/1106/problem/F 問題 p = 998244353とする。正の整数列(f_i)_iが以下のように定められている: f_1 = ... = f_{k-1} = 1 f_k = x i > kのときf_i = (f_{i-1}^{b_1} f_{i-2}^{b_2} ... f_{…

CODE THANKS FESTIVAL 2018 G - Sum of Cards

普通に難しくて何時間もかかってしまった。 CODE THANKS FESTIVAL 2018 G - Sum of Cards 問題 Nを正の整数とする。表に1からNまでの整数が、裏に1からNまでの整数が書かれたカードがN枚テーブルの上に存在する。現在の配置について、表に書かれている数字は…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 E - Weights on Vertices and Edges

普通に難しかった。 E - Weights on Vertices and Edges 問題 N頂点M辺の無向グラフが与えられる。頂点と辺には重みがついている。 このグラフから辺を何本か取り去って、残っている辺がすべて以下の条件を満たすようにしたい: 辺の重みをYとすると、その辺…

ABC116 D - Various Sushi

こういう、適切な貪欲をやる問題が苦手すぎる…。 D - Various Sushi 問題 N個の寿司があり、i個目の寿司の種類はt_i、美味しさはd_iである。この中からK個選び、美味しさd_iの総和とt_iの種類数の2乗の和を最大化したい。最大値を求めよ。 解法 寿司を美味し…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 参加記

楽しいコンテストだった 来社 寝坊して9:24頃到着した(受付は9:00-9:50)。運良くコンセントのある席が残っていてよかった。 本戦問題コード部門 DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 - AtCoder A (00m00s-07m56s): 「300にし…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 D - DISCO!

まあ実家だよね。 D - DISCO! 問題 'D', 'I', 'S', 'C', 'O'のみからなる文字列Sが与えられる。このとき、以下のQ個の質問に答えよ: SのL_i文字目からR_i文字目までからなる部分文字列を考える。この文字列に部分列として含まれる"DISCO"は何通りあるか? つ…

ARC058 F - 文字列大好きいろはちゃん / Iroha Loves Strings (解説を見た)

実装が大変すぎる。 F - 文字列大好きいろはちゃん / Iroha Loves Strings 問題 文字列の列s_1, ..., s_Nが与えられる。これの部分列を順序を保ったまま連結して、長さKの文字列を作ることを考える。ありえる文字列の辞書順最小値を求めよ。 制約 1 1 1 \sum…

KEYENCE Programming Contest 2019 E - Connecting Cities

色々な解き方があって本当に面白い問題だと思う。 E - Connecting Cities 問題 整数N, Dと長さNの整数列A_iが与えられる。以下の完全グラフの最小全域木の重みを求めよ。 頂点数はN 頂点iと頂点jを結ぶコストはD|i - j| + A_i + A_j 解法 Code Festival 2017…

KEYENCE Programming Contest 2019 F - Paper Cutting

母関数おじさんにとっては多分実家。 F - Paper Cutting 問題 長方形の中に縦線がH個、横線がW個ある。これからK本の辺を選んで、順番にその線に従って長方形をカットする。 各カットについて、そのスコアはカット後の分割された長方形の個数である。P(H + W…

ARC072 F - Dam

1.7年前(2017/4/22)の本番では解法の見当もつかなかったが、改めて考えてみたら分かった。 F - Dam 問題 数Lと数列v_1, ..., v_N, t_1, ..., t_Nが与えられる。このとき、各1 許容量Lリットルのダムに水を流入させることを考える。1日目にt_1度の水v_1リット…

ARC086 F - Shift and Decrement

最初面倒 + 間違っている方針を考えていたが、某にもっと簡単な方法があると言われたので簡単な方法に気づくことができた。 F - Shift and Decrement 問題 N個の非負整数A_1, ..., A_Nが黒板に書かれている。以下の操作をK回まで行う。 以下の2個から一つ選…

ARC080 F - Prime Flip

最初見た時こんなの無理だろと思ったが、期間をおいて考え直したら分かった。 F - Prime Flip 問題 無限枚のカードがある。カードには1番から番号が振られている。最初x[1], ..., x[N]番目のカードは表向きで、それ以外は裏向きである。 以下の操作を何回か…

ARC093 F - Dark Horse

当時E問題と同じセットで出題され、全完が5人しかいなかった。強い人にとっては典型。 例: F 程よい典型詰め合わせだと思うんだけどなんでこんなに解かれてないんだろう— エレベーターに乗ったら行先階ボタンを押す (@DEGwer3456) 2018年3月25日 F - Dark Ho…

ARC093 E - Bichrome Spanning Tree

本番解けなかったけど、知識が増えた状態でやり直してみたら解けたのでよかった。 E - Bichrome Spanning Tree 問題 N頂点M辺の無向グラフがある。各辺を白か黒で塗るとき、以下の条件を満たすような辺の塗り方を求めよ。 白い辺と黒い辺を1個以上含む全域木…

ARC092 F - Two Faced Edges

この手の全体の中から一つ取り除くタイプの問題は、「sigmaさんが『yosupoがこういうの得意です』と言っていたタイプの問題」という印象が強い。 F - Two Faced Edges 問題 N頂点M辺の有向グラフがある。各辺について、その辺だけの向きを反転した時、グラフ…

2019年の目標

2019年の目標です。 競技プログラミング レーティングをAtCoder 2900以上、Codeforces 2500以上(、Topcoder 2200以上)にする 週に1回は、難しい問題を解説を見て通す 実装が難しい問題が望ましい 競プロ共通ライブラリプロジェクトを進める 開発 RustやErlan…

CODE FESTIVAL 2017 Final J - Tree MST (解説を見た)

本番見すらしなかった問題だけど、解説を見たりドワコン5th本戦C問題の準備をしたりして理解が深まったので解けた。 J - Tree MST 問題 辺に重みがついているN頂点の木、および長さNの数列Xが与えられる。このとき、以下の完全グラフの最小全域木の重みを求…

Codeforces Round #524 (Div. 2) F. Katya and Segments Sets

定数倍高速化がだるかった。 Problem - F - Codeforces 問題 k個の区間[l_i, r_i] (1 区間には色c_iがついている。色の種類はn種類である。このとき、以下のm個のクエリにオンラインで答えよ。 クエリ(a, b, x, y): a色からb色までの色すべてについて、区間[…