関係ないところを高速化しようとしてハマった。 りんごだいぼうけん 問題 H * W のグリッド上にリンゴが M 個、スタートとゴールがそれぞれ 1 個、壁が何個かある。リンゴを K 個以上回収してスタートからゴールまで最短距離で行け。 解法 M 個のリンゴ間、…

ちょっとハマったのでメモ。 カードはおやつに入りますか？(Are Cards Snacks?) 問題 N 枚のカードがあり、i 枚目には整数 A[i] が書かれている。square1001 君はカードのうち何枚かを選んで合計 K にしたいので、最小の枚数のカードを除去して邪魔せよ。 解…

いい加減マトロイドの基本をスラスラと思い出せるようにならないと非常にまずいと感じた。 E - Card Collector 問題 H 行 W 列のマス目の上に N 枚のカードが置かれている。i番目のカードは R[i] 行 C[i] 列に置かれており、整数 A[i] が書かれている。(同じ…

AtCoderで赤タッチしたのももう1.5年も前ですが書きます。覚えていないこと・抜け・漏れなどのオンパレードですがご容赦ください。 お前は誰 kobae964 - AtCoderです。2017年11月に初めてAtCoderでredになりました。RedCoderになりました！！！！ pic.twitte…

階乗 mod 素数 - memo のO(p^{1/2} log p)解法の、Rustでの実装を与えた。説明は元記事の方で十分にされているので、この記事での説明は期待しないでほしい。また、実装にはところどころ雑な部分があるので、今後refineするかもしれない。 問題 n! mod pを計…

5時間45分かけてようやく解けた。本番で解きたかった。 F - Edge Ordering 問題 N頂点M辺の無向グラフがあり、辺には0からM-1までの番号が付いている。0番からN-2番までの辺は全域木をなすことが保証されている。 これらに1からMまでの整数の重みを付けた重…

本番Eまで解いてF, G, Hのどれを解くか、という状態になったときに一番可能性の高かったこの問題に粘着した。結局時間内には解けなかったが、悔しかったので全力で頑張ったら解けた。 https://codeforces.com/contest/1119/problem/H 問題 整数kが与えられる…

この手の実装が重い問題を解くのにかなりの困難を感じる。 https://codeforces.com/contest/1062/problem/F 問題 サイクルのないn頂点m辺の有向グラフ(DAG)が与えられる。以下の条件を満たす頂点vを重要な頂点と呼ぶ: 任意の頂点wに対して、vからwへの道かw…

この手の問題は最近割と見る印象がある。 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]番目…

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

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

自分で考察したときは手掛かりが何もなかった。 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枚テーブルの上に存在する。現在の配置について、表に書かれている数字は…

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

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

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

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

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

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

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

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