Entries

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

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

コメント

[C24]

今頃気が付きましたΣ
実はO(1)のソースは書かないで置けばみんな書きたがるだろう作戦だったんですけど誰も組んでくれないーって思ってたらこんなところにっ
あと変数が酷いwwww

ちょっとでも見落としあると0点になっちゃうTopCoderでこれやっちゃうのはちょっと怖いですよね
考えないといけないって部分には全面的に同意しますので、是非是非そういうのが必要になるMarathon Matchのほうを(ry
  • 2009-09-13 14:50
  • chokudai
  • URL
  • 編集

[C25]

SRM的には,制限時間に間に合う中で,最も愚直かつシンプルなアルゴリズムを書くのが正解ですね.
Marathonは参加したいなーとは思いつつ,面倒になったり,途中で飽きたり,上位陣と才能の差を感じて絶望したり….
  • 2009-09-14 12:32
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

SRM443 DIV1 MEDIUM - BinaryFlips (この記事を編集する[管理者用])

あの超有名人のchokudai先生書いた記事の反応が少ないとか嘆いているらしいのでソースコード(C++)張り付けておく.
元記事の方針3の
このコードではループを使って最小のものを求めていますが、これは直接解くことも可能です。
というのを愚直に実装しただけです.
本番で,BFSは区間でやれば大丈夫ってのになるほどと感心したんだけど,それは良いとして,普通に不等式解けるじゃんとか言われてなるほどとか思ってるのはいけないなぁ….
計算時間を見積もって大丈夫なら,それ以上考えないTopCoder脳は時に駄目だと思う.
ICPC形式のコンテストのときは結構考えるのにね.
#include<vector>
#include<iostream>
#include<sstream>
#include<climits>
using namespace std;

// THIS IS O(1) TIME SOLUTION!!

class BinaryFlips {
public:
int minimalMoves(int A, int B, int K) {
  int myonmyon=INT_MAX;

  if(A==0) return 0;
  if(A==K) return 1;
  if(K>=A+B || (A%2 && K%2==0)) return -1;

  if(A%2==0){
    int chota = (3*A+2*B-2*K-1)/(A+B-K)/2;
    int shota = (A+2*K-1)/K/2;
    myonmyon = min(myonmyon,2*max(chota,shota));
  }

  if(K%2==0 || A%2){
    int chota = (3*A+4*B-3*K-1)/(A+B-K)/2;
    int shota = (A+3*K-1)/K/2;
    myonmyon = min(myonmyon,2*max(chota,shota)-1);
  }

  return myonmyon;
}

コメント

[C24]

今頃気が付きましたΣ
実はO(1)のソースは書かないで置けばみんな書きたがるだろう作戦だったんですけど誰も組んでくれないーって思ってたらこんなところにっ
あと変数が酷いwwww

ちょっとでも見落としあると0点になっちゃうTopCoderでこれやっちゃうのはちょっと怖いですよね
考えないといけないって部分には全面的に同意しますので、是非是非そういうのが必要になるMarathon Matchのほうを(ry
  • 2009-09-13 14:50
  • chokudai
  • URL
  • 編集

[C25]

SRM的には,制限時間に間に合う中で,最も愚直かつシンプルなアルゴリズムを書くのが正解ですね.
Marathonは参加したいなーとは思いつつ,面倒になったり,途中で飽きたり,上位陣と才能の差を感じて絶望したり….
  • 2009-09-14 12:32
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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