perarduaadastra

競技プログラミングとかをしています

AtCoder Beginner Contest 212 反省

8問制ABCだ!後ろに黄橙の問題が増えました(?)

 

結果を鑑みて

2100 96:11

Eまでそれなりのペースだったはずだが、周りが結構速くて相対的にはそんなに速くなかった。G通らなかったら冷えてたかも!ぴえ〜

 

A - Alloy

if文をせこせこ書く。

 

B - Weak Password

ふつうにやる。コーナーがないかちゃんと調べた。

 

C - Min Difference

AとBを出身の配列がわかるようにして混ぜて、ソートする。

そうすると隣り合った別配列どうしの2要素の差の最小値が答えとみて問題がない。

 

最近、隣り合う要素・頂点の関係を利用した数え上げ法が少し見えるようになってきたのでここまではすぐに見えた。

見えたものの、証明してみても抜けがあるかもしれないと少し怖かったので丁寧にサンプルを合わせてから通した。

 

このとき、サンプル合わせに加えて順位表も見て情報を得ようとしてみたが、今回はあまり参考にならなかった。

 

D - Querying Multiset 

クエリ先読み系かなと直感したが、ちゃんと読むとただの優先度付きキューの問題だった。

 

解けたので順位表を見ると100位ちょっとだった。さっさと解いて行った気がしていたので100位は切れると思っていたが......

 

E - Safety Journey

少し難儀した。愚直に遷移させてdpすると重すぎるし、ダブリングでもなさそう。

ちゃんと考えると余事象的に遷移を扱えばよいだけだった。全体の方針としては普通の数え上げで、途中途中の部分問題が余事象数え上げだったりすると見えるのに時間がかかる。

 

この時点で150位ちょっと?まあレートは落ちないだろうと思って安心して進むことができた。

なお、Eを解いた時点でFは問題だけ読んであった。

 

F - Greedy Takahashi

なんかDAGだったらDAG上ダブリングだな〜とか思っていた。なんだかよくわからんし順位表見ても全然解かれてない上にGの方が解かれていたのでGを見に行った。

 

 

G - Power Pair

かなり難儀した。最初はPの約数列挙をしようとしていた。(Pは素数です!)

約数列挙して、それぞれの循環の長さとかを計算したりして約数系包除しようとしていた。

だいたい正しいのだが、このときは x^n mod PはxとPが互いに素なら常に循環の長さ(位数)がP-1になると思っていた。

 

いろいろ実験するとそうでないことがわかって、位数という語を知り、位数にP-1の約数しか現れないことを悟った。P-1がフェルマー小定理と関わっている数字であることもわかっていた。

ここからさらに難航して残り20分になろうというあたりで原始根という語を知った。原始根を利用して「なぜ位数がP-1の倍数になるのか」に説明をつけられる気がして実験してみると、やっと残り10分というところで法則を見つけることができた。

 

なんとかこのままACできた。

公式解説にはさらっと原始根を利用したとんでもない式変形が載っているが、見つけた法則というのはつまるところこれだった。ひょっとしてこれも典型考察なのか......

 

H - Nim Counting

ちらっと見て包除かなあとか思ったけどKの値が奇妙すぎて???となった。すぐ見るのやめた。

 

総括

F飛ばしてGに行ったムーブだけでレートを手に入れたようなもの。結構ムーブはよかった。高度典型の知識不足がやはり目立つ。ARC・AGCでの勝率の低さはそこにありそう。黄〜橙埋めをやろうね。

そろそろ黄色に戻れるかな?(戻る、といっても黄色だったのはマジで1日だけだしほぼ青の住人......)