Hatena::Grouptopcoder

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

2012-01-12

Codeforces Round #102 (Div. 2) 反省

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

Rank: 625/1254

Score: 1152

Solved: 2 (A: 482, 00:09 / B: 670, 01:10)

Rating: 1450 -> 1418 (-32)


B問題時間かかりすぎわろた

Ratingは下がったものの,問題の出来自体は前回よりは若干マシ.

143A

適宜枝刈りしつつ全探索でおk.

4つのマスをそれぞれint w, x, y, zと置いて,1<= w,x,y,z <= 9で4重ループ.

このとき,w, x, y, zの値が重複したり,計算してもr1やc1に適合しない場合はループの途中でcontinue

正しい組合せが見つかった時点でcoutしてreturn.

144B

ただのimplementation.と思ったらコードが超汚くなったorz

何とか根性で解いた.

文字列を整数部と小数部に分けてそれぞれ処理,最後に一緒にcoutすれば良いことに気付いたのは終わってから.

systestで落ちなかっただけマシだけど,こういうところを手早く解いてC以降に取り掛かりたい.

144C

n = (A-1)*(B-2)*(C-2)を満たすときの,A*B*C-nの最大値および最小値を求める.

A-1 = i,B-2 = jと置いて,iとjの1<=i, j <= nの2重ループをするとn<=10^9故にTLEで死ぬ.

iはともかく,jは1<= j <= n/i でいいじゃんと思い,試してみてもやっぱりTLE

2重ループで解く場合は1 <= i <= sqrt(n),1 <= j <= sqrt(n/i)でいけばOKのようだけど,これはつまりえーと・・

nの因数としてのi, jはそれぞれnやn/2も考える必要があると思いきや,k = C-2の計算の際にi = 1, j = 1ならばk = n,i = 1, j = 2ならばk = n/2になるから,i, j ,kが等価(本当に?)であるn = i*j*kにおいてはiやjをn/2まで考える必要がない・・ということか?

素数判定の試し割りに出てくるのと同じ考え方かね.(nの因数を考えるとき,sqrt(n)より大きい数の因数が存在するならば,それより小さい因数も必ず存在するので,sqrt(n)まで考えれば良い)

143D

殆ど見てない.

Standingsを見るとCを解かずにDを解いている人もそこそこいた&pretestに通った人の数も割とCに近かったので,Cで手こずったらDを見るのもありか.

143E

見てない.

反省点

  • 分割して処理すべきデータを常にまとめて扱っていた
  • 数学的思考力が足りない

教訓

  • 一見同じデータに対する処理でも,別々の箇所に行う場合はデータを分割して処理後に統合する
  • 整数問題をこなす

2012-01-08

Codeforces Round #101 (Div. 2) 反省

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

Rank: 763/1262

Score: 482

Solved: 1 (A: 482, 9min)

Rating: Not Rated -> 1450 (Specialist, 緑)


1完\(^o^)/

緑になれたのはTopcoder同様初参加時のレーティングだけ高いというアレだと思うので,今後精進したい.


141A

26文字のアルファベットの数をそれぞれカウントし,前者2文字列と後者1文字列の場合で比べる.

・・が,なぜかvector< pair< string, int > >を使うという無駄な行為に出る.

9分で解けたからまだいいものの,これなら5分で解けた.

141B

ただのimplementation.と思ったらsystestで落ちたorz

でも上位陣も割と落ちてるという..

141C

色々考えたけれどいいのが思いつかず.要再チャレンジ.

141D

見てない.

141E

殆ど見てない.スパニングツリーということはプリム法かクラスカル法?


反省点

  • 実装に無駄が多い
  • 条件文がややこしくなって自爆する
  • Status Number (#)をクリックするとテストの詳細を見れることを知らなかったorz

教訓

  • 定石を覚えて実装の負担を減らす
  • 複雑な記述は多少時間を使ってでも修正する
  • テストに落ちたら詳細を確認して対応する