ツバサの備忘録

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

ICPC2021模擬国内 参加記

番外編 ICPC

公式link
suzuken君と、bayashiko君とチーム"MSB"で出場しました。
ブログを書くのが久々で緊張しています。

day 0

ポケモンユナイトにハマりました。同じICPCに別のチームで出ているすず君と毎晩のようにプレイしており、一時期は5000位くらいでした。
今はレート1409で7000位くらいです。
8～9月はAOJ-ICPCを埋めて、精進メモを毎週書いていたのですが、突如モチベがぷつりと切れてしまい、後輩にばかすか抜かれました。残念。

本番

初手はばやしこくんがA、すずけんくんがB、僕がCを読みました。
僕がCを読んで†実装問題†だとわかった瞬間、一昨年の国内予選本番で実装をバグらせた記憶が蘇りました。これは誰かに実装を押し付けるしかない！と思い、すぐさまＤを読みました。
Ｄもパッと見でわからず(2乗なら通るのになぁ～って言ってました、はやく書けばよかったです)、すずけんくんにBのヘルプを求められたので、考察の手伝いをしました。
そうこうしている間にばやしこくんがAを通しました。


ばやしこくんの手が空いたので、すかさずCを押し付けます。ばやしこくんは実装系が一番苦手ですが、ここはやむなし。心を鬼にして譲ります。
僕はEを読み、ぱっと見でわからなかったため、Dへ戻りました。その間に、Bが通りました。


しばらくしてCも通ります。D問題を僕とすずけん君で考え、2乗が通るじゃん、という話になったため、僕が実装を開始します。
すると、数分後、ばやしこ君がこう言いました。
「Eのサンプルあったので投げます」
何かの言い間違いだろうと思い、笑ってごまかしました。念のため、
「どういう解法なの？」
と聞きます。すると、
「転倒数とLIS組み合わせたらサンプル合いました」
と言います。どうやら本当らしいです。
さすがに嘘でしょ、とゲラゲラ笑いながらDを実装していましたが、数分後、
「一つ目のケース通りました」
と言われました。もう何も信用できなくなりました。
結局、僕がDを通すより20分もはやく、Eが通りました。わけがわかりません。


僕が盛大にバグらせてひいひい言いながらDを通した後、3人でFとGを交互に考えます。僕はFをほとんど考えずGに突っ込んでいました(大失敗)。
すずけんくんがFでとりあえず適当なDPを書くと言っていたので投げました。
実装が終わるも、WAが出ます。
さすがに僕もFを考えよう、と思い、10秒くらい見つめると、なんと解法がすぐに降りてきて叫びました。

「これ、区間DPじゃん！ｗ」

嘘でした。
3分間くらい、チームメイトからすごい、天才、さすがです、とすごく褒められていたので申し訳ない気持ちになりました。
冷静になり考え直して、しっかり正しい解法を出しました。
すずけん君に伝えた後、僕も暇なので、昨年の国内予選優勝チームを真似て、どちらがはやくACできるか勝負することにしました。

負けました。


この時点で2時間たっていました。まだ1時間ありますが、Ｇ問題が不可能にしか見えなかったため、Fのデバッグをずっとしていました(1行変えれば通りました)。
その後は、三人で一生感想戦をしたり、Dの線形解を考えたりしていました。
今回はばやしこくんの大活躍のおかげでライバルチームに圧勝したかな、と思っていましたが、結局皆完数で並びました。 他のチームは完全体でないチームもあったため、かなり驚きました。

結果

15位でした。コンテスト中は16位と書いてありましたが、なぜかあがっています。

おわり

去年、模擬国内で16位を取ってから予選に落ちました。
今年は、昨年のチームメイトであるるぎうさん、とまとさんがコーチをしてくださっています。直々に頑張ってとも言われたので、今年はきちんと国内予選を勝ち抜きたいと思います。
頑張ります。

p.s. 本番で大学へ行く予定なので、ラーメンを食べるのが楽しみです。

精進メモ 2021/10/04~

精進記

書き忘れてました。

MojaCoder Random Xor Division

リンク
O(N^{2})が想定っぽい？ですが、O(N \log A_{i})で解けました。
ビットごとに見ます。すると、累積和の偶奇で右端を固定したときの相方の候補が出せます。
数日前のABC-E問題同様、2の冪乗の累積和を計算して、右端より右側で自由に切れる部分、左端より左側で自由に切れる部分のパターン数が計算できます。
あとは、ビットごとに上記を計算していき、総和を取って、全体のパターン数である2^{N-1}で割れば答えです。

ABC222

C - Swiss-System Tournament

毎回愚直に対戦させ、勝利数を計算してからソートしなおしていけばOKです。

D - Between Two Arrays

DPをいもすで高速化します。

E - Red and Blue Tree

辺ごとに通る回数をメモしてから、差が問題の条件を満たすようDPすればOKです。一回も通らないものは素直に2倍していきます。

F - Expensive Expense

全方位木DPです。
dp[v] = vを根とする部分木で、vからどこかへ観光しに行ったときにかかるコストの最大値、として計算します。

G - 222

離散対数問題のライブラリがバグっていてコンテスト中に通せませんでした。
漸化式の解き方をググって解くと、a_{i} = \frac{2}{9}(10^{i} - 1)という式が出てきます。
これがKの倍数になれば良いです。
少し変形すると、
2 \times 10^{i} \equiv 2 \mod{9K}
となります。
あとはこれを満たす最小のiを求めればOKです。

精進メモ 2021/09/27~

精進記

気温の変化にやられて一日中鼻かんでます。

AOJ-ICPC

2169 Colored Octahedra

素直に全探索します。
next_permutationで全列挙し、ひたすら回転させました。

2249 Road Construction

ダイクストラをしてから、近い順に最小全域木を計算していきます。

2178 Futon

隣接するマスを同一視して、二部グラフ判定します。
実装に少し困りました。

2302 On or Off

それぞれのマスで通る時刻はわかっているので、マスごとに計算すればよいです。
dp[i][j] = i回目に通った後、電気がオンになっている/オフになっている(j)ようなスイッチの切り替え方における最小コスト
と定義して計算していけばよいです。

2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

チーム練です。

D. Cycle String?

出てくる回数が最大のものがn以下であれば、適当にソートして出力でOKです。
そうでない場合、s_{n}とs_{2n}に最大のもの以外を置き、あとは前から回数最大のものを順に詰めていきます。
最大のもの以外が3個以上あるか、種類が3種類以上であれば問題の条件を満たします。
そうでない場合は構築できません。

E. Life Transfer

BITを7本くらい用意してごり押しました。
年齢の降順にソートして、車、バイク、乗客、の順で選んでいきます。
車を運転する人の人数を全探索していけばよいです。

F. Game on a Tree

ずるしました。
昔かっつくんが解いた時のツイートを皆で思い出してしまいました…
移動できる頂点に辺を張り直し、完全マッチングが存在すれば後手の勝ちです。
適当にDFSをして、葉から貪欲にマッチングさせて頂点があまるかチェックすればおしまいです。

ABC221

可もなく不可もなく。

C - Select Mul

2回誤読してコードを書きなおしました。
ビット全探索して降順ソートです。
leading zeroは無視してOKです(どちらにしろ答えが0になるので正しい答えが出ます)。

D - Online games

イベントソートして日付ごとに処理をしました。

E - LEQ

得意分野なので自分の体感難易度とまわりがズレていました。
数列の最初と最後を決めると、間の要素を任意に選ぶか選ばないか、になります。2の冪乗です。
i,jを決め打ったときの選び方は、累積積のようにしてO(1)で計算できます。
あとはBITで累積積をまとめて計算すればいいです。

F - Diameter set

直径の偶奇で場合分けをしました。
奇数距離の場合は、中心が2頂点に分かれます。それぞれの中心で木をわけたとき、それぞれで直径として選べる端点が計算できますが、2つの木のそれぞれから1つずつ選ぶしか方法がありません。
よって、それぞれの木の候補の数の積が答えです。
偶数距離の場合は、中心が1つになります。中心と隣接している頂点との辺で木を複数に分けたとき、先ほどと同様に直径として選ぶ候補がそれぞれの部分木で数えられます。それぞれの部分木から最大で1つ(0でもよい)頂点を選べるので、(個数 + 1)の漱石を計算します。
ここから、一つも選ばれないパターンと、一つだけ選ばれるパターンが条件を満たさないので引けば答えです。　　

精進メモ 2021/09/20~

精進記

もうすぐ秋学期が始まりますね。夏休み返して…

AOJ-ICPC

これまで通り下から埋めるか、星付きを優先するか悩みます。

2170 Marked Ancestor

後ろから見ると見通しがよくなるやつです。
クエリが起きたタイミングを管理して、葉からのぼりつつ処理します。
クエリが起きたタイミングが、今見ている頂点のマークされるタイミングよりも遅ければ、その頂点の値を加算します。そうでなければ親にまわします。
親に渡すパートはマージテクを使えばＯＫです。

2224 Save your cats

閉路がない = 木(森)である
ということが条件なので、コストの正負を反転してから最小全域木を作成していきます。使わなかった辺のコストの総和が答えです。

1318 Long Distance Taxi

燃料を補填できる都市同士を移動できるかどうかを、それぞれの都市を始点としたダイクストラで調べます。
その後、移動できる都市に辺を張りなおしたグラフで再びダイクストラすればいいです。

1244 Molecular Formula

頑張って構文解析します。
式全体は ()1 で囲んでるとすると実装が楽になるかも？しれません。

Educational Codeforces Round 114 E. Coloring

縦で見ると、黒白…と白黒…のどちらかを選択することになります。
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/13~

精進記

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

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チームメンバーが温まっているのでヨシとします。

f:id:emtubasa:20210918232050p:plain

D - Strange Lunchbox

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

E - Moat

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

1111
1001
1001
1111

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

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

精進記

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で繋いでいき、端とグレムリンの家が連結になるまで繰り返します。

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

全探索すればいいのですが、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/08/30~

精進記

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

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です。後ろから見て、最後に原点の値を見てあげれば答えです。