AtCoder ABC142 参加記録
Dまでの4完だったが、Dを解くのに時間をかけすぎた。
反省するべき点はあるけれど、実装力と論理的思考力はそこそこの水準になってきていると思っているので、うっかりミスとかを減らしていくことでどこかで飛躍的にパフォをあげられる気もする。また、Dは時間はかかったとしてもだいたい解けるようになってきているので、400点問題の精進もしつつ、500点問題も挑戦していく必要がある。
A問題
N=1かそうでないかで分ける。奇数の個数はN>=2のとき、N/2の小数点切り上げしたものになるので、これをNで割れば奇数の確率が求まる。
B問題
これは数えるだけ。頭使わない分Aより簡単な気もする。
C問題
登校時点で教室にいた人数が自分含めてA[i]なので、order[A[i]-1] = i+1 なるorderを用意してあげるとよい。
D問題
AとBの共約数のリストを求める→素でない約数を消していく
の手順で解いた。約数のリスト作成でミスするという作問者も意図していないであろうところでつまってしまった。
pがAの約数であるとき、(A/p)もAの約数という処理を入れるのを忘れていた。
たぶんAとBを素因数分解してsetの論理積で共通の部分をとるのが楽かな?
素因数分解して集合の論理積をとる方法で解きなおしたら早い&スッキリしてミスもなくできた。やっぱり変に愚直に実装せず、スマートな解き方の方がいいよなぁなどと感じた。
E問題
解けなかった。どう考えてもDPだよなとは思ったけど、DPは基本的な奴しかまだ解けないのであきらめた。