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

見てない.

反省点

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

教訓

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