ぷの日記

作問・解説・日記など

へやわり！(AOJ 2829) 解説

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

問題

https://onlinejudge.u-aizu.ac.jp/problems/2829

順を追って考察していけば解けるような数え上げの問題です

問題概要

整数 N と長さ N の配列 A が与えられます

次の条件を全て満たす配列の集合として考えられる最大の大きさを mod 1000000007 で答えなさい

集合に含まれる任意の配列は以下の条件を満たす

・長さが N+1 である

・配列を B とする時、B には 0 から N までの整数が 1 つずつ含まれる

・各 i (1 \leq i \leq N+1 , B_i \neq 0) について、 B_{i-1},B_{i+1} のいずれかは A_{B_i} に等しい

・B の 0 である要素と 0 でない要素のいずれかとを swap した時、新しくできる配列は集合に含まれない。(この操作を、以下 swap 操作と呼ぶ)

解法

各 i について i から A_i へ辺を貼ったグラフを考えると、(有向辺を無向辺と考えた時の)各連結成分は以下のようになっている必要がある

また、swap 操作において新しくできた配列が集合に含まれている時、新しくできた配列も条件を満たしているため、swap 操作において問題であるのはパターン 1 の場合のみであることがわかる

さて、ここで 1 つ大事になってくることが、この操作において連結成分のブロックの並びは変わらないということである

例えば、初め B = {{1,3,2},{0},{4,5},{6,7}} であった時、操作をしても B = {{1,3,2},{5,4},{0},{6,7}} のように、{{1,3,2},{4,5},{6,7}} の並びは変わらない

観察

上の 4 つの配列について、上下に隣接するもの同士が同じ集合に入っていてはならない → 2 つは同じ集合に入れることができる

この観察を元にすると、ある連結成分のブロックの並びにおいて、集合に含まれるその並びの配列の個数の最大値がわかる。

パターン 2 であるような連結成分の個数が 0 個であるような場合を除いておくと、0 を挿入できる場所は以下の 2 つの場合に分けることができる

1. [配列の端][パターン 1 が x 個][パターン2]

2. [パターン2][パターン 1 が x 個][パターン2]

いずれについても、0 は最大で floor(x/2)+1 個入れることができる。

よって、それぞれ x の値で主客転倒して答えを求めてやり、足し合わせれば良い。

具体的には、パターン1 の配列の数が a 個、パターン 2 の配列の数がb 個あり、パターン 1 の配列が x 個連続しているようなものについて

1. (floor(x/2)+1) \times binom(a,x) \times b \times 2 \times (a+b-x-1)! \times x! \times 2^{a+b}

2. (floor(x/2)+1) \times binom(a,x) \times binom(b,2) \times 2 \times (a+b-x-1) \times (a+b-x-2)! \times x! \times 2^{a+b}

を足してやれば良い

計算量は O(N) である

提出

onlinejudge.u-aizu.ac.jp

終わりに

こういう問題、好きです

アドカレ大幅に遅刻してすみません

でぶでぶ天使

でぶばんわ！バーチャル界の天使 ☆shojin_pro☆ わよ！😡😡😡😡😡😡😡😡

この記事は でぶ Advent Calender 2022 16 日目 の記事です。

今回は、shojin_pro に関係することを思いつくままに書いていこうと思います

1. お絵描きデ部

among us で SEEEEEEE! の代わりに出てきたでぶ

2.でぶなぞなぞ

Q. shojin_pro の高貴な部分な〜んだ？

A. しょうじんぷろの神父の部分(白文字)

3.美味しそうな問題がよく出るコンテストがあるらしい

JOI - chinese - 中華料理(難易度9)

おすすめ 青~

程よい難易度です。考えて損はないと思います。

JOI - F - 小籠包 (Xiao Long Bao) (難易度10)

おすすめ 黄~

自分が解いた時はなかなか考察に苦しみました。

面白かったです。実装力の練習にもなるかも。

JOI - apples - リンゴの出荷 (Apples)(難易度 11)

おすすめ 黄~

verify 問題に成り下げよう。知識として知っていてもいいかもしれません。

4.そもそも名前がもう美味しそうなコンテストサイトがあるらしい

www.codechef.com

いわゆるインドです。

インドと聞くと、よく問題がコピーされていたり、順位表がぶっ壊れているような印象を持っている方も知るかもしれません。

しかし、それは野良インド(非公式コンテスト)の話で、公式のコンテストはかなり質が高いです。最近 UI が変わって随分見やすくなったので、初めての人でもコンテストに参加するまではわかりやすいと思います。

時間帯が遅いことが多いのが難点ですが、ぜひ参加してみてはいかかでしょうか。

※注意点

- コンテストに Register の概念はない

時間になったら問題が表示されます。提出をした瞬間に Rated になります。

- コンテストのトップページの問題順が変わる

コンテスト中は、Solved の多い順に問題の順番が変わります。順位表に表示される問題の順番は変わりません。

- コンテストの点数のつき方がコンテストごとに違う

コンテストのトップページや順位表に点数のつき方が JOI - style , ICPC - style という風に書いてあります。詳しくはルールを読んでください。

- 傾向

今まで出てきた中だと、JOI - like な問題が多いように思います。

楽しいインドライフを！

5.世の中には美味しいものがあるらしい。

卵潰してしまった、また食べたい

終わりに

shojin_pro 愛してるぜ！

The J-th Number (AOJ 2563) 解説

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

問題概要

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2563

N 個の配列 t_1,t_2,\ldots,t_n があります。初め、全ての配列は空です。

この配列に対して次の M 個の操作を行いました。

・配列 t_k (a_i \leqq k \leqq b_i) に対し、整数 v を末尾に追加する。

以下の Q 個のクエリを処理してください。

・配列 t_k (x_i \leqq k \leqq y_i) に含まれる全ての要素を値が小さい順にソートした時、j_i 番目の要素を出力しなさい。

1 \leqq N \leqq 10^9

1 \leqq M,Q \leqq 10^5

1 \leqq a_i,b_i,x_i,y_i \leqq N

1 \leqq v_i \leqq 10^9

1 \leqq j_i \leqq \sum_{k = x_i}^{y_i} |t_k|

解法

クエリに対して、並列二分探索をします。

各クエリに対して、値 mid 以下の数が配列 t_{x_i} から t_{y_i} の中に幾つ含まれるか知りたいです。

初めの M 個の操作について追加する値、 Q 個のクエリについて mid で二つを合わせてソートすると、以下の問題に帰着されます。

数列 A に対して、以下の 2 種類のいずれかを行うクエリを処理する。

・ A_{a_i} から A_{b_i} に 1 を加算

・ A_{x_i} から A_{y_i} の値の総和を求める

これは遅延セグ木を用いると答えることができますが、今回は N が大きいため、普通にやると TLE/MLE します。

必要なところだけ作る遅延セグ木を用いると AC できます。

(実際には必要なところだけ作る遅延セグ木でも TLE したので、必要なところだけ作るStarrySkyTreeを用いました)

実装例

judge.u-aizu.ac.jp

終わりに

多分殴ってます。別解が存在したら追記するかもしれません。

追記 : これ座圧遅延セグ木で良いですね、解散

必要なところだけ作る (遅延セグ木 / StarrySkyTree) についての記事も出すかもしれません。

ICPC 模擬地区予選2022 参加記(team plasma)

背景

前から模擬地区予選には興味があったが、年齢の差からビビって出られていなかった。レートも上がってきたし、そろそろいいだろうと思って同期を誘って出ることにした。

 

チーム紹介

primenumber_zz (僕)

典型早解き・筋肉実装マン

DP の数え上げがわりかし得意

チームの中では唯一 AOJ-ICPC を多少埋めている (57250 点)

 

Cyanmond

JOI の難易度 11,12 を埋めている。JOI が得意

 

shiomusubi496

賢い。めっちゃ強い。

 

かくして中三 橙-黄-黄 チームができてしまった。チーム名は PG BATTLE と同じ plasma になった。いつまでこのチーム名続くんだろう...

本番

自分が 11:50 に起きたこともあって、かなり慌ただしいスタートだった。

オンラインでチャットツールは Discord を使った。通話はしていない。

とりあえず Cyan が A 、僕が B 、しおむすびが C を読む。

A AC (10)

10 分で Cyan から AC したと言われたので B を書きはじめた。

Cyan が D を読む。

B AC (15)

5 分で B を AC したのはわりかし偉いらしい、なぜかバグらなかった。

D で Cyan がセグ木 DP と言っていたので制約無理だろ〜wと言いながら応援

Cyan C に D を提出

やっぱり TLE で落ちたので、考え直すことになった。

しおむすびが C 分かったと言っている。天才か？とりあえず実装をしてもらう

自分と Cyan で D を考えていたところ、D は Brave CHAIN 的な発想で出来そうだったのでしおむすびに変わってもらう。

D AC(53)
しおむすびに実装交代。

C AC(73)

この時点でかなり良い順位だったと思う、順位表を見ると H が解かれているので、H を読むことにした、他の二人もバラバラに後ろの問題を見ていた

H の解法がわかる、SCC するとパスグラフになるから DP 出来そう。

しおむすびに SCC のやり方聞いたりペナを吐いたりしながらも AC

H AC(115)

H を実装している時点で Cyan が I を解けそうと言っていたので Cyan に交代。

WA を出してどうかなと思っていたら草。

kaage が JOI 本戦の A でオーバーフローしたので

一瞬何言ってるのかマジでわからなかった。

I AC(168)

Cyanmond つえ〜

H - I の間、自分としおむすびで L を考えていた。しおむすびが初手で重心分解と言っていてビビる、頭良すぎるだろ。そうすると木の同型判定をしたくなるので、Tree Hashing かと思うが検索できないので詰み。色々二人で考えるもわからない。

G も Cyan-しおむすびで議論していたが、こちらもダメそう

J を読むと簡単すぎてビビる。と思っていたら最小値を取る座標は整数じゃなくてもよいらしい。ここで絶望していたらしおむすびが二円の交点を見る。円を決め打ったとき区間になっている。と立て続けに天才をしてくれた。とりあえずしおむすびにライブラリ写経などをしてもらう

E 、K は絶望感がある

ここで F が解かれ始めていたので、考える。

やることはわかるけれど、難しい

→頑張ってたら数列をその数と同じ数がいくつ前に出てきたかに変換すればハッシュで解けそうという気持ちになる。

しおむすびと交代して書き始める。WA。

ここで Cyan も L を書きたいと言っていてカオスが始まる。

とりあえずしおむすびに続きを書いてもらう。

多分ハッシュの衝突なのでどうすっかな〜と言っていたらしおむすびが実装権を渡してくれた。

なんとか AC

F AC (268)

やった〜〜〜、ハッシュの衝突ってそれ以外の場所でバグってたらと思うと実装緊張してしまうなあ

L と J をしおむすびたちに任せて高みの見物をしているとコンテストが終わった

結果

全体 9 位！

感想

J と L に悔しいところはあるけれど、チーム練などをしていない割にはレート的にもかなり好成績なんじゃないだろうか。満足。そもそも ICPC 現役の時に同じ大学に入っているのか・ICPC が存在するのかもわからないけれど、このままこのチームで居られれば大学 1 年でチーム歴 4 年みたいなチームが組めるのはかなり面白い。