[AtCoder 参加感想] 2019/04/27:ABC125

  A B C D    
問題文    
自分の提出    
結果 AC AC AC AC    
スポンサーリンク

全体感想

初参加!23分で全問正解。

問題Dから考え始めたのですが、かなり簡単でやや拍子抜け。問題Cが少し難しかったです。
それなりにミスなく乗り切れたと思ったのですが、3桁順位。やり込み層は本当に速いですね。

問題C – GCD on Blackboard

1元を除いて$\mathrm{gcd}$を計算する問題。当然、個別の計算でループ回すと$O(N^2)$でダメです。事前計算を使って、個々の$\gcd$の計算を軽くすることを考えます。

初めはsegment木を考えました。区間内の$\mathrm{gcd}$を計算していきたいので、自然な解法だと思います。この時点で「解けた」という気持ちにはなりました。segment木を迷わず実装する自信はないので、ノートに実例を書き出しながら、一旦他の問題に移りました。

問題Dが物凄く簡単だったことも合わせて、「本当にそんな難しいことさせるのかなぁ?」と思い、もう少し考えます。よく考えると、$[0,x)$や$(x,N-1]$の形の区間しか計算する必要がありません。そのような区間に対する事前計算の方法を考えると、左右からの累積$\mathrm{gcd}$を計算しておくだけで良かったです。

(後日考えたこと)
「左右からの累積」という発想は、
集合$S$があり、各$s\in S$ごとに部分集合$S\setminus\{s\}$を考察する必要がある場合
に使える場合がある、と一般化しておくと良さそう?他に過去問で一度同じ発想を経験しました。

問題D – Flipping Signs

やたらと簡単です。操作に回数の制限も特にないので、たいていのものを正に変更できます。
唯一、全ての要素の積が定符号という条件があるだけです。

Dは、「考察が必要」「考察すれば易しい」ような問題が多めなのか、あるいは今回だけなのか。
$0$は存在する場合などで正しく実装出来ているかを慎重に確認しながら提出。

コメント

  1. […] 4/24:AtCoderで初めて問題を解く。4/27:ABCコンテストに初参戦。 […]

  2. Thank you, I have just been searching for information about this subject for ages and yours is the greatest I have discovered so far. But, what about the conclusion? Are you sure about the source?

  3. At the very center of your being you have the power; you understand who you are and you know what you must do.

  4. hello!,I really like your writing so a lot! percentage we keep up a correspondence extra approximately your post on AOL? I need a specialist on this space to solve my problem. May be that’s you! Taking a look forward to peer you.

  5. I’ve been absent for some time, but now I remember why I used to love this website. Thanks, I will try and check back more often. How frequently you update your web site?

  6. Perfect piece of work you have done, this internet site is really cool with good information.

タイトルとURLをコピーしました