2017-09

Latest Entries

スポンサーサイト

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

SRM 510 DIV 1

1000 から開き,残り 15 分で一旦 250 を解き,再び 1000 を解いて終了間際に提出したがすぐミスに気付いた.撃墜は 1 成功 1 失敗.
変数名に注意.

250: TheAlmostLuckyNumbersDivOne


a 以上 b 以下で,10 進法表記で桁に 4 と 7 以外は高々 1 回しか現れない整数の個数を求める.
1 <= a <= b <= 10^16.

すべて 4 か 7 なものが 2^17 個以下しかないのですべて数えても間に合う.再帰で書いた.

500: TheLuckyGameDivOne


10 進法表記で桁に 4 と 7 以外が現れない整数を lucky number という.
John は [a, b] に含まれる jLen 個の整数を含む区間を選び,その後 Brus は John の選んだ区間に含まれる bLen 個の整数を含む区間を選ぶ.この区間に含まれる lucky number の個数を,John は最大化しようとし Brus は最小化しようとする.結果含まれる個数を答える.
1 <= a <= b <= 10^10.

lucky number の個数 N は 2^11 個以下.Brus が選ぶ区間として考えるべきものは,John の区間の端にくっつけるか,[a, b] の端にくっつけるか,ある lucky number をぎりぎり含まない箇所.このうち最初の場合以外を,含まれる lucky number の個数とともに列挙する.John の選ぶ区間として考えるべきものは,[a, b] の端にくっつけるか,Brus の選びうる区間をぎりぎり含まない箇所.これらをすべて試すと O(N^2) となる.
区間の min を求めることになるので O(N log N) でも解ける.

l と r を 1 箇所間違えた.Brus の選ぶ区間の候補の数,の代わりに N と書いてしまった.

1000: TheLuckyBasesDivOne


10 進法表記で桁に 4 と 7 以外が現れない整数を lucky number という.
整数 n を B 進法 (B >= 2) で書いたとき桁に lucky number しか現れないような B の個数を求める.無限個あるならばそれを指摘.
1 <= n <= 10^16.

無限個あるのは n が lucky number であることと同値.さらに,そうでなければ B <= n.
n 以下の lucky number をすべて生成しておく.
B <= n < B^2 については,n = a[1] * B + a[0] とすると,a[1] < n^(1/2) かつ a[0] < n / a[1] を満たす lucky number a[1], a[0] をループで回してすべて試す.
B^2 <= n < B^3 については,n = a[2] * B^2 + a[1] * B + a[0] とすると,a[2] < n^(1/3) を満たす lucky number a[2] をループですべて回し,それらに対して (n / (a[2] + 1))^(1/2) < b <= (n / a[2])^(1/2) を満たす B をすべて試す.
B^3 <= n については,B <= n^(1/3) を満たす B をすべて試す.
これらを重複を生じないよう数える.返す型は long long となっているがすべて数えられる程度の個数しかない.
最大の実行時間は 900 ms 弱だった.

サンプルが弱く n < B^2 しか確認できない.
B^3 <= n について B の上限を n に依らない値に決め打ったが,B^2 <= n < B^3 に対して小さい B も数えてしまい,重複していた.また,B <= n < B^2 に対して a[1] と a[0] を回す変数 i と j を間違えた.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/29-4fe47d91

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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