2021-08-29

精進メモ 2021/08/23~

精進記

構造化束縛が便利なので、これを使ってちょっとした3つ以上の構造体は全部Tupleに任せてしまうのもいいかもしれないです(可読性と要相談)。
久々に1日10問とか解いた気がします。やっぱりやると楽しい。

AOJ-ICPC
ABC216

AOJ-ICPC

10万点いきました。ちょうど300問。
f:id:emtubasa:20210828212201p:plain

1389 - Digits Are Not Just Characters

比較関数を頑張って実装します。

1306 - Balloon Collecting

$dp[x] =$ 今バルーンを受け取った時刻に個数が $x$ になるような動き方の中で、距離が最小になるもの、として計算していけばOKです。

1315 Gift from the Goddess of Programming

時刻をパースして、"000"と一緒にいる時間が一番長い人を求める問題です。
"000"が入るタイミングで、今いる人は今の時刻分値をマイナス、"000"かほかの人が抜けるタイミングでその時刻分値をプラスしていけばいいです。

1248 The Balance

ダイクストラをしました。
個数と重さの合計で大小を定義し、現在はかれる重さに+a, -a, +b, -b, +(a-b),+(b-a)の6通りを計算するパターンを遷移としました。

2166 Erratic Sleep Habits

$dp[i][j] = i$ 日目にサイクルが $j$ 番目になるようなパターンの中で、カフェイン摂取回数の最小値
として計算していきます。

1326 Stylish

$R,C,S$ を全探索すればOKです。
括弧の個数は累積和を取ればいいです。
構文解析に見えて構文解析はいりませんでした。

2730 Line Gimmick

最初は面白いと思いましたが細かい計算で頭を使いました。
ある>をスタートにするとき、その>から左にある>の個数と、それより右にある<の個数の大小で、最終的に右と左どちらに行くかがわかります。
最終的に取り除いたパネルは、どちらかの端を含む区間になるので、端でない側がどこまで到達できるかを求められれば答えがわかります。

1380 Medical Checkup

$i$ 番目の人のインターバルは、 $\max(h_{j})$ になります。
開始時刻は $\displaystyle\sum_{j = 1}^{i-1} h_{j}$ になります。
あとはこれを計算すればいいです。

1390 Arithmetic Progressions

$(i,j)$ のペアを高々一度だけ見るようにすればよいです。
先頭の2つを決めたら、その後に続く列は自動的に決まります。先頭ができるだけ小さい方から見ていき、既にチェックしたペアは先頭に持ってこないようにすればOKです。

1391 Emergency Evacuation

最初に距離を計算し、あとは入れられるところに詰めていけばいいです。適当に空いている要素を全部setに挿入し、使うたびにsetから削除していけば、二分探索で次の人の時間を決められます。

2906 Santa's Gift

サイズを人数で割ると、全ての $1 \leq k \eq M$ の総和は $O(M \log M)$ です。
よって、あとは $1/k$ した状態でナップサックを解いていけばいいです。

2912 Sum of QQ

$(\sum_{i = a}^{b}i) \times (\sum_{j = c}^{d}j)$ が $S$ になるような $(a,b,c,d)$ を探せばよいです。
$(a,b)$ と $(c,d)$ は独立に探せます。
$a,b$ の組み合わせは $1$ から $10^{5}$ まで愚直に探しても間に合うので愚直にメモしていけばOKです。
よって、 $pq = S$ となるような $(p,q)$ について、先ほどのメモしたカウントの積を足していけばおしまいです。

2847 Ninja Map

頑張って左上から順に復元していきます。
隣接する辺を決まったところから削除していくと、あとは残っている辺を選ぶだけになります。

1280 Slim Span

辺を重みでソートして、ある辺を最小値としたときに、必要な辺の重みの最大値の最小値を二分探索で求めます。判定部分は、Unionfindを用いればできます。

2320 Infinity Maze

右手法をダブリングします。
$L$ が小さいと思って最初は愚直にシミュレートしていました…

ABC216

得意セットでした。

C - Many Balls

+1と×2で構築する問題です。いつものビットを見ながら後ろから決めていく形でOKです。

D - Pair of Balls

1問目に開いたのですが、すごくてびっくりしました。
愚直に取り出せるところを取り出していけばOKです。
取り出せる色をqueueに入れ、シミュレートしていきます。
どの筒にそれぞれの色が入っているかをメモしておけば、筒から取り出して先頭の色がどうなっているかも簡単にわかります。

E - Amusement Park

大きい方から愚直に選んでいけばいいです。今一番大きい値が複数同時にあるとき、まとめて計算するようにすれば、 $N$ 回の計算で終わります。0を配列に入れておくのがポイントです。計算がしやすくなります。

F - Max Sum Counting

Eより先にニコニコしながら解きました。 $(A,B)$ を $A$ の昇順でソートしておくと、ナップサック問題と同じような形のDPに落とせます。総和が $S$ になるようなパターン数を数え上げ、最後に使った $i$ についての $A_{i}$ が $S$ 以上であれば、今数えた部分を答えに加算します。総和は5000まで見ればOKです。
面白かったです。

G - 01Sequence

区間スケジューリングで構築していけばOKです。
$R$ が小さい方から見ていき、右詰めしていきます。今見ている条件についてあといくつ置くべきかはBITで区間和との差分を見れば良いです。右詰めパートは、まだ使ってないものを適当にsetに入れておけば、set上の二分探索で一番右が求まります。
実装は軽めでした。面白かったです。
~~Online Judge toolを使うと、実はサンプルアウトプットの最後に空白があることがわかります~~

2021-08-22

精進メモ 2021/08/16~

精進記

ABC215

久々に2桁順位を取った気がします。

D - Coprime 2

ひたすら素因数分解すれば良いです。
全ての $A_{i}$ に含まれる素因数の倍数を除くと答えになるので、愚直に計算していきます。調和級数で計算量が収まるタイプです。

E - Chain Contestant

既に行ったコンテストの種類をbitでもって、最後に何が開催されているかと合わせて添え字にするタイプのDPです。

F - Dist Max 2

最小値の最大化は二分探索です。
二次元座標はどちらか片方でソートすると嬉しいことが多いのでそれを考えると、判定部分で尺取りができることがわかります。

G - Colorful Candies 2

まず、キャンディの種類ごとにまとめて計算できることがわかります。なので、それぞれの種類に対して個数を求めておきます。
種類数が $\sqrt{N}$ 以下のとき、期待値の線形性を利用して $O(N\sqrt{N})$ で計算できます。
そうでないとき、登場する個数の種類が $\sqrt{N}$ に収まっているはずです。個数ごとに計算する値は同じなので、そこをまとめることで、結局どちらの場合も同じ計算量で解くことができます。
頻度の種類が $\sqrt{N}$ で収まる問題、苦手でしたがついに自力で解けました。

ARC125

途中でパフォを見てぬか喜びしました。難しい問題を先に解いていたのでそれはそうでした…
やっぱり構築が苦手ですね。あと再帰的に綺麗に解けます、みたいなタイプも苦手なのかもしれません。

A - Dial Up

$A$ の末尾に追加すると誤読していました。
01の切り替わりタイミングまで移動したら、あとはコスト2以下でどちらも追加できます。そこだけ調べてあとは愚直シミュレートです。

B - Squares

$x^{2} - y = z^{2}$ とすると、式変形して $(x + z)(x - z) = y$ となります。
$x,y,z$ は非負なので、 $x + z \gt x - z$ です。
よって、 $x - z \lt \sqrt{N}$ であることがわかります。
$x-z$ を $p$ と固定したとき、条件を満たす $q = x + z$ がいくつあるかを求めればよいです。
$pq \leq N$ なので、 $q$ の個数はだいたい $N / p$ の半分くらいになります。
あとはこれを足し合わせていけば答えです。

D - Unique Subsequence

$A_{i}$ を選んで問題の条件を満たすには、その前後で選ぶ箇所が $A_{j}, A_{k}$ としたとき、区間 $(j,i)$ および $(i,k)$ に $A_{i}$ が存在してはいけません。
逆に、この条件を満たせば、問題の条件を満たします。
$dp[i] = i$ 番目を最後に選んで、問題の条件を満たしているような数列の個数
とすると、セグ木を使って区間和を計算しながら更新ができます。
数列の先頭と末尾に0があると仮定して計算していくと計算がしやすかったです。

2021-08-14

精進メモ 2021/08/09~

精進記

ABC214

ABC214

ペナ出し過ぎです。

D - Sum of Maximum Weights

全方位木がちらつく中、UnionFindが初手で見えたのは良かったです。
が、long longのミスを久々にしたり、インデックスのズレがあって2ペナしました。さらに、間違えてB問題に提出して計3ペナです。

E - Packing Under Range Regulations

未証明です…
Rの昇順、Lの降順でソートして、貪欲に左から詰めていきます。
入れられない区間をsetで管理するパートが本質で、実装が複雑です。ミスして1ペナしました。

F - Substrings

初手で↓の記事を読みました。連続している部分を数えないように調整しながら似たような実装をそのまま行いACです。

emtubasa.hateblo.jp

2021-08-08

精進メモ 2021/08/02~

精進記

ABC212 G - Power Pair
ABC212 H - Nim Counting
The 15th Chinese Northeast Collegiate Programming Contest
ABC213

ABC212 G - Power Pair

提出
途中まで解説を読んだので、ほぼ解説通りです。
位数の総和を求める問題ですが、原子根を持ってきて肩の数字の比較で条件をつくります。
$an \equiv b \mod{p-1}$ を満たす $(a,b)$ を数える問題になります。
ある $a$ に対して、 $b$ が $x$ 個となるのは、 $p-1$ との $\gcd$ が $(p-1)/x$ となるときです。
位数は、 $p-1$ の約数個しか種類として登場しません。
逆に、 $(p-1)/x \times k$ となるような、 $x$ と互いに素な $k$ は、これを満たします。
よって、あとは $x \times (kの個数)$ を数えればよく、これはオイラーのΦ関数で求めることができます。
原子根、Φ関数あたりは知っていますが、活かしきることがいつもできないですね。

ABC212 H - Nim Counting

提出
 アダマール変換とダブリングです。
アダマール変換さえ書ければあとは…というところでした。未履修だったのでコンテスト中は解けずじまいです。

The 15th Chinese Northeast Collegiate Programming Contest

チーム練です。suzuken君と二人でした。
自分はA,E,C,D,Hを担当しました。suzuken君がI,K,M,Jです。
~~嫌な問題を全て押し付けました~~

A. Matrix

$N^{2}! \times N - N \times _{N^{2} - N}P_N \times (N^{2}-N)!$
が答えです。前計算の配列サイズを間違えてREしました。

E. Easy Math Problem

$6p$ として、 $p,2p,3p$ を部分集合として選べばOKです。

C. Vertex Deletion

頑張って木DPをします。今見ている頂点が、ひとりぼっちになっているか、子のいずれかと連結か、見ている頂点自身を消すかの3通りで場合分けです。

D. Lowbit

解法は好きです。
立っているビットが1つずつ減っていき、1になると、それ以降は常に2倍になります。
立っているビットは数十個以内なので、その部分だけは愚直に計算してあげて、ビットが1つになったら、区間更新でまとめてあげます。

H. Loneliness

初手で一周を考えたのが正解でした。
時計回り、反時計回りで+1および-1が作れるので、下にいった場合の2倍と組み合わせて、目標の数字に作り上げていくいつもの構築をすればよいです(奇数は作れません)。
右端の方に寄せてあげるパートでとてつもない回数を食ってしまうのですが、この部分はsuzuken君が回数を減らす方法を考えてくれました。
少し下に移動してから上に戻ると、回数がかなり抑えられます。
2が作れないと思い込んでいましたが、上記の方法を使えば2も作れました。

ABC213

頭が疲れていて全然まわらなかったです。F通せないのは悔しいですね。

C - Reorder Cards

座圧だけであれば特に苦手としていなかったのですが、まわりがはやすぎてびっくりしました。

D - Takahashi Tour

DFSをすればOKです。

E - Stronger Takahashi

01BFSです。上下左右はコスト0で、パンチを1回使った際に移動できる範囲はコスト1で移動します。綺麗な書き方が思いつかなかったので適当にコピペしたら、バグりました。

F - Common Prefixes

Suffix Arrayを使って、LCP配列を求めた後、累積minの総和を求めるのはすぐにわかりましたが、それぞれの計算を行う部分をまとめてやる方法が思いつきませんでした。
stackを使って処理を行う感じでやればいけるかなぁと思いついたのが残り3分だったので間に合いませんでした。
体力が残ってないので後日に…

2021-08-02

精進メモ 2021/07/26~

精進記

公開し忘れていました。

2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020)
ABC212

2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020)

チーム練です。ばやしこくん、suzuken君と出ました。
suzuken君:A,C,I(考察)
ばやしこくん:D(考察)、G(考察・実装8割)、K
僕:D(実装)、E、F、G(実装2割)、I(実装)
という担当でした。

D. Jogging

下限は無視してよく、まずはダイクストラを普通にします。
それぞれの頂点について、そこまでにかかる時間×2が、上限未満であれば、その頂点に繋がっている辺を答えに加算できます。
答えをチェックする配列のサイズが $N$ になっており、1ペナしました。反省。

F. Mentors

大きい方から愚直に当てはめていけば良いです。
子が既に1つある頂点の個数でまとめられるので、あとはDPです。 $R$ については特別処理するだけでOKです。

H. Figurines

永続セグ木で検索すると、hotman君の記事が出てきて、それを読むとそのまま応用できる問題が出てきます。これを頑張って書き換えればOKです。
OKですが、入力について、それぞれの日について、フィギュアの更新が2つで固定というわけではないらしいです。これに気づけず、コンテスト中はACできませんでした。
許しません。

I. Emails

適当な頂点から最遠点を探すと、グラフ内の距離の最大値は、先ほどの最遠点の2倍以内に収まります。
答えは、その距離のlogです。

ABC212

FGHのうち2問解こうとしたら、GHが解けなくてFもギリギリになってしまいました。さっさとFを解いておくべきでした…

D - Querying Multiset

mapで $X - (これまでに加算した値の総和)$ を管理します。
出力時は、一番小さい値に、現時点での総和を足せば答えです。

E - Safety Journey

包除でやったらMLE＆TLEの1ペナをしました。配列のサイズを減らしたら通りました(TLEはよくわからず)。
$dp[i][j][b] = i$ 回移動して、今 $j$ にいるようなルートの中で、違反した回数が少なくとも $b$ 回(偶奇)になるようなもののパターン数
として遷移すればOKです。

F - Greedy Takahashi

力でなんとかしました。
バスについては、乗る時刻と降りる時刻、クエリについては、出発する時刻と出力をする時刻の2つにわけます。
あとは、時刻でソートを行い、それぞれを順番に処理していけばいいです。今どの頂点にいるかは、バスの乗り降りをするたびにUnion Findでうまくまとめました。

2021-07-25

精進メモ 2021/07/19~

精進記

そろそろ大学のチーム練が始まりそうで楽しみです(出られるかは置いといてですが…)

ABC211
ARC124

ABC211

順位は良かったのですが、Fで思いのほかてこずってしまったので少し悔しいです。

D - Number of Shortest paths

これのBFS版ですね。つまりこれと全く同じです。

最短経路を計算しながら数え上げもしていきます。

E - Red Polyomino

サンプルが答えです。
個数が多くないので、dfsで探索していけば終わります。bitで持つのが楽でした。

F - Rectilinear Polygons

考察自体はシンプルな気がしました。実装を頑張る問題。
平面捜査をしていけばよいです。
x軸の向きで見ていくとき、ある多角形について、縦の直線が、その範囲の座標で奇数回目に登場していれば直線の座標すべてに+1を、偶数回目であれば-1をします。
少し近い？考え方として、これがあります。
点のクエリに対する答えは、+されている現在の回数を見ればよいです。
いもすでやっていましたが、バグったので遅延セグ木に変えました。それでも結局かなりバグらせて、時間を食ってしまいました…

ARC124

苦しい結果です。

A - LR Constraints

可能なカードの枚数をそれぞれメモすれば良いです。二乗が間に合うので愚直でOKでした。
文字のLRの判定を間違えて数字の入力で判断していたため、実装に時間がかかりました。

B - XOR Matching 2

$A_{0}$ を固定して、それに合わせる $B_{i}$ を愚直に試せばOKです。
必要な数の個数と、 $B_{i}$ のカウントがあっていればOKです。

C - LCM of GCDs

まず、全体を全ての要素の $\gcd$ で割って問題ありません。これは最後にかければ答えになります。
すると、2択を選んでいき、それぞれの集合の $\gcd$ の掛け算が最大になっていればＯＫです。
あとは、愚直に2択を選んでいけばいいです。 $\gcd$ のペアの個数は少ないです。

D - Yet Another Sorting Problem

初手で実験を選んだのは大正解でした。デバッグでも大活躍しました。
割とはやめに考察は終わっていたのに、コーナーケースの処理がきちんとできていなくて40分ほど時間を溶かしました…パフォが200ほど落ちているので厳しいです。
実験をすると、 $i = p_{i}$ という操作を繰り返して行くループそれぞれ独立にまず数えればOKということがわかります。
どちらかの値一方しか入っていない場合、両方を行き来する場合があります。
前者は、(長さ + 1)を足します。これは、1度反対側の適当な箇所とスワップをして、列の値を揃えていき、最後に元に戻すという操作です。
後者は、(長さ - 1)を足します。これは素直に、1つずつ戻せる箇所を戻していけば良いです。
コーナーケースは、左側のみのケースおよび右側のみのケースが複数個存在していた場合、 $2 \times \min(左の個数, 右の個数)$ を答えから引くことです。これは、左と右のみのループの列について、その中から1つずつ最初に選ぶことで、最初の適当な箇所をスワップする、という操作の無駄がなくなり、(長さ-1)のケースに帰着させることができるからです。
以上をまとめて数えれば、答えとなります。

2021-07-18

精進メモ 2021/07/12~

精進記

精進量が明らかに減っていてパフォーマンスも落ちているのでピンチです。

ABC210
謎のコンテスト
ARC123
- A - Arithmetic Sequence
- B - Increasing Triples

ABC210

Fはまだ仕方ないとして、ペナルティをたくさん出しているのは少し残念です。

C - Colorful Candies

スライドしながらmapで管理していけば良いです。
更新のタイミングがおかしくて1ペナです。

D - National Railway

上から順番に見ていくと、1マス左右もしくは下に移動するたびに、 $A_{i,j}$ の値が $C$ 増えるとして、累積 $\min$ を取っていけば良いです。
同じ行で左右に割り振るパターンをまず計算した後、下に全部ずらしていきます。
同じマスを始点と終点の両方にしないように注意しながら実装する必要があります。2ペナしました。

E - Ring MST

基本的には最小全域木です。新しく辺を張れるのであれば、張れるだけ張っていけばいいです。
GCDを取りながら張る辺の本数を数えていけばOKです。

謎のコンテスト

CTFと同時開催？している謎の3hコンテストに出ました。
難易度はICPC国内予選セットくらいでした。
結果はイマイチでした…

ARC123

久々に青前半パフォをたたき出した気がします。

A - Arithmetic Sequence

3パターンくらい考えられるケースを考えて、適当にやったら通りました…
Aを合わせるパターン、Cを合わせるパターン、B + ACの偶奇を合わせるパターンです。

B - Increasing Triples

素直な問題でした。貪欲で問題ないので、A、B、Cの優先順位で前から見ていきます。
しゃくとりを3本にすればＯＫです。