ロアちゃんかわいい

競プロっぽい話がなされる駄文の掃きだめ

祝、ABC初全完(えらいです)

おはようございます。全完と申します。

しばらくぶりの更新のようですが、ちょうどゴールデンウィークですのでまあ気のせいみたいなもんです。

前回のABC148で念願の全完を果たしたので喜んでいます。

簡単でも何でも構わん、ぼくはついにやったのだ。こるぼーは偉いですから、えらい新生物とお呼びください。

F問題は特に最近の練習の成果が出ている感じがして嬉しい。考察も一応論理的にできたのでこの調子で進めたい。

まあ簡単だったというのは流石に分かっていて、difficultyを見ているとF問題ですら水diffのようです。あまり調子に乗るべきではないですね。


以下解いた時の思考。

A問題。
普通にforとifでいける。排他的論理和でも行ける気がするけど不要な冒険は避けよう。

B問題。
stringの変数を三つ用意します。うち二つに入力し、一つには空文字列を入れておきます。
後は一文字ずつ空文字列へ放り込んでいきます。おわり。

C問題。
最小公倍数が必要十分になってるね。実装しちゃお。AとBの積をgcd(A,B)で割ればええやんな!
あれ、なんで答え違うんだ、えっgcd壊れとるやんけ!うわあああ!!!たすけて!!!!おぎゃー!!!!
いいよgcd程度この場で実装するよ!オラァ!おわり!ばぶ~……(焦った……)

D問題。
なんだお前!と思ったけど消えた後の数列を想定すれば簡単やな。おわり。
(あとでスターリンソートだというコメントを見て爆笑していました)

E問題。
うわあああああ!!!!うわあああああ!!!!なんだこの関数みたいなやつ!!!!!うわあああああ!!!!!
数学の暴力しちゃうか!!!!よく分からん漸化式は展開!おっこれ二重階乗やな!!!うわあああああ!!!!
困った!!!!階乗なら典型だけど無理やんけこれ!!!!!うわああああ!!!!
なんだこれ!!!!アッ奇数の時は0!!!!うわああああ!!!!!
偶数限定だからn=2kやな!!!!オラァ分からん時はとりあえず式変形じゃ!!!!オラァ!!!!
あっこれn!! = (2**k)(k!)やな!!!!心の中のロアちゃん「えし!帰着でよ~」よしそうか!!(n/2)! でp=5についてLegendreの定理ィ!!!!おわり~。

F問題。
なんかこんな感じの解いたことあるな。距離をd[]で置いてみるか。おっこれ青木君と高橋君からの各点までの距離がわかれば勝ちか?
青木君より高橋君に近い点なら高橋君が到着出来て、逆にそうでなければ必ず青木君に邪魔されちゃうな!!!!という事はどんどん詰めると青木君は一回で目標の頂点まで移動することで上手くいく!!!!よっしゃあ!!!!終わり!!!!

たしかこんな感じでした。後半になると思考が散乱します。大変。


折角なのでF問題に関連してdfs(ついでにbfsも)を使う問題を列挙して、それらを復習して終わることにします。

next_permutationとかいうのよくわからんから使いたくない。そんなわけでdfsを利用。
D - joisino's travel

解説を読んで「こんな天才解法で解きたくないよ~~」って泣いてたらbfs解法が降りてきた。
bfsは各辺の長さが1の木における最短経路を求める時に使える。
ので、適当な問題に木の構造を見出すことができたら(ちなみに大体ここがボトルネックです)上手く実装出来るかもしれない。
C - Strange Bank

みんな大好き何とか門松。なんやお前、しばくぞ
C - Synthetic Kadomatsu

ここからはグラフに対してdfsを使う問題。

いつぞやのD問題。dfsに上手く適当な機能を付けていく感じ。
変数を持ってなんやかんやみたいなのも慣れてきたか?
D - Coloring Edges on Tree]

今回のF問題。考察パートが一番の本題で、ここを勘で通してた人もかなり多いっぽい?
厳密な証明はよくわからない。
F - Playing Tag on Tree

今回のF問題の類題。バチャでやっといてよかった。適切に記号を使って考察するのは大事。
木の二頂点からそれぞれ出発し、ある頂点へ向かう時、そこまでの距離が短い方が先に到着する。
従って同時に出発した場合、先回りすることが出来る。よって通せんぼ可能。
D - Fennec VS. Snuke

以上。後で追加するかもしれません。

何となく、グラフにdfsを使う時はdfsを使うことがすぐにわかるので比較的簡単で、それ以外は構造的にdfsで解けることを見切る方が難しい気がしています。

ではおやすみなさい。