ツバサの備忘録

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

精進メモ 2021/08/02~

精進記

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/07/26~

精進記

公開し忘れていました。

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/19~

精進記

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

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/12~

精進記

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

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本にすればＯＫです。

精進メモ 2021/07/05~

精進記

もうすぐ夏休みですね。コンテスト中の問題を間違えてアップしないよう、週末にアップするようにします。

典型90問

084 - There are two types of characters（★3）

ランレングス圧縮をして、それぞれの長さLに対し、L(L+1)/2を引いていけばOKです。

085 - Multiplication 085（★4）

3重ループを素直に書いたら終わりです。枝刈り。

086 - Snuke's Favorite Arrays（★5）

桁ごとに見て、ビット全探索です。

087 - Chokudai's Demand（★5）

二分探索 + ワーシャルフロイドです。頭がこんがらがり、1ペナしました。

088 - Similar but Different Ways（★6）

鳩ノ巣原理です。全探索をして、見つかった時点で探索を打ち切ります。
最近みたのでさすがに大丈夫でした。

089 - Partitions and Inversions（★7）

しゃくとり + 累積和DPです。
K以下の転倒数になるようしゃくとりを行い、遷移できる箇所に遷移させます。いもす + 累積和です。

090 - Tenkei90's Last Problem（★7）

7点。きたまさ、NTT、FPSをぐっと睨みましたがイマイチわからずです(NTT以外は使ったことないので難しいですね)
DPを頑張って高速化すると7点が取れます。自分の解法の計算量はわかっていません。
種類が\sqrt{K}に落ちるのが面白いですね。

ABC209

E,Fを平行でやったら爆死しました。どっちも自力で通せたので、どちらかに絞るべきでしたね(最近こういうの多くて、Fへ行く勇気が必要なのでつらいです)

C - Not Equal

一瞬かたまりました。
ソートして、C_{i} - iをかければいいです。
ところで、0とのmaxを取り忘れていますがこれは正しいのでしょうか…？

D - Collision

偶奇だけであれば一回DFSすればいいことを完全に忘れていました。
LCAをぺたり。

E - Shiritori

グラフの頂点数と辺数はある程度抑えられるので、後ろからDPすれば良いです。
いろいろ直したせいでコンテスト中にどこにバグがあったのかはわかりません(考察自体は最初から合っていました)…
おそらく、変な頂点を複数回見ていた？のかもしれません。

F - Deforestation

前から素直にDPすればいいです。
一つ前の要素が大きい場合と小さい場合(どちらも等号含む)で、それぞれ似たような遷移をします。累積和を取りながら数えていけば良いです。

精進メモ 2021/06/28~

精進記

気づいたら月が替わっていました。もう半年なのですね…

競プロ典型 90 問

078 - Easy Graph Problem（★2）

グラフの基礎。隣接リストをループで見ればOKです。
初心者？が割と躓きやすい問題だと思います(僕が競プロを教えていた同期も、ここは躓きポイントだと言っていました)

079 - Two by Two（★3）

左上から貪欲に操作をしていけばOKです。
とりあえずできる操作をして、一番右と下の列は最後にチェックです。

080 - Let's Share Bit（★6）

がんばって包除をします。
包除が青ぐらい(ABCのE問題)で出るたびにびっくりしている記憶があります。

081 - Friendly Group（★5）

二次元累積和を取ってK \times Kの正方形の総和の最大値を探します。

082 - Counting Numbers（★3）

おっと、書きそうになりました…(これいつかやらかしそうで危ないですね、本当に気を付けないといけません)
10^{18}だけ場合分けして、あとは等差数列の総和の公式で桁ごとに計算します。

083 - Colorful Graph（★6）

クエリ平方分割で頑張りました。
setをunorderedにしたり、クエリの更新を必要最小限だけ実行するようにしたりと結構キツキツにつめて5ペナの末ACです。

Codeforces Round #729 (Div. 2)

unratedですが久々に出ました。

B. Plus and Multiply

bをした後にa倍をする必要はありません( a回bを足せばよいです)。
なので、1をa倍することを繰り返した時に、残りの差分がbの倍数かどうかで判定できます。
難しいです。

C. Strange Function

1からkまでのLCMを計算し、その値でNを割った値を答えに足す、ということを繰り返せばOKです。

D. Priority Queue

i番目が+のとき、その値の寄与を考えます。
それ以外の要素は、i番目の要素より小さいかどうか、で01を振り分けることができます。
あとは、dp[j][k] = j番目までのクエリのあるなしを決め終え、k個、自分以下の要素が含まれている状態のパターン数
を計算すればＯＫです。
i番目のときだけ、遷移が少し特殊になります。

E1. Abnormal Permutation Pairs (easy version)

i番目までは一致していて、その次の値がことなるとしたとき、その異なる値による転倒数の寄与の差分は簡単に計算できます。
それより後ろの部分についても、挿入DPでどれくらいの転倒数になるかが計算できます。
dp[i][j] = 小さい方からi個の要素を入れて、転倒数がjになるような順列のパターン数
を計算できると、あとは最初の差分と合わせて気合で計算できます。

ABC208

D - Shortest Path Queries 2

僕はワーシャルフロイドを知りませんでした。
手元で再発明して同じ遷移まで出しておいて解けなかったの、悲しいですね
蟻本読んだはずなのですが…

E - Digit Products

DFSで解きました。桁DPでなくてDFS派はほとんどいないのですかね(たしかに桁DPの方が考えることは少ないかもしれません)
N以下が確定したタイミングでそれぞれDFSをスタートさせます。
0が含まれるパターンだけ面倒なので別枠で計算します(これは、0が含まれないパターンの総数を、全パターンから引けばよいので、10のべき乗から9のべき乗を引きます)。DFSは、数字を小さい順に使うと仮定して、総積がKを超えない範囲で決めていき、最後に並べ替えのパターン数を計算します。余計なbreak文を入れていて1ペナしました。

精進メモ 2021/06/21~

精進記

CTFとの両立難しいですね。

典型90

072 - Loop Railway Plan（★4）

DFSを頑張ります。

073 - We Need Both a and b（★5）

木DPです。部分木について辺の有無を決め終え、今見ている頂点を含む連結成分の"ab"の状態が何か、を添え字に持ちます。

074 - ABC String 2（★6）

c があるとき、一番左側の c を選ぶようにしておけば、回数を最大化できます。
dp[i] = i番目を1回操作したときに行える、操作の回数の最大値 とすると、
\displaystyle dp[i] = \sum_{j = 1}^{i-1} dp[j] + 1
となります。
あとは、cを2、bを1、aを0として、\sum_{i} dp[i] \times S_{i}を計算すれば良いです。

075 - Magic For Balls（★3）

素因数分解をし、含まれている素数を数えます。
2^{i}が、その個数を超える最小のiが答えです。

076 - Cake Cut（★3）

総和が10の倍数でなければまず答えはありません。
10の倍数のとき、しゃくとり法で答えがあるかを探せばOKです。

077 - Planes on a 2D Plane（★7）

二部マッチングです。飛行機と、到着地点をマッチングさせます。
復元はいつもの残余グラフを見るやつです。
実行時間が864msになっていて、Dinicの実装見直さないといけないパターンかもしれません…

ABC207

D問題が難しすぎました。

C - Many Segments

共通区間を抜き取るのは、 \max(l_{i},l_{j}),\,min(r_{i},r_{j})を計算するいつものでOKです。
あとは開区間閉区間の細かい部分ですが、l \neq rであれば答えはすぐに決まります。そうでない場合は頑張ります(ただ、そこまでひどくなりません、if文2つでOKです)。
区間を2倍するテク、完全に失念していました。

D - Congruence Points

重心からのベクトル集合を作ります。
それを原点中心で回転させて、2つを一致させることができればOKです。ベクトルをそれぞれの集合から1つ選び、x軸に一致するようにして判定しました。
コーナーケースは、重心部分に丁度点があったとき、そのベクトルをx軸に揃えようとするとバグることです。

E - Mod i

dp[i][j] = i個の数列を決め終えた状態で、\sum_{k}A_{k} \mod (i + 1) \equiv jとなっているようなもののパターン数
とすると解けます。
DPに、zero sum rangesを組み込む形で面白いです。まぁmodで状態をまとめているだけと言われればそうなのですが。

F - Tree Patrolling

dp[i][j][k] = 今見ている頂点を根とする部分木について、監視されている頂点がk個、今見ている頂点に高橋君を配置したか( i )、今見ている頂点は監視されているか( j )
としてDPの遷移を組み立てます。
二乗の木DPです。

AGC054

A - Remove Substrings

先頭と末尾が異なる場合、明らかに答えは1です。
それ以外の場合、2つ連続して、先頭と異なる文字がある場所を探します。あれば、明らかに答えは2です。
それ以外の場合、連続するどの2点を選んでも、必ず1つは先頭と一致してしまいます。そのため、どのように削除しても空文字列にすることはできません。

B - Greedy Division

高橋君と青木君が選ぶミカンの集合を決め、それぞれ適当な順番で並べます。すると、それに対する順列は1通りに決まります。
この決め方でできる順列は重複しないので、丁度総和が半分ずつになる集合を選び、i, n-i個だったとすると、i! \times (n-i)!を答えに加算すれば良いです。
あとはi個選んで総和を全体の半分にする集合の決め方を数えられればよく、これは

  • dp[i][j] = i個選んで総和がjになるようなパターン数

として遷移をすると間に合います。

C - Roughly Sorted

まず、ある順列が与えられたときに、問題の条件を満たすような最小の操作を探します。
これは、自分より左側にある、自身より大きい数の個数がKを超えているインデックスのうち、一番左側にあるものを、より左側に動かす、という操作を繰り返せばよいです。
Kを超えているものを左側に動かしても、swapされて右側にきたものが新しくKを超えることはありません。
ということで、この操作を逆順に見ます。
すると、今自分より大きい数が左側にK個あり、自分の1つ右隣も自分より大きいものについて、元々の順列の位置は、今いる位置、もしくはそれより右側であれば何でも条件を満たします。
これは、順列の数字それぞれ独立に考えることができ、最終的には

  • 上記の条件を満たすiについて、N- i (0-indexed)の総積を計算したもの

が答えになります。