Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1139-edc8473e
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 6408 - Counting Triangles 2 [KKKCT2] (この記事を編集する[管理者用])

Source

SPOJ 6408 [KKKCT2]

問題概要

左下と右上が(0,0), (x,y)の格子点から3点選んで,直角二等辺三角形を作る方法の数 mod 2009を求める問題.
xとyは10000以下.

解法

直角二等辺三角形の形は(0,0), (a,b), (a-b,a+b)と書けて,その幅と高さによってその三角形が置ける個数が求める.
aとbを全部確かめるとO(xy)でできるが,これだとTLE.(SPOJ 5464 [CT]はこれで通る, ブログ記事)
aを固定したとき,サムメーションを計算するとO(1)で三角形の数がわかり,結果的にO(x+y)で解ける.
ちなみに,最大ケースでも答えは63bitに収まるので,最後にmod 2009を取るだけで良い.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1139-edc8473e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。