ロコリンの雑記

アニメ大好き会社員のロコリンのブログ。2015年卒(修士)の社会人。学生時代(2010年)から続けてるブログなのでエントリによっては学生ブログと社会人ブログになっています。時系列から察して。
 
 
このブログについて
ブログ内検索
カテゴリ
プロフィール

ロコリン

Author:ロコリン
2017年4月から会社員。2015年3月まで大学院生でした。
趣味:アニメ/Twitter/ゲーム
今(2015年2月更新):プリキュア/プリパラ/アイカツ/ごちうさ/艦これ

外部リンク
Twitter

スポンサーサイト 

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

17歳だよ?!進数変換祭り!! 

NPCA Judge #59: 17歳だよ?!進数変換祭り!!」を見て思わず作りました。

実年齢:

理想年齢:

進数:

C++ 版は Gist へどうぞ。

追記 (2013年8月6日)

問題の作者様よりご指摘をいただいて,私の最初の実装だと計算に時間がかかることがわかりました。

なので,ちょっと修正しました。候補となる進数を線形探索(総当たり)で探すのではなく,2分探索で探すように変更しました。これによって時間計算量が O(n) から O(log(n)) に減りました。

(なお,2分探索法は単調関数に対して使える手法です。正直,単調性の証明をしないまま直感で2分探索法を使いました。)

もっといいアルゴリズムもあるのかもしれませんが,私は O(n) から O(log(n)) になっただけで満足です。

さらに追記 (2013年8月6日)

まだ間違いがあるみたいです。確認したところ,桁数が多くなるとオーバーフローしてしまう不具合が残っています。申し訳ありませんが,修正はしばらくの間保留ということにします。

スポンサーサイト
コメント
ありがとうございます
問題の作者です。早速のネタ化ありがとうございます。

失礼ですが、C++版って実際の問題を解こうと思って作られましたか?
提出してみるとわかりますが、そのコードではおそらくTLEになります。
Re: ありがとうございます
(´,,•ω•,,`)はわわっ,作者さんですか?!

(๑´╹‸╹`๑)お恥ずかしいコードを見せてしまって申し訳ありません。

(๑´╹‸╹`๑)提出はしていないですが,やはり私のコードだと計算量が多くなってしまうんですね...

ヾ(๑╹◡╹)ノ"機会があればもっといいアルゴリズムを考えます!

ヾ(๑╹◡╹)ノ"アドバイスありがとうございました!
残念
C++版 Revisions 6ですが、
実際の問題ではWrong Answerとなることをお伝えしておきます。
本当に問題を解きたければ、もう少し考えてみてください。
Re: 残念
間違っていましたか。゚(゚∩´﹏`∩゚)゚。

確認したところ,桁数が多くなるとオーバーフローしてしまう不具合が見つかりました。
これを直すには私の実力だと非常に時間がかかる(またはできない)と思われるため,大変申し訳ありませんが修正は保留とさせていただきます。
面白い問題なのでいつの日か再挑戦したいと思います。

この度はご確認およびご助言を賜りありがとうございました。














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

トラックバック
 
http://rexpit.blog29.fc2.com/tb.php/119-c9af506a
最新記事
最新コメント
FC2カウンタ
やりたいゲーム

艦これはやってる

神姫PROJECT かんぱに☆ガールズ オンラインゲーム ロードオブワルキューレ オンラインゲーム
欲しい
最近買ったもの
Amazon 検索
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。