縦で見ると、黒白…と白黒…のどちらかを選択することになります。
$2^{M}$ 通りです。
横も同様ですが、全体が綺麗な市松模様になっている箇所が重複するので上手くひく必要があります。
また、隣接する2列が同じ並びになっているものが存在した場合、横方向で見ると黒黒、となっているため、一意に定まってしまいます。
そうなっていない行、もしくは列について、まだ確定していない部分の並びを決めていけば数えることができます(手抜きだと説明が難しいですね)。

Aizu Competitive Programming Camp 2021 Day 1

suzuken君、serpent君と3人で出ました。
ユナイトをしていたら開始まで残り5分になっており、チーム名が決まっていました。

E: ヘクト問題

$i$ 番目の数列の $j$ 番目の要素は、 $i \times j \mod{P}$ とすればよいです。
綺麗な性質がありそうだなと思っていたのですが、suzuken君が一言掛け算、と言ったのでこれを思いつきました。

F: SからTを作るやつ

操作2のみを繰り返して、長さを最大にしておきます。すると、0101...という文字列になります。この部分文字列であれば、任意の文字列をつくれます。

G: Round Tour

$dp[i][j] =$ 行きで $i$ 番目、帰りで最後に $j$ 番目を通り、 $1$ から $\max(i,j)$ 全ての頂点を通るルートにおける最小コスト
としてDPすればよいです。復元がバグっており間に合いませんでした。

H: TUAT文字列

子音 $p$ と母音 $q,r$ は全探索します。
これらを一つ決め打つと、作成できる文字列のパターン数は $_{4}H_{N-4}$ となるので、ここから、 $S$ より前、もしくは $T$ より後ろの文字列となっているものを数えればよいです。

Aizu Competitive Programming Camp 2021 Day 2

ICPCのチームで出ました。

B I am sleepy

$dp[i][j] = i$ 秒後に $j$ にいるような移動の方法のなかでの最適解
としてDPすればいいです。pairを持たせます。

D WeightedLIS

$dp[i][j] = i$ までみた時点で数列の最後の値が $j$ になっているときの最適解
としてDPすればいいです。セグ木で更新します。

G Tree Propagation

dfsしながら答えを計算していきます。
$N(N-1)$ から白い頂点の個数を引いていけばよいです。距離が $i$ の頂点については、自分の部分木について、距離が $2i,2i-1$ の頂点の個数だけ部分木サイズ分の答えを引きます。
最後に $N-1$ を引けばおしまいです。

K All Clear

それぞれのステージに対して、腕前が $X$ であったときにクリアできる回数の最小値を計算すると、 $X$ の増加に対して単調減少していきます。
この回数が切り替わるタイミングが答えの候補で、 $4N$ 回しかありません。
ので、 $X$ の降順でソートして逐一計算して、全探索すればＯＫです。

ARC127

Cの速度が…

A - Leading 1s

なんでもいいので実装できればいいです。がんばります。

B - Ternary Strings

先頭が0,1,2の文字列が $N$ 個ずつあります。先頭が2の文字列について、辞書順をできるだけ小さくするようにすればいいです。
そのためには、先頭以外の残りの部分を、3進数で $0$ から $N-1$ まで表現していけばよいです。
先頭が0,1については問題の条件を満たすよう適当に文字列を生成すればいいです。
先頭が2の文字列を作成した後、 $\mod{3}$ で1ずつ加算していくのが楽でした。

C - Binary Strings

上位ビットから見ていくと一意に定まります。よく見る問題。
引き算は遅延セグ木で実装しました。

Aizu Competitive Programming Camp 2021 Day 3

ソロ参戦でした。チーム戦にソロ参戦は夢でした。

B: Sufficient Condition

素因数が2個以上含まれているものがあれば、答えが存在します。
個数を半分(切り上げ)にしていけばいいです。

C: Separate Number

総和が $A_{i}$ になるまで $B_{i}$ の累積和を取っていく、という操作を繰り返していきます。
その区間ごとに答えを計算します。
場合分けが少々多いので注意します。

D: Successive Tree

頂点 $i$ が選ばれたときに足される距離の期待値を計算すると、あとは平均を取れば答えです。
頂点 $i$ について加算される距離の期待値は、 $[0,i)$ についての距離の期待値の平均 + 1になります。
あとは愚直に計算していけばOKです。

E: +- Switch

未証明です。鳩ノ巣っぽい問題なので、DFSで適当に調べたら通りました。

F: A2B

まずは、総和が変わらないことに気づきます。この手の問題は、何かが隣接swapになっていることが多いので頑張って探すと、累積和の隣接swapになっていることに気づきます。
あとは転倒数を計算すればおしまいです。

G: XOR Walk

$x$ と $y$ の距離が奇数であれば、合計が奇数個になるように頂点を選んだ総XORであればなんでも作れます。
偶数であれば、頂点を偶数個選んだ総XORであればなんでも作れます。
二部グラフでない場合は奇数と偶数のルート両方作れるので、なんでも作れます。奇数個、偶数個選んで総XORを最大化するには、 $2^{61}$ を全要素に追加して基底を求めると、 $2^{61}$ のビットが立っている場合は奇数個、そうでない場合は偶数個になります。
奇数個のパターンは、基底全体での最大値を求めればよく、偶数個は、 $2^{61}$ のビットが立っていない要素のみで最大値を求めればいいです。

ABC220

Ｃ問題にやられました。

C - Long Sequence

$\gt$ を $\geq$ と誤読する痛恨のミスで15分 + 3ペナの大事故です。
二分探索でもループ回数計算するでも何でもいいです。

D - FG operation

DPします。

E - Distance on Large Perfect Binary Tree

深さがおなじ頂点達は対応するもう片方の頂点の個数が決まっています。
丁寧に相方の個数を探してあげればよいです。
何回で折れ曲がっているかで全探索しました。

F - Distance Sums 2

僕が作った問題の弱いバージョン。きちんと貼りました。

G - Isosceles Trapezium

$O(N^{2})$ で線分全部を洗い出し、平行な直線を見ていきます。
元々の線分および、垂直二等分線の傾きと切片が一致していればいいです。
同一直線上に注意。コンテストの80分あたりに提出していたコードの $0$ を $ix$ に変えるだけでACしたので少し悲しいです。

2021-09-20

精進メモ 2021/09/13~

精進記

AOJ-ICPC、350が埋まったのでだんだん辛くなってきました。

AOJ-ICPC
- 1399 Sixth Sense
- 1337 Count the Regions
Northern Eurasia Finals Online 2020
ABC219
ARC126

AOJ-ICPC

1399 Sixth Sense

suzuken君に投げられました。
辞書順が無ければソートして小さい方から貪欲に詰めていってOKです。
そのときのスコアを計算する関数を作っておきます。
答えの数列を前から決めていきます。
ある箇所について、まず $p_{i}$ より大きいか、そうでないかを選択します。どちらも、条件を満たす中で最小のものを選びます。
そのときのスコアを計算し、最終的に大きくなる方を選びます。同じであれば辞書順が大きくなる方です。
その後、条件を満たすなかで辞書順が最大になるような値を探します。
ここは二分探索で求めることができます。
これを繰り返すことで答えが求まります。

1337 Count the Regions

$n \leq 50$ を完全に失念していました。
座標圧縮すると、マス目上でUnionfindを行って連結成分の個数を数える問題になります。

Northern Eurasia Finals Online 2020

絶不調でした。

Geometrical Combinatorics

諸悪の根源です。一問目に開いたのが運のつきでした。
斜めの直線ごとに見ていけば、公式を使って計算できるはず…なのですが、結局最後まで通りませんでした。誤差なのか、考慮もれなのかはいまだわかってないです。

A. Almost Balanced Tree

2を優先的に使います。
2と1の個数を基本的に半分になるように分けます。ズレる部分は1を移動させて微調整します。

Lookup Performance

ある頂点にいるとき、クエリ $L,R$ に対して再帰を行わない条件は、今いる頂点のminとmaxが $(l,r)$ であるとき、
$R \lt l, r \lt L, L \leq l \leq r \leq R$ のいずれかの条件を満たすことが必要です。
また、ある頂点でこれらを満たした時、その部分木における頂点全てが上記の条件を満たします。
ということで、(上記の条件を満たさない頂点の個数)×2 + 1が答えです。
1,2番目の条件は簡単に数えることができます。
3番目は、suzuken君にwavelet treeで殴ってもらいました。

ABC219

爆死しました。ICPCチームメンバーが温まっているのでヨシとします。

D - Strange Lunchbox

$dp[i][j] = i$ 個使って $j$ 個の鯛焼きを買えるときに購入できるたこ焼きの最大値、としてDPをします。
初期値を間違えて2ペナしました…

E - Moat

あなぽこは含むものだと思っていたら、Clarで含みませんと言われて泣きました。
結局そこからバグり続けて終わりました。
囲まれているかどうかをビット全探索すればOKです。
村を全て含むか、連結であるかどうかは簡単に判定できます。後者はUnionfindでＯＫです。
あなぽこ判定は、白のマスが外側と全て繋がっているか判定すればいいです。途中から実装をしたため、手抜き実装をしたら

のケースで落ちるような実装になっていました。

F - Cleaning Robot

日曜日に解きました。
文字列一回分を1セットとし、到着するマス目を洗い出します。
そして、1セット単位で移動する距離 $(p,q)$ も計算します。
これらが共に0であった場合は1セット分のマス目の個数が答えです。
$p,q$ のうち片方が0であった場合( $p$ が0であるとします)、重なるパターンは、到着するマス目 $(a,b),(c,d)$ に対し、 $(a,b \mod{q})$ と $(c,d \mod {q})$ が一致し、 $b / q + i = d / q + j$ となる場合です( $i,j$ は操作回数)。
なので、 $(a,b \mod{q})$ ごとに $b / q$ をメモしていき、 $[b/q,b/q + K)$ の区間の共通部分を全体で考え、区間の幅を計算すると答えになります。
$p,q$ どちらも0でなかった場合は、
$(a \mod p,b \mod q,a/x - b/x)$ に対する $a/x$ をメモすると、同様の計算で答えが求まります。

ARC126

不調の後には好調がやってきます。

A - Make 10

FAまであと少しでした。
長さ3のものは優先的に使います。
それが終わったら、4を優先的に使います。
あとは2だけで作って終わりです。

B - Cross-free Matching

LISに気づきませんでした。
$dp[i][j] = i$ 個めの線分まで見終えて、最後に選んだ線分の $a$ が $j$ であるときに選べる線分の最大値
とします。 $a_{i}$ で線分をソートしておくと、上記のDPをセグ木で更新できるようになります。
$a_{i}$ が同じものは同時に更新する必要があります。

C - Maximize GCD

とても好きな問題です。 $M = \max(A_{i})$ とすると、全部の要素を $M$ 以上にできる場合は答えが簡単に求められます。余った操作回数を均等に割り振るようにすればよいです。
そうでない場合を考えます。
$\gcd$ が $x$ にできるかどうかを考えた時、それぞれの要素は $x$ の倍数でなければなりません。 $A_{i}$ について、その値以上の $x$ の倍数は一意に定まり、 $A_{i}$ をソートしておくと、目標となる $x$ の倍数が同じ要素については連続して並んでくれます。
ということで、境界を二分探索やしゃくとりで求められれば、必要な操作回数が求まります。
$x$ の倍数のみ調べるので、全体で調べる回数は調和級数で収まります。

D - Pure Straight

はじめに嘘DPを書いていて時間をロスしました。
$dp[i][S] = i$ 番目が右端で、集合 $S$ に含まれる要素が $i$ 番目から順に左側にならぶように操作したときの操作回数の最小値、とします。ただし、 $i$ 番目までの要素のみを用います。このDPは、 $i$ 番目の要素を用いない場合
$dp[i][S] = dp[i-1][S] + |S|$ という遷移になります。
用いる場合、 $dp[i-1][S \setminus \{i\}]$ に、 $i$ 番目の要素を正しい位置へ移動するコストを足したもので更新させます。
これを、右側のみの要素のみで構築するパターンについてもどうようにDPで計算します。
最後に、両方のパターンをマージして、ちょうど $S$ が全体になるようなものを計算し、答えを求めればOKです。

2021-09-12

精進メモ 2021/09/06~

精進記

Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma
ICPC Central Russia Regional Contest (CRRC 18)
ABC218
AOJ-ICPC

Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma

suzuken君に投げられました。最初の実装に15分、そこからバグを取るのに15分でした。
セグ木に必要な要素をのせてがんばります。
答え、左端の値、右端の値、左端から続く広義単調増加な列の長さ、右端から続く広義単調増加な列の長さ、全体が単調増加かどうかのフラグ
を持たせると計算できます。
[1,2,3,4]と[5,6,1,2]をマージする場合に注意。

ICPC Central Russia Regional Contest (CRRC 18)

難読問題セットでした。つらい。

B. Gremlins attack!

通れるようになる家を順にUnionfindで繋いでいき、端とグレムリンの家が連結になるまで繰り返します。

全探索すればいいのですが、OEISが見つかったので埋め込みです。
多倍長が必要なのでpythonでした。

E. Hanoi Tower

愚直にシミュレートすればOKです。実はもっと簡単らしいです。

H. A self-describing sequence

他のチームは最近既出で秒殺だったらしいです。問題文が読めず無限に時間が溶けました。
7以上は似たような構築方法でいけるので、6までは埋め込みです。

J. R u really ready?

$dp[i][j$ = p]の $i$ 文字目、 $t$ の $j$ 文字目でちょうど終わりになるようなパターンの適用方法があるか？でDPしました。バチャ込みで現時点FAっぽいです。

ABC218

最近2桁順位が安定している気がします。対してARCは…
Aでななめよみした問題文が全然違うものになっており1ペナしました。
相変わらずHは解けません。

C - Shapes

一番難しいです。90度回転の関数を作って、チェック→回転→チェック…と4回繰り返します。
チェックは、左上の位置をS,Tそれぞれメモして、そこからチェックします。
左上の位置から右下方向だけ見てしまい、サンプルがずっとあっていませんでした(サンプル1のようなケースで落ちます)

D - Rectangles

縦の直線を全部作り、そこから数を数えました。
直線の端点のy座標のペアごとに個数を数え、そこから2つ選ぶパターンを答えに追加すればOKです。

E - Destruction

基本的に最小全域木を行い、使わなかったコストの総和が答えです。コストが負の辺は全て繋いでおきます。残りはコストの昇順に辺を見ていきます。

F - Blocked Roads

全ての辺が使える状態での距離を求めます。距離は $N-1$ 以下になっているはずです。つまり、最初の状態でのルートに含まれる辺を取り除く場合のみ、愚直にBFSで最短距離を計算すれば良いです。面白かったです。

G - Game on Tree 2

最小値、最大値を選ぶパートはよくあるゲームの木DPと同じです。
中央値は、値を座圧し、BIT上で二分探索することで求められます。

AOJ-ICPC

1401 Estimating the Flood Risk

これ難しかったです…(本番、自分担当にならなくてよかった)
すでに決まっている位置の値に対し、全てのマスについて、Manhattan距離を足し引きしたものをメモすることで、それぞれのマスでの上限と下限が求まります。
あとは下限を全て足すと答えです。

2783 Parentheses

()()()...の状態から一番右側にある開き括弧を動かしていくと辞書順最小のものが作成できます。
それぞれの長さで作れる最大値は決まっているので、長さを決めた後は、答えと一致するように移動させればOKです。

2723 Surface Area of Cubes

外側の表面積を足します。その後、6×抜く個数を足しておきます。
ここから、余分に足した値を引いていきます。まずは、元々外側にある立方体を抜くケースで、これは表面に存在する面×2を引きます。
そして、抜く立方体同士が接している場所で、ここも接している箇所×2を引けばよいです。

2684 RLE Replacement

2乗が通るので、愚直に一致する箇所を調べ、置換すれば良いです。
置換元の文字が1種類の場合に注意です(この場合、置換前の文字列の長さが長い時は置換先の文字列より後ろに残ります)。

2599 Idempotent Filter

19個のマスの01パターンを全て試し、2回適用することを愚直にシミュレートします。

2857 Tournament Chart

構文解析です。形がかなり決まっているので、実装はかなり軽いです。
優勝者の勝利回数チェックが抜けており1ペナしました。

2858 Prime-Factor Prime

2から順番に、 $[l,r]$ で割れる場所を割っていきます。 $\sqrt{r}$ の素数まで見ればOKです。
素因数の倍数だけきちんと見るようにすれば、調和級数により $O(N \log N)$ で収まります(長さが $N$ )。
残った数が1より大きければ素因数をもう一つ足し、あとは問題の条件に合ってるかどうか判定していけばいいです。
難しかったですが面白いですね。

2913 Prime Routing

それぞれの頂点に偶数距離で到着する場合と奇数距離で到着する場合の最小値を両方メモします。
偶数距離が2であれば答えは2ですし、そうでなければ、奇数距離以上の最小の素数が答えです。

2021-09-05

精進メモ 2021/08/30~

精進記

AOJ-ICPC、一進一退です。負けません(今突き放されていますが…)。

AOJ-ICPC
ABC217

AOJ-ICPC

2303 Marathon Match

$i$ が $x_{i}$ 回休憩をしたときに優勝する確率を、全ての $(i,x_{i})$ について計算すればよいです。
それぞれが $x_{i}$ 回休憩するときの確率は、二項係数を使って求められます。
そして、そのときに $j$ に勝つために行える $x_{j}$ の最大値も求められます( $x_{j}$ を全探索してもOKです)。
あとは、自分以外の全員に対して勝つ確率を計算して、総和を求めればOKです。

2156 Magic Slayer

AllとSingleでそれぞれ、

$dp[i] = i$ だけダメージを与えるために必要なMPの最小値

を計算してあげます。あとは、Allで与えるダメージを固定したときに必要なSingleのMPの総和を計算してあげて答えを求めればよいです。

2534 Dictionary

まずは、接頭辞になっている文字列が後ろに来ている、サンプルの2つ目のケースを潰しておきます。
あとは、文字の種類ごとにどちらが前に来るべきかをメモして、矛盾がないかをチェックすれば良いです。

2177 Champernowne Constant

よくある問題です。
二分探索でスタートする位置を決めて、あとは適当にシミュレートします。

1379 Parallel Lines

傾きで直線を管理します。3点が同一直線上にないので楽に処理できます。
傾きごとに、その直線の部分集合を取った時の、点の集合に対するペアの個数を求めておきます。
あとは、点の集合に対するペアの個数をbitDPでマージしていけば良いです。

1400 Fast Forwarding

ICPC2019の横浜で解いた問題ですが、なんとコードをなくしました。
maxでどの速度にするか、を全部試します。
最低限必須な時間はあらかじめ除外して、残った部分を3進数で計算すればいいです。

ABC217

弊学top2の2人に一生勝てません。

D - Cutting Woods

setに入れて、set上の二分探索をすればOKです。

E - Sorting Queries

一瞬？となったので飛ばしましたが、帰ってきて冷静になるとすぐに解けました。
queue + priority_queueでいいですが、コンテスト中は何故かdeque + mapでやっています。~~やっぱり焦っていそうですね~~

F - Make Pair

操作を後ろからみると区間DPできる、というのはどこか別のところでも見た気がします。
区間を二つに分断し、それぞれでの操作をコンビネーションを使って並べていけば良いです。
境界回りがちょっと面倒でバグらせました。

G - Groups

$\mod M$ ごとにまず個数を数えます。
すると、 $dp[i][j] = i$ 番目のグループまで見て、 $j$ 個のグループになるようなパターン数
というDPをすると、二乗の木DPのような形で計算量が $O(N^{2})$ で収まります。それぞれのグループで番号が一番若い人を目印にして重複をなくすのがポイントでした。
もしかしてこの解き方少ないですか？あまり見なかった気がします。

H - Snuketoon

コンテスト翌日にSlope Trickを履修すると、「そのまんまだ…」となりました。
時間の移動はシフト、ダメージはそのまま加算をすればOKです。後ろから見て、最後に原点の値を見てあげれば答えです。

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

AOJ-ICPC

2170 Marked Ancestor

2224 Save your cats

1318 Long Distance Taxi

1244 Molecular Formula

Educational Codeforces Round 114 E. Coloring

Aizu Competitive Programming Camp 2021 Day 1

E: ヘクト問題

F: SからTを作るやつ

G: Round Tour

H: TUAT文字列

Aizu Competitive Programming Camp 2021 Day 2

B I am sleepy

D WeightedLIS

G Tree Propagation

K All Clear

ARC127

A - Leading 1s

B - Ternary Strings

C - Binary Strings

Aizu Competitive Programming Camp 2021 Day 3

B: Sufficient Condition

C: Separate Number

D: Successive Tree

E: +- Switch

F: A2B

G: XOR Walk

ABC220

C - Long Sequence

D - FG operation

E - Distance on Large Perfect Binary Tree

F - Distance Sums 2

G - Isosceles Trapezium

AOJ-ICPC

1399 Sixth Sense

1337 Count the Regions

Northern Eurasia Finals Online 2020

Geometrical Combinatorics

A. Almost Balanced Tree

Lookup Performance

ABC219

D - Strange Lunchbox

E - Moat

F - Cleaning Robot

ARC126

A - Make 10

B - Cross-free Matching

C - Maximize GCD

D - Pure Straight

Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma

ICPC Central Russia Regional Contest (CRRC 18)

B. Gremlins attack!

D. We were trying to share an orange ...

E. Hanoi Tower

H. A self-describing sequence

J. R u really ready?

ABC218

C - Shapes

D - Rectangles

E - Destruction

F - Blocked Roads

G - Game on Tree 2

AOJ-ICPC

1401 Estimating the Flood Risk

2783 Parentheses

2723 Surface Area of Cubes

2684 RLE Replacement

2599 Idempotent Filter

2857 Tournament Chart

2858 Prime-Factor Prime

2913 Prime Routing

AOJ-ICPC

2303 Marathon Match

2156 Magic Slayer

2534 Dictionary

2177 Champernowne Constant

1379 Parallel Lines

1400 Fast Forwarding

ABC217

D - Cutting Woods