Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps

考察・実装合計で 2 時間かかった上に、無駄な実装をしてしまった。 Problem - D - Codeforces 問題 長さ n の数列 h が与えられる。1 番目の要素から n 番目の要素まで離散的ジャンプだけを使って移動したい。i 離散的であるとは、max(h[i+1], ..., h[j-1])…

yukicoder No.1031 いたずら好きなお姉ちゃん

解説より速い方法で AC できたので記念に。 No.1031 いたずら好きなお姉ちゃん - yukicoder 問題 長さ N の順列 p が与えられる。以下をちょうど1回実行して得られる順列として、あり得るものの個数を計算せよ: 1. non-empty な区間 [l, r] を選ぶ。 2. [l, …

yukicoder No.93 ペガサス

挿入 DP の問題を集中特訓していたのに、どうしても挿入 DP 解法が思いつかず別解で通してしまった。 No.93 ペガサス - yukicoder 問題 N 点の順列 p であって以下を満たすものの個数を mod (10^9 + 7) で求めよ: 1 制約 1 解法 包除原理を使う。 まず、ある…

AGC043 E - Topology

本番は ABD しか解けず無事死亡した模様。物理学科の人たちが E を通していて本気でびっくりした。 E - Topology 問題 整数 N と、それぞれの部分集合 に対して 0 または 1 の整数 a[S] が与えられる。 以下の条件を満たす xy 平面内の 閉曲線 C を構成せよ…

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution

かなり好きなタイプの問題。 C - Cookie Distribution 問題 N 人の人にクッキーを配りたい。i = 1, ..., K に対して、以下の操作を順番に行う。 N 人の中から a[i] 人を等確率にランダムに選び、その人たちにクッキーを 1 個ずつ渡す。 最終的に 人 i がもら…

yukicoder No.963 門松列列(2)

最近流行りの例のアレ。 No.963 門松列列(2) - yukicoder 問題 長さ N の交代順列の個数を、mod 1012924417 (= 483 * 2^21 + 1) で割ったあまりを求めよ。 交代順列: 1 から N の並び替えであって、任意の i (2 a[i + 1] が同値であるもの。 2 解法 N=i の…

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

典型のはずなのにかなりハマった。 No.951 【本日限定】1枚頼むともう1枚無料! - yukicoder 問題 N 種類のピザがあり、i 番目のピザのコストは P[i] 円、美味しさは D[i] である。各ピザはちょうど1枚だけ売られている。以下の行動を好きな回数繰り返すこ…

PAKEN Programming Camp 2019 Day 1 - Speedrun O: りんごだいぼうけん

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

PAKEN Programming Camp 2019 Day 1 - Speedrun M: カードはおやつに入りますか?(Are Cards Snacks?)

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

第一回日本最強プログラマー学生選手権-予選- E - Card Collector

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

AtCoderで赤になるまでにやったこと

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

階乗 mod pの高速な実装 (Rust)

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

diverta 2019 Programming Contest F - Edge Ordering

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

Codeforces Global Round 2 H. Triple

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

Codeforces Round #520 (Div. 2) F. Upgrading Cities

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

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とすると、その辺…