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つのみの木を構成するペアおよびその他のノード全てとつながっているノードのペアを探せ,ということですね.


反省点

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

教訓

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

TopCoder SRM534 Div2 反省

| 23:39 | TopCoder SRM534 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM534 Div2 反省 - iwbtr - kmats TopCoder SRM534 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 282/943

Points: 353.65

Solved:oo-

Challenge: 1 failed

Rating: 940 -> 964 (+24)


250で許されざる時間ロス&チャレンジ失敗.何とか500を通したものの,その500も糞コードすぎて解いた気がしない・・

20分後のCodeforcesも頑張ります.


534 Div2 250

ただイテレータスワップするだけ.するだけだったのだが・・


後ろ2つが"."か".."であることを確認するために

vector<string>::iterator it = files.end();
advance(it, -1);

等とするところを,

it = advance(it, -1);

としてたorzorzorz


一発で解けなかった時点で半分パニック状態に陥り,大幅に時間ロスしてしまった・・

イテレータの基本的な使い方を復習しないと・・


どう見ても撃墜できるだろう,という回答が一つあったのに弾かれた.

Codeforcesが終わってから要確認.


534 Div2 500

"o"マーク(checker)を左から右に移動させていき,移動できなくなった方が負けるゲーム.

対戦形式のゲームなのでミニマックス法的な考え方が必要なのかと思いきや,今回は特に各プレイヤーの最適解を考える必要はなく,操作する人が一人だけと考えてしまって良い.

  1. 最も左のチェッカーを操作対象として選ぶ
  2. 右端に到達するか,他のチェッカーが邪魔で移動できなくなるまで移動させる
  3. まだチェッカーが残っていれば1に戻る
  4. 全てのチェッカーを移動し終わったら,操作回数の偶奇で勝利プレイヤーを判定する.

またもや実装しながら考えていたため,二度と見たくないような糞コード爆誕.

なぜか2度もチャレンジされてた.


534 Div2 1000

ちらっと問題文を読むも,解いた人がほとんどいなかったため投げた.

結果的に0%..


反省点

  • イテレータの扱い方を忘れていた
  • 考えながら実装した

教訓

  • 基礎的な文法やアルゴリズムを復習すべし
  • せめて大まかな方針を固めてから実装し始める