ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

HUPC2020 1日目

番外編

僕、とまとさん、るぎうさんで組みました。
コンテスト開始直前に、チーム名が変わって Ramen as a Serviceになりました。

f:id:emtubasa:20200914162432p:plain
捨てられてしまったアカウント(ごめんなさい)

ICPCのチームはこの三人で行く予定でしたが、チーム練習は初めてでした。果たして…

流れ

開始直後

僕がAをさっさと通し、Bをとまとさんが通します(A→0:03、B→0:13)。
その間はるぎうさんがCを読んでいました。僕がDを読み終えた段階でるぎうさんがCわからないと言っていたので、Dの考察をるぎうさんに投げて僕はCに行きました。とまとさんがBを通した頃にるぎうさんからDの考察が返ってきたので自分が実装、とまとさんとるぎうさんでCを解く、という形になります。
コピペOKだったので、自分の幾何ライブラリ(400行)をバン！と貼り、サクサク書いて全体2番目にDをACしました(0:24)。
この間にCの考察が終わっていたようなので、とまとさんにバトンタッチしCもAC(0:30)。

中盤

るぎうさんがEを読み、僕がFを読みます。とまとさんがCを通した後はEに合流していただきました。
Fの考察は、まず0に戻る回数を決め打った際、1以上の頂点について使う辺の並べ方をあとは数えればいい、という部分まで解けていて、その部分がうまくハマらずにうんうんうなっていました。
この隙にEが解けていたらしく、提出→WA。
ここで、自分もFを詰め切った(つもり)ので、Eのデバッグをしていただきながら自分はFの実装を開始しました。
その後、すぐに解法が違うことに気づき修正したらしく、無事AC(1:27)。

とまとさん「二部マッチングのライブラリ2つあるんだけど、片方壊れていた記憶あるんだよね…」  
僕、るぎうさん「両方投げましょう！」    
1回目 → WA(37ケースAC)  
とまとさん「やっぱり嘘解法なのかな…」    
僕、るぎうさん「とりあえずもう一つもだしましょう！」   
2回目 → AC


ライブラリ整備はきちんと行いましょう。

このやりとりのあと、自分はFのサンプルが合わず苦戦。
ところが、今出ている答えから逆算した結果、0に戻る回数で値を割るとサンプルがあってしまうことがわかり、わけがわからない状態に。
半信半疑だったので、るぎうさんととまとさんに考察を聞いてもらうと、それでサンプルが合う理由がようやくわかり、提出、AC(1:59)。ラバーダッキング最強！(素振り)

HUPC2020Day1 F: n 角錐グラフ - ツバサの備忘録

終盤

G、Hは僕が解ける問題に見えず、お二人を応援していました。
Hは双対かな、というところでるぎうさんが詰めていましたが、結局誰もかける人がいなかったので最後の5分は順位表を眺めてお祈りしていました(るぎうさんはメールを書いていました…)。

結果

6完10位でした！同大学の中では多分1位なので、結構うまくいったと思います。
f:id:emtubasa:20200914165015p:plain

反省点

序盤、少しどの問題を読むか？でもたついてしまったので、もう少しスムーズに行けると良いかなと思いました。
G, Hは今の実力では通せないのでペナを少なく、そしてよりはやく解く必要がありますが、D問題あたりは結構理想ムーブをした気がするのでわからず…
F問題で結構もたついたので、ここはもう少しはやくしたいです(おそらく自分がそこそこ得意な枠なので…)。

おしまい

明後日と、ACPCはこのチームでまた出る予定なので、対戦(?)お願いします！

WUPC4th を開催しました

番外編

2020/9/12に行われた、WUPC4thの運営側目線の感想です！
コンテストサイト

運営陣について

早稲田大学の競プロコミュニティは、現B2が今一番ホットになっています。彼らが今回主催となってWUPCを開催しようとしているところにのっかる形で参加することになりました。AOJや告知はadminのHyadoくんや、同じく現B2のかっつくんに任せて、僕は高学年なことをいいことに、いろいろ口出しをしたり邪魔していました。 これが理由で、実はWUPC3とはメンバーが大幅に変わっていて、yamadさんと自分以外は新規メンバーです(WUPC3のお話はこちら)。 以下、writer&tester陣の紹介です:
yamadさん
しろくん
sutaくん
Senくん
かっつくん
Hyadoくん(admin)
ばやしこくん
hotmanくん
オウコウくん
suzukenくん
よぴぱくん

問題セットについて

今回は、5時間で13問という形になりました。

A: Prime Number Sum 2

簡単枠です。昨年のWUPC3rdよりは簡単になったかと思います。
基本区間の幅の偶奇を見ればいいのですが、A = 1、すなわち素数の"2"が含まれている場合だけ、答えが逆になります。
他の問題だけだと序盤から解けなくて詰まる人がいるのではないか、ということから最後に生えた問題です。

B: Canceling Sequence

少し簡単めの構築枠で、当初はこれがAに置かれていました。
[1,N)とN番目の要素に分割し、それぞれの係数をうまく組み合わせて0にすればOKです。緩めの制約にしてあるため、適当につくっても問題の条件を満たします。
僕は構築が苦手なので、この問題を解くのに少し時間がかかりました...

C: Flip Difference Sequence

奇数列目を最大化、偶数列目を最小化すればOKです。あとはどれだけ答えに寄与するか、を計算できればいいのですが、実は二項係数になっています。
問題ができた当初、割と最近のAGCでこれ(ネタバレ注意)が出題されていたので意外と解かれるかも…？と思っていました。

D: Treasure Mountains

自分の問題1つめです。
指数部分について、区間積を計算し、\mod{N}の逆元を計算すれば、xを累乗するだけで簡単にtが求まる、という問題です。
これは、自分が参加したCTFで似たようなことをする問題があり、それが面白いと感じたことから作問しました(元ネタを知りたい方は、 cryptctf three ravens で検索してみてください)。
この問題を作成した時点では作問が閉め切られていたのですが、追加枠が発生したのでそこに滑り込ませました。
数学系の問題を作るのは初めてで、証明をなんども反復して行ったりと不安要素が多かったです。

E: LCM Count

問題を見ると約数包除をしてください、と書いてあるので約数包除をします。
考え方は蟻本のとほぼ同じで、あとは数列の並べ方を気合で数えます。
問題や入力がシンプルかでかつ解法が面白いので、結構好きです。

F: Abyss and Coins

2で割れる回数を固定したとき、その中で取れる最大の数が答えの候補になります。あとは全探索です。
結構アドホック要素多めですが実は素直に見ればいいという問題でした。(僕らの想定では)C以降で一番簡単枠、でした。

G: Fitness

01ナップサックと、個数制限ナップサック両方をやるという問題です。帰着できればすごいサクサク解けてシンプルですがハマると…？
もちろん元ネタはこれです。少し前は諸事情でできなくて、最近再開したのでのんびり頑張ります。
典型 + 典型 で解法も実装もシンプルなので、結構好みです。

H: RGBtree

木の直径が奇数かつ3の倍数 + 一定の条件を満たしたときのみ、他と比べて少しペナルティが大きくなる、それ以外は適切に構築すると最高効率で構築できる、という問題です(簡単に説明するのは難しいので解説を見てください)。
個人的に圧倒的ボス問でした。こういうの解けるようになりたいですね…
yamadさんがすごい不安がりながら何回もこの問題を証明し直してるのを横目に、自分もD問題の証明を必死になって反復していました。

I: Magical Matrix

桁ごとに見て、マスの行と列の差の絶対値が1以内の部分に立っているビットがあるかどうかを見ればよい、という問題です。気づいたり証明したりするのは難しいかもしれませんが、気づけばそこまで数えるのは難しくないです。
これ結構すごいと感じました。作問スキルいいな～。

J: Meet on the Island

一度クエリでYESとなった島は、それ以降常にYESなので、そこを探索しないようにうまく見ていきます。
今いる頂点も、既に探索済みであれば探索しない、ということをしないとコーナーケースにハマってしまうのでご注意を！！

K: Rectangle Game

ミラー戦法をベースにやると、あとは細かい場合分けです。
リアクティブ問題にして実際に構築、等々いろいろ考えましたが難しくて断念しました。
割と最近、こんな問題があり、ビクビクしていました。

L: Count Pow Sum

蟻本239ページを一般化すればよいです。全然しらなかった、面白いです。

M: Star Gazer

suta-Gazerってね。 気合で全方位木DPが最初の想定でしたが、より軽い実装もあります。
木の問題が作りたいなーと言ってるときに生やしました。距離が計算式にあるのに距離を全く使用しなくても解ける、というのが当時のポイントです。

準備について

B2が主体となって進めてくださったので、あとはただその流れに乗るだけでした。
既出等が見つかっても、代理問題を準備できたのでよかったですね。
テストケースが弱くなってしまいがちな問題が今回も多かったので、全員で協力していろいろ作成できたので安心でした。
今回、作問陣だけでは不安が残るということで、外部テスターとして物理好きさん、SSRSさんのお二人に参加していただきました。内容は、完成したセットをバチャ形式で一通り解いていただく、というものです。
お二人とも得意分野が違っていて、解く順序やスピードが異なっていて面白かったです(内部では順位表を見てワイワイしていました)。
特に物理好きさんは、解くたびに問題面白い、とコメントをくださっていて、内部で喜んでいました。

本番

途中、ジャッジが一時期詰まるという事態が発生しましたが、それ以外は特にトラブルなく進みました。
問題文の訂正が一つだけありましたが、後はなんとかなったのでよかったです(B2陣、すごい)。
自分達が用意した問題で詰まったりケースで落ちるのを見るのは最高ですね！！！

終わりに

改めて、参加してくださった皆様、主催してくれたひゃどみん、一緒に準備した皆、サイトを提供してくださったAOJの方々、外部テスターとして参加してくださったSSRSさん、物理好きさん、その他大勢の皆様、本当にありがとうございました！

DDCC2020本戦 C - 特別講演「括弧列と塗り分け」

動的計画法(DP) 二乗の木DP

問題
提出コード

解法

dp[i][j] = [i,j)という区間の塗り分け方、みたいなものを考えたいですが、上手いこと工夫しなければ計算量が大きくなってしまいそうです。
ここで、括弧列が木に対応することを思い出すと、二乗の木DPができそうになってきます。

  • dp[i][j] = i番目の文字(開き括弧)とそれに対応する閉じ括弧までの区間で、R-B = jとなるような塗り方

を考えます。
子にあたる部分についての上記の値が求まっていると、それらを組み合わせてR-B = jとなるような塗り方は簡単に計算ができます。
なので、再帰をしていって、子から計算をしていけばよいです。
このDPは、まさに二乗の木DPの形をしているので、計算量的にも問題ありません。
\sum dp[0][j] \ (|j| \leq K)が答えです。

AGC032 D - Rotation Sort

動的計画法(DP)

問題
提出コード

解法

シフトという操作が少しわかりづらいのですが、結局は

  • 任意の要素を取り出し、別の任意の位置に挿入する(現時点より左に挿入するならコストはB、右であればA)

という操作ができることになります。
ので、それぞれの要素を、 右側に移動してそろえる、左側に移動してそろえる、操作しない、の3パターンに割り振ればよいです。
右側に操作するか左側に操作するか、というのは、今作成中の順列で操作しなかった要素の右端を見ればよいです。

dp[i][j] = i番目の要素まで並べた上で、操作しなかった要素の右端がjであるようなもののなかで可能な最小コスト

とします。
dp[i][j] = \left\{\begin{array}{} dp[i][j] + B \ (a_{i} \lt j)\\ min(dp[i][k])(ただし k \lt j) \ (a_{i} = j) \\ dp[i][j] + A \ (a_{i} \gt j) \\ \end{array}\right.

という遷移を行えばよいです。
dp[0][0] = 0が初期値、min(dp[n][j])が答えです。

AGC043 D - Merge Triplets

数え上げ

問題
提出コード

解法

いろいろな数列を試していると、4つ以上の連続する区間が単調減少することはありません。
この原因を考えてみると、長さ3の数列A_{i}を作成しているため、4つ単調減少させようとすると、1つの長さ3の数列 + どこか1か所別の値が選ばれる必要があります。
長さ3の数列の先頭と、のこりの1つの要素のどちらが小さい場合でも、これらを単調減少させつつPの末尾に追加することは不可能です。
単調減少の先頭に注目、というのを少し拡大し、Pの完成形としてありうる数列に対し、

  • 今までの要素の最大値が出てきたときに、その最大値と、その前の要素で区切る

という操作を繰り返すと、長さ3以下のブロックのようなものがたくさん出来上がります。これらのブロックを組み合わせて、その順番でPに追加できるようなA_{i}が作成できれば、答えにカウントできます。
これまたいろいろ手元で試すと、

  • 長さ3のブロックの個数 + 長さ2のブロックの個数がN以下

であれば、A_{i}が作成可能であることがわかります。
長さ3はそのままA_{i}にすればよく、長さ2のブロックに対しては、適当に長さ1のブロックと組み合わせ、それぞれの先頭の要素の小さい方をA_{i}の先頭にすればよいです。残った長さ1のブロックは、適当に昇順に並べます。
これにより、長さ3以下のブロック集合の作成方法が、そのまま答えになることがわかりました。
長さ2のブロックは、先頭 > 末尾となっていればよいです。
長さ3のブロックは、A \lt B \lt Cに対し、CAB,CBAの2通りが考えられます。
長さ3のブロックをi個作成する、とした時、
\frac{\prod_{j = 0}^{i-1} \left(_{n-3j}C_{3} \times 2 \right) }{i!}
通りの組み合わせが考えられます。
そして、残った数の中から長さ2のブロックをk個作成する時、
\frac{\prod_{j = 0}^{k-1}\ _{\left(n-3i - 2j\right)}C_{2} }{j!}
通りの組み合わせが考えられるので、これを全ての(i,j)のペアについて考えればよいです。

感想

昔解けなかった数え上げシリーズが解けていくのは楽しいです！(前も言った気がします)

ARC082 F - Sandglass

問題
提出コード

解法

クエリが時間順で並んでいるので、時刻を進めながらクエリに答えていくことを目指します。
時刻tのクエリに答えるには、r_{i} \lt tとなるようなr_{i}の中で最大の時刻まで時を進めて砂の量を調べ、最後にひっくり返す部分だけシミュレートすれば良いです。
よって、それぞれのr_{i}にて、最初の砂の量がaであった場合にどうなっているか、がわかればよいことになります。
また、砂の量をaで始めたにも関わらず途中で砂時計の上部の砂が空になり、全て下部にたまった場合、砂の量は始め0(X)であった場合と同一視できます。
このような状態になるaは、区間になっているので、その境界を見つけることができればよいです。
途中で空にならなかった場合は、砂時計をシミュレートしていった場合の増減を累積和で記録しておくことで、ある時刻r_{i}における砂の量がわかります。
よって、あとは0,Xと同一視できる区間の境界が求まればよいことがわかりました。
まず明らかにr_{i} - r_{i-1} \geqq Xの場合、任意のaが初めから0もしくはXであったとわかります。
そうでない場合も、増減の累積和を確認し、ある時刻に0(X)になるaの区間をマージしていくことで、高速に求めることができます。

感想

おおまかな方針はたっていたのですが、細かい部分を詰めるのに結構時間がかかりました。実装もあんまり綺麗ではない？気がするのでもう少しどうにかしたいです。

Typical DP Contest I - イウィ

動的計画法(DP)

問題
提出コード

解法

操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。

  • dp[l][r] = [l,r)の区間の文字全てを消すことができるかどうか

という区間DPを考えます。r-lが3の倍数でない時はもちろんNOです。
[l,r)を全て消去するには、

  • l \leq m \leq rを満たすmについて、dp[l][m],dp[m][r]が共にYESとなるものが存在する

  • S_{l},S_{r-1}がi、S_{m}がwであり、dp[l + 1][m]とdp[m+1][r-1]がYES

のいずれかを満たしていればよいです。(dp[l][l\のような空の区間についてもYESとみなしています)
よって、上記のいずれかを満たしていればYESとすることで、ある区間について全て削除できるかどうかがわかるようになります。
さて、

  • sum[l][r] = [l,r)について行うことができる操作の最大回数

として、再び区間DPをすることでこの問題に答えていきます。
dp[l][r]がYESのとき、sum[l][r]は明らかに(r-l)/3となります。
そうでない場合は、
sum[l][r] = max(sum[l][m] + sum[m][r])
によって計算できます。
以上により、答えを求めることができました。

感想

昔はとっかかりすらつかめなかったものがさらりと解けると嬉しいですね！考察、実装ともにサクサク行けたので良かったです。　

嘘解法はよくないですね！！！(上の解説は修正済みです)