Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-02-24

Codeforces Round #109 (Div. 2) 反省

| 03:04 | Codeforces Round #109 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #109 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #109 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 981/1284

Score: 492

Solved: ox-x-

Rating: 1451 -> 1383 (-68)


フルボッコキタ――(゚∀゚)――!!

の割には,あまり下がってない様子.

いずれにせよ,今回のDは勉強になりました.


155A

最大値・最小値が更新されたらcount++するだけ.

https://github.com/k-mats/codeforces/blob/master/150/155A.cpp


155B

a[n]とb[n]を用意しておき,b[i] > b[i+1]になるようにaとbをソート.b[i] == b[i+1]の場合は,a[i] > a[i+1]になるようにソート.

その後,i == 0から順にcount_b == 0になるまでcount_a += a[i], count_b += b[i]すればいいだけ.


が.実際に書いたソートが間違っていたカウントする際の処理を間違えていた/(^o^)\

SRM533 Div2 250のピカチュウの時もそうだったけれど,解法が思いついた状態でさっさと書いたコードの中にケアレスミスがあっても見つけようがないなあ・・

https://github.com/k-mats/codeforces/blob/master/150/155B.cpp


C (154A)

前から順に貪欲法で解いて死亡.

abbaaaのときはbを全て潰し,abbaaabbbbのようなときはaを全て潰す必要があることに気付いたのはCを飛ばしてDをsubmitしてから..


D (154B)

何も考えずon/offの状態を配列で保持し,二重ループするとO(10^10)になって死亡する.

ので,on状態のcolliderのみset<long> colsに保持し,offのリクエスト時にはcols.findしてoffを判断.

onのリクエスト時にも同様にcols.findし,無ければリクエストされた番号とcolsの中の番号をしらみつぶしにユークリッドの互除法.


で死亡.そりゃあいくらfindで計算量減らしても,ループの中で全探索やってりゃ結局O(10^10)になるわな・・


診断人さんの放送(http://com.nicovideo.jp/community/co78570)を見ていたら,”整数のペアを共に素因数分解し,同じ素数を持っていたら互いに素ではない”ということを利用すれば良いと知る.なるほど.


k番のリクエストが来たらk番と一緒にkの素因数もon状態と考えておけばユークリッドの互除法は必要なくなる.

更に,使用中の素因数を覚えておけば,k番を削除するときにも役立つ,と.


ついでに,整数が非常に多く出てきても,出てくる素因数はそんなに多くない,というのも有用な情報だと思った.


E (154C)

読んだだけで解いていないが,u, vを使ってる時点でグラフ問題だなあ,という感想.

ノードが2つのみの木を構成するペアおよびその他のノード全てとつながっているノードのペアを探せ,ということですね.


反省点

  • ”互いに素”に対してユークリッドの互除法しか対処法を知らなかった

教訓

  • "互いに素" = "共通する素因数を持たない"と言えるので,素因数分解が有効