/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210919] AtCoder Regular Contest 126



2021年09月19日 (日)

最終更新: 2021-09-23T19:26+0900

[AtCoder] AtCoder Regular Contest 126

昨日の ABC に続いて今日は ARC があった。

昨日と同じく ABC の3完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの?どうなの?)

 A 問題 Make 10

脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785

 B 問題 Cross-free Matching

LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。

LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02

LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。

 C 問題 Maximize GCD

最初にサンプルの3にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。

次に GCD について。砂で隙間を埋めるように1ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか?

  1. 考えてる途中でなぜか +1 の他に -1 の操作もできるつもりになっていて WA>提出 #25992664
  2. -1 の操作に対応した部分を削除して AC>提出 #25993948 (1248 ms)。
  3. C 問題も B 問題同様、制約と入力がガチガチに厳しくないのに助けられている。余分な log を削って 943 ms>提出 #26017330

どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が2×N になってもオーダーは変わらないけど、ループを2本に増やすことに無意識の抵抗があるらしい。

 D 問題 Pure Straight

残っていた 20 分で愚直解だけ>提出 #25995534

RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。