ツバサの備忘録

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

ACPC2020 3日目

番外編

最終日！です

内容

通した順です。

A(0:05)

なんで4方向じゃないのだろう…とぼやきながら頑張って実装しました。
幸いバグらせることはほぼなかったのでよかったです。Bに先実装を渡すか悩みましたが書いた方がはやいかなと思い先に書きました。

B(0:07)

とまとさんが累積和ーと言いながらサクサクとおしてくださりました。ありがとうございます。

C(0:11)

\mod{K}を状態に持ってDPをしてくださいとるぎうさんに言われたので、バトンタッチしてサクサク実装しました。これは結構はやく書けたと思っています。

E(0:37, 2ペナ)

最初僕が読みましたがわからず、Dをやっていたとまとさんと問題をスワップ。これがうまくハマり、とまとさんが方針をパッと出してくれて、そのまま実装→AC。
剰余をとると値が半分以下になる、言われればそれはそうですが気づきません…

D(0:56, 2ペナ)

とまとさんとるぎうさんで最初に出した方針が2ペナしたので、とまとさんと僕をスワップしました。と、考察ミスにるぎうさんが気づき修正してもらい、実装がまるっきりかわるので1から実装しなおしました。
scc上の頂点idと元の頂点idを混在させてしまいバグらせたので少し時間はかかりましたが、なんとかACでした。

F(1:27)

Dをやっている間にとまとさんとるぎうさんが考察をしてくださっていたので、その最後の詰め部分から参戦でした。
とまとさんがModIntを持っていなかった(PCが普段と違う)ので僕が実装しました。るぎうさんに、僕がやる意味ある？って言われましたが、実装がしたくなってしまったのであんまり聞こえなかったことにしておきました。
とまとさんに実装を見てもらいペアプロをしつつ、無事ACしました。

G(2:49)

3人でいろいろ考えるも何も方針が立たずだったのですが、るぎうさんがO(N)の計算がO(M^{2})くらいに圧縮できることを伝えてくださったあたりから考察が動き始めました。
僕がO(M^{2}2^{M})くらいのDPを思いついたので画面共有をONにして一人で実装を始め、ガリガリ書きました。
バグらせ(答えるときにdp配列を参照せずreturnするという凡ミス)つつも、なんとかサンプルを合わせ、提出。

3人「ありがとうありがとうありがとうありがとうありがとうありがとうありがとう…」
ジャッジ「AC」

やったぁ！
ありがとうと連呼するの、噛みませんか？

結果

7完22位でした。
やっぱり20位台前半から抜け出せたいのでどうにかしたいですね…
f:id:emtubasa:20200921171228p:plain

おしまい

WUPC、HUPC、ACPCが終わりました！携わっていた皆さまありがとうございました！！！楽しかったです！

ACPC2020 2日目

番外編

ICPCチームです。

内容

また通した順です。

A(0:00)

2 * a + 3 * bを出力するタイピングコンテストです。

B(0:06)

とまとさんが実装しました。問題内容は何もしらず…

C(0:26)

るぎうさんが実装しました。問題文が読みづらくてつらそうでした。

E(0:45)

パッと読んでDPっぽいと思ったのですがすぐにわからなくて、るぎうさんに投げたらこのDPは僕がやるべきって突き返されました。
泣きながらDPを書き上げると、問題文の 残りの白い石の数がw_mより小さい場合は白を選ぶことはできない。 という文章と、 黒い石が残っていない場合、ゲームを終了する。という文章を見落としていることに気づき、慌てて考え直しました(本質部分が抜けた全然違う問題を解いていませんか？)。たまたま書いていたDPが白い石の個数を添え字にもつやつだったので、少し修正して無事ACしました。

F(1:31)

Eの実装をしている際、
るぎうさん「こういうのはツバサ君が実装をするといい感じに書いてくれる」
とまとさん「たしかに、そうしよう」
という話が聞こえて、Eを解き終わったらFの実装を押し付けられました。
再び泣きながら実装し、すこし時間はかかりながらもなんとかACしました…
1次関数の値を求めるのにいもすをしてもう一度累積和をとる(座圧上で)というのは初めてやったので、バグらせて終了させることがなく安心しました…

J(3:53)

割とずーっとこの問題を考えていましたが全然解けず、残り30分少し前くらいに、るぎうさんが クエリ平方分割みを感じる… と言っていたのでその中身を聞くと、確かにそれっぽいとなりまた僕が泣きながら実装しました。
実装が終わっても全然サンプルが合わず、画面共有をして3人で泣きながらデバッグをしていると、残り7分でようやくサンプルが合いました。おそるおそる提出して…1発AC！気持ちよかったです。

G

とまとさんが担当していて、僕やるぎうさんも時々顔を出していましたが、結局BFSの辺が多くなりすぎてわからずでした…

結果

6完ペナ無しで18位。後輩チームにも一応勝ったのでとりあえず一安心です。
f:id:emtubasa:20200920173847p:plain

おしまい

今日は何故か実装をたくさん押し付けられましたがペナは無かったのでとりあえず仕事はできたかなと思います。
あと1日、後輩チームに完数でも差を付けたいですね！(出場するのか知りませんが…)

ACPC2020 1日目

番外編

全日程 Ramen as a Service で参加予定です。

内容

通した順です。

A(0:02)

どうせ割り算すると誤差死するんだろうなと思ったので、きちんと手元で立式しました。
普段より時間はかかりましたが、問題ないスピードでACです。

B(0:31)

何も知らないので何もいうことがありません。とまとさんが危なげなく通していました。

D(1:09)

問題は最初に読みましたが、結局僕がCへ行くため、るぎうさん考察→とまとさんが実装の流れに。
詳しい中身をあまり知りませんが、DPとか二分探索とかセグ木とか言っていたような…

C(1:15, 3ペナ)

いい感じの考察をるぎうさんから受け取り自分が実装。
最小全域木をすればよくて、x本の道を敷いた後テレポーターを割り振る部分が嘘になっていたのでペナを生やしまくりました。冷静になると、制限付きテレポーターを使う場合と使わない場合で2回似たことをすればよかったのに気づき、ようやくAC。

G(1:58)

問題を知りません。三分探索ってワードが聞こえました。この問題の位置にしては簡単というのも聞こえた気がしますが何もわかりません(無責任)

E(2:36, 2ペナ)

序盤のDP部分の後数え上げるところは僕がやるのがよさそう、と先に見ていたるぎうさんが指示してくださったので僕がやりましたが、思ったより包除パートの正しい考察に気づくまで時間がかかってしまいギリギリに…
O(N^{2}S)のDPでModIntを使ったらTLEして泣く泣くintに直してようやくAC...
と思っていたのですが、コンテスト後に確認してみると二項係数の割り算で毎回計算量が \log MODだけ増えていたせいだったぽいです(↓参照)、たまたまそこも書き換えていたので気づかなかっただけっぽい？

F

Eが終わって駆け付けると考察はとっくに終わっていて、提出後のバグ修正中でした。考察は自分が考えたものと先輩方のものが同じだったのでおそらく大丈夫だろうとは思っていたのですが、クエリごとに辺を書き換える部分で無限にバグっていたっぽいです。

結果

6完23位でした。ペナが生えているのが自分の担当箇所のみなので反省しています…
f:id:emtubasa:20200919164023p:plain

おしまい

冷えてるか～～～(実際冷えていて結構焦っていました)

HUPC2020Day3 G Katsusando

動的計画法(DP)

問題
提出コード

解法

まず、二人が出会う地点は必ずカツが置いてある座標になります。途中で挟むとしても、左右どちらかのカツで出会うように適切に調整することで損をすることはありません。

  • dp[i] = 左からi番目のカツまで食べ終えた状態のときに経過した時間の最小値

としてこれを解こうとします。
今、j番目のカツの座標で次のカツサンドを作成するとします。また、

  • d_{(i,j)} = i番目のカツに誰かを配置して、j番目のカツに移動させたときにかかる時間

とします。これはO(N^{2})で計算できます。i,jはどちらが大きくても問題ないです。

そのとき、左側における行動の最適解はmin\left(dp[p] + d_{(p+1,j)}\right)になります。この時間をTとします。これが求まると、
dp[i] = min\left(dp[i], T + d_{(i,j)} + K + 1\right)
という計算をしていくことで、dpの計算ができます。
あとは、dp[N]を答えれば終了です。
コストを求める前計算、dpの計算共にO(N^{2})になります。

感想

カツを挟む部分を決め打った場合に更新が楽にできるようになり、これはあまり普段使わない考え方だったので面白かったです。

HUPC2020 3日目

番外編

1日目はこちら、2日目はこちら
3日目は、とまとさんるぎうさんとのチームです。
例によって問題は解いた順です。

内容

A

ここはサクッと。全体3番目だったので良かったかと思います。

C

るぎうさんがサクッと考察していたのですが、少しバグって僕がコードを見たりしました。
遅すぎはしなかったのでまぁこれから、という感覚でした。

I

るぎうさんに通ってる(けどパッとはわからない)から見てみてと言われたので僕が見たところ、2,3分で最小全域木→倍数→調和級数、という考察フローを辿れたので即座に実装、ACしました。この問題を軽く通せたのは良かった気がします。

M

僕が考えたりるぎうさんが考えたりしましたが、るぎうさんが最終的に考察を出し、僕が実装するという流れに。

  1. 3進数を描きたくなくてmap + stringでごまかす→TLE

  2. 基本strnigでmapの部分だけ3進変換→TLE

  3. stringを一切使わず全て3進数で実装→2.82sでAC(TLは3s)

という流れでした。結構オーダーギリギリだから気を付けてとるぎうさんに言われたのにいう事を聞かなかった僕が完全に戦犯でした。
ところで、よくよくこの問題を見直すと、同じ頂点からの辺は高々1度しかみないという、WUPCのJ問題そっくりの問題だったので最初に見た時点で気づけず反省…

B

最初、とまとさんと僕で解法をくみ上げ、たかだかマンハッタン + 2で抑えられますね、という解法(縦横どっちかを先に終わらせた後、残りを計算)を連打してペナを蓄積しました。
結局、るぎうさん一人で考察しなおしてAC…

E

僕とるぎうさんで考察を行い、考察はいいが自分が実装があんまり思いつかないからどうしよう、と話していたところでとまとさんが参戦。とまとさんとるぎうさんの話を聞いていたところで僕が実装イメージをくみ上げ実装していましたが、まず偏角ソートが幾何ライブラリに入っていませんでした。
yosupo judgeで適当にコードを漁り(かつっぱさんのものを参考にしました、ありがとうございます)、それを自分のライブラリに組み込むことで実装を行いました。
が、なぜか偏角ソートの確認でバグって動かず、よくよく見たらお手製サンプルの方が間違っていて時間を溶かしました(つд⊂)ｴｰﾝ
その後実装を終えますが、なぜかサンプルの答えがグラフ全体の面積に。
手元で確認したところ、辺の向きが逆になっていたので書き直すとサンプルが通り、無事AC。
この時点ではまだあまり通っていなかったので、ここをさっさと処理できたのはよかったです。

この時点で、あと通せそうな問題がG(るぎうさん)、F(とまとさん)に加えて +1問(J,Kのいずれか)になり、これが全部通れば結構いいのではないか、と思っていました。

G

カツサンドの問題ということ以外何も知りません。気づいたら通っていましたシリーズです。ありがとうございます。

F

問題を見終えて割とはやい段階で、swapが定義できること、 GYYというものがあったときに GRR もしくは GBB に変換できること、がわかり、後は細かい部分を詰めればいけそう、という話をとまとさんと二人でしていました。
が、そこから嘘解法にひたすら走ってしまうことになり、結局最後まで通せず…
最後にるぎうさんが駆けつけてくださりましたが、間に合いませんでした。

結果

もう一声欲しいですね(2回目)
f:id:emtubasa:20200916211601p:plain

反省

BやFで、とまとさんと僕が2人で嘘解法を投げまくっていました。
とまとさんの実装スピードがせっかくはやいのに、僕が嘘に気づけず修正ができないのが弱点な気がします…
今後は、るぎうさんが考察のかなめになり、嘘っぽい解法で炎上しかけた際はかならずるぎうさんに見てもらおう、という話になりました。
そのためにも、るぎうさんの考察は僕ととまとさんが実装(実際、僕は変な実装でなければ基本的にスピードがそこそこで、とまとさんはスピード + 安定感があります)することになるので、練習しておこうと思います。

おしまい

3日間はやっぱり多少疲れました…
楽しかったです、運営してくださった皆様ありがとうございました！
弊学チームはACPCでまたボコボコにしたいと思います。

HUPC2020 2日目

番外編

一日目はこちら
yamadさん、とまとさんと yamad as a Serviceで出場しました。
yamadさんが助っ人サービスになる時代…
通した順に書いていきます。

内容

A

3秒くらいオーバーフローどうするんだろう…って悩んでいました。素直に0を出力するだけでした。

B

とまとさんがやりたくないーって少しバグらせつつもしっかり通してくださりました。問題文をチラ見しましたが、本当にやりたくない見た目をしていたのでスルーしました。ごめんなさい。

C

yamadさんが解けないーって言っていたので参戦しました。
二項係数っぽいとかいろいろいいながら、手計算でN=10のケースまで計算し、OEISに投げた結果を見て「ただのDPじゃん！行列累乗じゃん…」と二人で反省しつつyamadさんが通しました。

G

気づいたら通っていました。とまとさんがダブリングとか言っていて、それをyamadさんが通したっぽい？これもB同様問題をチラ見だけしましたが、内容が頭に入ってこなかったのでそっとじしていました。

M

それぞれの頂点にあるグランディ数を求めるのに、O(NK^{2})かかるんですがbitsetで高速化できると思います、と考察をyamadさんに話したら通るはず、と言われたので書きますがWA。
内容を再び細かく説明するお、グランディ数はKには収まらずO(\sqrt{N})くらいなので、bitsetの長さを100から1000にしたら今度はMLEしました。きちんと\sqrt{10^{5}}を計算しなおして317にセットし、ようやくACしました。通れば正義

J

とまとさんに面白そうですと紹介されたので読んでみると、セグ木でDPしたくてたまらなくなりました。
考察を少しすると、この問題にほとんど似ている形に帰着できます。
この問題は、WUPCでも似た問題を作問していて、その既出判定の際にピックアップされた問題だったので記憶に新しく、あとはサクサクと実装できました。ひゃどみん、あの問題を作問してくれてありがとう！

D

yamadさんととまとさんがずっと考えていましたが全然わからず、ただ気づいたら通っていました。内容は知っていましたが、自分が解いたら解ける自信はないです…

I

最初、三分探索という話があがりそれをとまとさんが実装しましたが、30ケース目と31ケース目でずっとWAが出ていました。
その後、想定解をyamadさんととまとさんが思いついたらしく書いていましたが、5ケースしか通りませんでした…
と、残り10分前後で、実は逆行列を求めるパートが間違っているのでは？という話になり、僕がkoprickyさんのライブラリを見つけ、それを使ってみるとなんとAC…
ちなみに解法はなんとなくしか理解しておらず、いまだにふわふわしているので線形代数を勉強する必要がありそうです。koprickyさんありがとうございました。

My Algorithm : kopricky アルゴリズムライブラリ

結果

もう一声欲しいですね。

f:id:emtubasa:20200916211455p:plain

反省

C問題等、変なところでつまるのが多かったです。yamadさんのICPC力をフルに生かすには、僕がもう少し簡単枠をサクサク倒していかないといけないかなと感じました。
ライバル視している後輩チームの1つにペナ差で負けたので悔しいです(途中まで2完差ついていたので、さすがに負けないだろうと思っていました)。

おしまい

明日はまたるぎうさんが復帰するので、 Give us sociabilityをボコボコにしようと思います！

HUPC2020Day1 F: n 角錐グラフ

問題
提出コード

解法

頂点0と別の頂点を結ぶ辺の集合を中心の辺、pとp+1を結ぶ辺の集合を円周上の辺と呼ぶことにします。
i回頂点0に戻る、と仮定したときの数え方が高速に求まれば、これを全部のiについて試せばよいです。
このとき、頂点0を1回だけ通る閉路はi個あるはずです。よって、今回見ているサーキットは、中心の辺がN本の中からi本、円周上の辺はN本からk-2i本選ばれていることになります。
これらの閉路を通る順番はなんでもよく、また、閉路を時計回りに進むか、反時計回りに進むかはそれぞれの閉路ごとに独立に考えられます。よって、最後にi! \times 2^{i}をかける必要があります。
次に、上記の閉路で使う辺のパターンを数えます。
同じ辺を2回以上通れないことから、
(辺を通る区間)(辺を通らない区間)(辺を通る区間)...(辺を通らない区間)
となっているはずです。辺を通る区間、通らない区間は丁度i個になっています。
辺を通る区間の1つが、1,2,...kであると固定します。そうすると、このときの区間の決め方を数えたときに、\frac{N}{i}をかければ、全体での辺の決め方を数えられたことになります(先頭を固定したので、その先頭をN頂点全てに経験させる必要がありますが、先頭のそれぞれの閉路パターンで、先頭の選び方はi通りあります。よってこの値をかければよいです)。
このとき、辺を通る区間、通らない区間それぞれ独立に考えると、
辺を通る区間:_{i}H_{k - 3i}通り
辺を通らない区間:_{i}H_{n - (k-2i) - i}通り
で数えられます。
選ばなければいけない辺の本数がそれぞれ決まっていて、i個の区間に最低1本ずつ割り振る必要があるので、まず1本ずつ割り振った後に、重複組み合わせを考えればよいです。
さて、これにより辺k本を通るサーキットの個数が

  • i! \times 2^{i} \times _{i}H_{k - 3i} \times _{i}H_{n - (k-2i) - i} \times \frac{N}{i}

で求められることがわかりました。
あとは重みの総和ですが、中心の辺が選ばれる確率は\frac{k-2i}{N}、円周上の辺が選ばれる確率は\frac{2i}{N}なので、これをb_i,a_iにかけてあげた後、上記の通り数をかければ答えが求まります。

感想

悩みましたが、実際に数え上げてみると求める解は想像以上に綺麗になるので面白かったです。