2023-02-07

虹ヶ咲聖地巡礼をした

こんにちは、腕プルプル足クタクタ喉カラカラ男です

A・ZU・NA LAGOON を満喫したあとで Codeforcesに出るためにライブ会場すぐそばのヴィラフォンテーヌを予約したら、結果は +1 で (宿代) = (レート1) になってしまったので、泊まったメリットを生かして聖地巡礼をしてきました

大量連投するのもアレかと思ったのでここに放出します

QU4RTZ聖地の公園行って、昼食はハンバーガー食べてその付近も少し見るぐらいにしておくか、と思っていたけどかなり楽しくて徒歩10分圏内なら追加でGOをして歩き回ってたらヘトヘトになってしまいました

2022-12-31

2022年まとめ

いつもの続き

rubikun.hatenablog.jp

レート

AtCoder 2697 → 2841 (+144) (highest 2841) (106位)(更新されたら100位？)

Codeforces 2740 → 2941 (+201) (highest 2941) (65位)

topcoder 2297 → 2899 (+602) (highest 2899)

codechef 2460 → 2839 (+379) (highest 2839)

DMOJ 0 → 2780 (+2780) (highest 2870)

toki 2328 → 2646 (+318) (highest 2646)

精進

AtCoder 3444 → 4334 (+890) (5位→3位)

RPS 790200 → 1050600 (+260400) (9位→7位)

Codeforces 1779 → 2468 (+689)

AOJ 696 → 762 (+66)

yukicoder 98 → 175 (+77)

Library Checker 4 → 14 (+10)

CodeChef ? → 150 (+150)

topcoder 110 → 175 (+65)

Sum 6130 → 8077 (+1947)

AOJ-ICPC 218550→257750 (+39200) (10位→5位)

Project Euler 0 → 350 (世界688位,日本40位)

2022-12-21

AGC級,ARC級で多く解かれている問題リスト

こんにちは、もうすぐクリスマスですがRPS盛れてますか？

僕は盛れてないことがわかりました、いかがでしたか？(終了)

僕(Rubikun)とのレート差がプラマイ200以内ぐらいである程度埋めてる人10人強の解いた問題リストを見て、僕がまだ解いていない問題のうち多く解かれていた問題をまとめました

埋める順番の参考にするも良し、これ解いてないんだwってバカにするも良しで自由に使ってください

それぞれAC数ごとにまとめています

解けたやつは(O)をつけることにした

AGC級

10 ↑

Placing Squares(O)

Permutation and Minimum(O)

Blackout(O) , Chords(O) , ABBreviate(O) , Shuffle and Swap(O)

Mr.Aoki Incubator(O) , Ball Eat Chameleons(O) , Balance Beam(O) , Tokaido(O)

Manhattan Max Matching(O) , Less than 3(O) , Range Argmax(O) , Reverse Grid(O)

Uninity(O) , Rearranging(O) , RNG and XOR(O) , Inversions(O) , Shopping(O) , Yet Another ABC String , 3 Letters(O) , AB=C Problem , Modern Painting(O)

Games on DAG(O) , Construction of a tree(O) , Simple Subsequence Problem(O) , Sightseeing Plan(O) , Walking on a Tree(O) , Two Histograms(O) , Grafting , Lamps and Buttons , ZigZag Break(O) , Distinct Elements on Subsegments(O) , Triangular Lamps Easy(O)

人増やして追加(4/19)

4以上

Kenus the Ancient Greek(O) , Gachapon(O) , Snuke the Phantom Thief(O) , Subset Sum Game(O) , Sum Avoidance(O)

Wide Swap(O) , 90 and 270 , Generalized Insertion Sort(O) , Reachable Cells(O) , Topology , Equal LIS(O) , (ox) (O), Same Descent Set , Summation By Construction(O)

Namori(O) , Shik and Copying String(O) , Black Radius , Tree MST(O) , Trinity(O) , Manju Game(O) , ABC String , Negative Cycle(O) , Pairing Points , Histogram Rooks(O) , Random Pawn , ABC Ultimatum

ARC級

10 ↑

Circular(O)

Revenge of BBuBBBlesort!(O)

HonestOrUnkind(O) , Colorful Sequences(O)

Collecting Balls(O) , Deterministic Placing(O) , Permutation Division(O) , Sliding Window Sort(O) , Jewels , Triangles(O) , Preserve Diameter(O)

Cyclic Medians(O) , Shift and Decrement(O) , Migration , Diverta City(O)

Contest with Drinks Hard(O) , ColoringBalls(O) , Die Siedler(O) , Growth Rate(O) , ModularPowerEquation!! , Domination(O) , Monochromization(O) , Keyence Repetition(O) , 1D Kingdom Builder(O)

人増やして追加(4/19)

最近のAC多め(3以上)のARC

ABS Permutation (Count ver.)(O) , Constant Sum Subsequence(O) , Flipping Coins , Rational Number System(O) , Non-Adjacent Matching(O) , Flip Cells(O) , Reverse and Inversion , Split and Square(O) , Tree Degree Subset Sum(O) , Delete 1, 4, 7, ...(O) , Overlaps , 998244353 → 1000000007

2022-12-18

Counting 1's (AOJ 2539)

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 18日目の記事です。

https://onlinejudge.u-aizu.ac.jp/challenges/search/titles/2539 (900点)

問題概要

$b_i(x)$ を $x$ を 2 進数表記したときに下から $i$ bit 目 (1-indexed) が立っているなら 1 を, そうでないなら 0 を返す関数とする。

A と B を $1 \le A \le B \le 1e18$ を満たす整数とし、 $k_i$ を $A \le x \le B$ かつ $b_i(x) = 1$ となる整数 $x$ の数とする。

$k_i$ が与えられるので、A と B を求めてください。

ただし、答えが複数あるなら Many を、1 つもないなら None を出力すること。

制約

マルチテストケース

テストケース数は 100000 個以下

$1 \le n \le 64$

入力では $k_1 , k_2 , ... , k_n$ のみ与えられる。

$i \le n$ のとき $0 \le k_i \le 2^{63} - 1$

$n \lt i$ のとき $k_i = 0$

解法

$k_1$ を見ることで、 $B-A$ の値は高々 3 通りに絞ることができる。

$B-A$ を固定したとき、 $(A+B) (B-A+1) / 2 = \sum 2^{i-1} k_i$ を利用すると、A, B が求められる。

あとは、それぞれ $k_i$ を実際に計算して確かめればよい。

実装例

あとがき

解説とか(公開)コードを読むと $\sum 2^{i-1} k_i$ を計算してる人が見当たらなくて桁ごとになんかやってたので別解チャンスと思って書きました、がどうせ $k_i$ を確かめると思うとそんなに楽になってないかも

2022-12-11

Animal Companion in Maze (AOJ 1374)

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 11日目の記事です。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1374 (900点)

問題概要(意訳)

$n$ 頂点 $m$ 辺のグラフが与えられる。

辺は無向と有向が混在していて、長さは全て $1$ である。

同じ辺を連続で通ってはいけないという制限のもと、最長 walk の長さを求めよ。

始点と終点は自由に選択して良い。

いくらでも長くできる場合は Infinite を出力。

制約

$2 \le n \le 100000$

$1 \le m \le 100000$

多重辺が存在することはあるが、自己ループは存在しない。

解法

無向辺だけみたときに無向閉路があれば Infinite

そうでなければ、無向辺部分は森である。

以後、無向辺だけみたときの連結成分をそれぞれ 1 つの頂点に潰した場合のグラフを考える。

有向辺が自己ループ or 有向閉路をもてば Infinite

そうでなければ答えは有限であり、DAG になっている。

あとは、トポロジカルソートしておいて、DAG 上での最長経路を求める dp をしながら、各頂点をみるタイミングで潰れた無向辺部分に再度注目して木の直径を求める全方位木 dp と同じようなことを行って更新すれば良い。

実装例

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7153864#1

あとがき

900点もなさそうだけど、初期重みがあるときの全方位木 dp のやり方や、どうやって最長経路 dp + 全方位木 dp で更新していくかで意外と苦戦した(潰す前のグラフでやるとトポソで変な頂点を先に見てしまうことがある)。

2022-12-04

Floating Islands (AOJ 2571)

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 4日目の記事です。

https://onlinejudge.u-aizu.ac.jp/challenges/search/titles/2571 (800点)

問題概要

$n$ 個の島があり、最初は全て孤立している。

島 $i$ と島 $j$ の間に橋をかけるコストが $|p_i - p_j|$ のとき、全体を連結にするためのコストの総和の最小値を求めよ。

ただし、島 $i$ にかかっている橋の本数は $d_i$ 以下という制限がある。

制約

$2 \le n \le 4000$

$1 \le p_i \le 10^9$

$1 \le d_i \le n$

解法

$p_i$ でソートしておく。

$\sum d_i \lt 2(n-1)$ ならば $-1$

もし全て $d_i \ge 2$ ならば $p_n - p_1$ が達成できる。

$d_i = 1$ となる島があった場合が厄介でそれを考える。

$d_i = 1$ となる $i$ を順に $a_1, \dots, a_x$ , $d_i \gt 1$ となる $i$ を順に $b_1, \dots, b_y$ とする。

連結にするためには, $a$ に含まれる島は $b$ に含まれる島とつなぐ必要があり, $y$ 個の連結成分が残る。

残った $y$ 個の連結成分は, $(b_1,b_2), (b_2,b_3), \dots , (b_{y-1},b_y)$ とつなぐのが最適である。

$a$ に含まれる島と $b$ に含まれる島の最適なつなぎ方は二部マッチングを考えると

流量 $1$ , コスト $0$ の $s \to a_i$ の辺
流量 $1$ , コスト $|p_{b_j} - p_{a_i}|$ の $a_i \to n + b_j$ の辺
流量 $d_{b_j} - 1$ , コスト $0$ の $n + b_j \to t$ の辺

を張った $2n + 2$ 頂点のグラフで $s \to t$ の流量 $x$ の最小費用流を求めれば計算できる。

が、ACLを使うと $O(n^3logn)$ でTLEしてしまう。

ここでコスト関数の構造を利用すると、

流量 $1$ , コスト $0$ の $s \to a_i$ の辺
流量 $d_{b_j} - 1$ , コスト $0$ の $b_j \to t$ の辺
流量 $\infty$ , コスト $p_{i+1} - p_i$ の $i \to i+1$ の辺
流量 $\infty$ , コスト $p_{i+1} - p_i$ の $i+1 \to i$ の辺

を張った $n + 2$ 頂点のグラフで $s \to t$ の流量 $x$ の最小費用流を求めることでも計算できるため、ACLを使うと $O(n^2logn)$ に改善することができ、ACすることができる。

実装例

が、7.47s (TL 8s) なので何かがおかしく、実際にこれよりオーダーがいい解法が存在しました。( 公式解説 )

$i \lt j , k \gt l$ となるような $i,j,k,l$ について島 $a_i$ と島 $b_k$ , 島 $a_j$ と島 $b_l$ がつながる場合が最適になることはない(交差することはない)ため、島 $b_j$ を $d_{b_j} - 1$ 個に倍化することで適当に $O(n^3)$ dp ができます。