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

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

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

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

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

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

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

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

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

暗号とか勉強したことがあれば実家。 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 問題 Nを正の整数とする。表に1からNまでの整数が、裏に1からNまでの整数が書かれたカードがN枚テーブルの上に存在する。現在の配置について、表に書かれている数字は…