ARC124

2完。全部難しい。最近調子悪いというのもあるが、惜しいところまで行かないんだよね。「混乱して何もわからなくなった」まで行かない。どうすりゃいいんだ。そういえば心拍数もあまり上がらなかった。

A - LR Constraints

趣旨がわからないので、力ずくで解く。問題の変数名でKとkがあるだけでも嫌なのに、意味が似てなくてかなり嫌な気持ちになった。

B - XOR Matching 2

何もとっかかりがない。Cと交互に考える。だいぶ経って、xの候補をN通りに絞れることに気づいた。Bをソートしておく。候補とAのxorをとり、ソートしてBと比較。

uniqueし忘れで1WA。順位表でペナが多いのを見てかなり見直ししたのにわからなかった。気づく方法がない。

C - LCM of GCDs

タイプの違うものをまとめるように分けたいよね。何もわからない。制約も意味がわからないし。半分全列挙は考えたけど何もできない。となると約数全列挙みたいな方向になりそうだが、答えを決め打ったところで袋は2つあるんで無理(片方で最大公約数3を達成してねと言われたらできるが、もう片方で何を達成したいか色々考えられる)。試しに gcd{ lcm(A_i, B_i) } みたいの計算してみたけど、答えはこれ以下になるのかな。一般論として「最大値の最小値」と「最小値の最大値」の関係とかも自分は全然わからないし、となると何かを考えるという風にならない。何もできなかった。

D - Yet Another Sorting Problem

答えはO(N+M)になりそう。N側とM側に分けて、片方の3か所だけ違ってるとか色々なパターンを考える。その数があるべき場所へ移動していってループを検出するという方針に気づいたのがだいぶ遅かった。ループが長くてN側とM側両方あって交互ではないときがわからない。考えるべきパターンが多すぎて、現実的に解ける問題に見えない。