Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-26SRM522 Div1

  • 250:188.32, 450:367.18(-25), 1000:Opened, score:530.50, rank:38, rating:2303(+56)
  • 450が比較的早かったので順位は結構良かったが250でバグったりチャレンジミスったり反省点の多い出来だった

SRM522 Div1 250 RowAndCoins

| 01:47 | SRM522 Div1 250 RowAndCoins - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM522 Div1 250 RowAndCoins - SRM diary(Sigmar) SRM522 Div1 250 RowAndCoins - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何も考えずbitメモ化再帰した。

10分弱で書けた

答えが全然合わない。なんで・・・

見なおしても分からない。やばい。あせる

ステップ実行してチェック。

メモ化の代入が逆になってる。memo[mask][d]=resとするところがres=memo[mask][d]となっている。合うわけない。

修正。提出。

10分も無駄にして随分低い点数を取ってしまった。。。痛すぎる。。。

こういう凡ミスがいつまで経ってもなくならない。どうしたもんだろう。


ソースコード

他の人を見ると左端か右端がAならAlice、それ以外ならBobでいいらしい。

それを思いついたとしても自分なら安全を見積もって結局メモ化で書いただろうな。。

続きを読む

SRM522 Div1 450 CorrectMultiplication

| 01:47 | SRM522 Div1 450 CorrectMultiplication - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM522 Div1 450 CorrectMultiplication - SRM diary(Sigmar) SRM522 Div1 450 CorrectMultiplication - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

あるA,B,Cについて元の値a,b,cからの合計距離を少なくすることを考えると、

A*B<cかつ(A+1)*B<=cのとき、Bが1以上であることを考慮するとC=A*BにするよりC=(A+1)*B、A=A+1にするほうがいい

(Aはaから1離れる可能性があるが、Cは確実にcに1以上近づくため)

同様にA*B>cかつ(A-1)*B>=cのとき、C=A*BよりC=(A-1)*B、A=A-1とするほうがいい

Bについても同様のことが言える


ということを前提に考えると、単に尺取法の変形版をせよと言われている気がしてきた

A=1、B=cと置くと、この時点でC=A*B=cとなる

Aを1増やすと、A*B>cとなるので、Aを固定したままA*B>cの条件を崩さないような最小のBを求める

(先ほどの前提により、途中のBは考慮する必要がない)

Bを1減らすと、A*B<=cとなるので、Bを固定したままA*B<=cの条件を崩さないような最大のAを求める

(先ほどの前提により、途中のAは考慮する必要がない)

またAを1増やして・・・と、Bが0になるまで繰り返す

計算量の見積もりは難しいがまあAやBが小さいと一気に移動できるから多分問題ないだろう


書いた

サンプル通った。

最大ケースも一瞬で終わる。問題なさそう。

提出。


・・・

何か不安になってきたので色々合っているか考える。

450と言いつつ結構コーナーケース満載っぽい問題だし・・・

やっぱり合ってるように思う。大丈夫かな・・・


チャレンジフェーズ

他の人が軒並み√nでイテレーションしているのを見てよく考えたらそりゃそうだよなと思いつつ、心細さが急上昇

終わり際に勘違いして1チャレンジミス。Easy点低いしMedium落ちたら終わる・・・


システムテスト

通ったのでものすごくほっとした


ソースコード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111026

2011-10-23STLのsortの計算量

STLのsortの計算量

| 22:55 | STLのsortの計算量 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - STLのsortの計算量 - SRM diary(Sigmar) STLのsortの計算量 - SRM diary(Sigmar) のブックマークコメント

STLで非常によく使用するsortというアルゴリズムがあるが、規格上は実装方法が規定されていないらしい。

何となくクイックソートで実装されてて計算量はO(n log n)なんだろうと勝手に思っていたが、よく考えるとクイックソートの最悪計算量はO(n^2)である。

これを突いてチャレンジ・・なんて聞いたことがないので多分大丈夫なんだろうと思ったが心配になったので調べてみた。

計算量が規定されていれば早いのだが規定を調査しきれなかったのでソースを調べてみた。


結論:Topcoder Arenaで使用するSTLのsortは平均計算量O(n log n)、最悪計算量O(n log n)である。

ついでにVC++2010も同様。


TopcoderのWeb FAQによると、gccについては以下のような環境とのこと。

General SRM Algorithm FAQ

Linux 2.6.9-55.0.12.ELsmp, gcc 4.0.2 (RedHat EL 4), glibc-2.3.2, and libstdc++-3.

gcc 4.0.2のソースをWebでダウンロード*1すると、libstdc++-3が付いてきたので、この中にあるstl_algo.hというファイルを見てみる。

(おそらくこいつがalgorithm関連のソースだろう)


stl_algo.h内のsort関数の実装は以下のようになっていた。

  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      // concept requirements
      // アルゴリズムと関係ないので中略

      if (__first != __last)
	{
	  std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
	  std::__final_insertion_sort(__first, __last);
	}
    }

見るからにイントロソートしたあと挿入ソートする、と読める。

イントロソートというのは、最初はクイックソートするのだが再帰回数がリミットを超えるとヒープソートに切り替えるというものである。

ヒープソートは最悪・平均計算量ともにO(n log n)だが、実行上はループ内部の処理の多さからクイックソートに平均計算量で劣る。

しかし最悪計算量はクイックソートより良いので、良いとこ取りをしようということである。

ここではヒープソートに切り替えるリミット(再帰の深さ)を3つ目の引数でlog2(n)*2に指定している。

なおイントロソートしているのにその後挿入ソートをしているのは高速化のためである。

実はイントロソートの関数内では要素数がある閾値以下になると処理を終了するようになっている。

その結果イントロソート終了後は、ほとんどソートされた配列ができることになる。

ほとんどソートされた配列に対しては、挿入ソートが非常に高速に(クイックソートよりも速く!)働くのでこのような実装となっている(と想定される)。


イントロソートは以下のような実装になっている。

  template<typename _RandomAccessIterator, typename _Size>
    void
    __introsort_loop(_RandomAccessIterator __first,
		     _RandomAccessIterator __last,
		     _Size __depth_limit)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      while (__last - __first > int(_S_threshold))
	{
	  if (__depth_limit == 0)
	    {
	      std::partial_sort(__first, __last, __last);
	      return;
	    }
	  --__depth_limit;
	  _RandomAccessIterator __cut =
	    std::__unguarded_partition(__first, __last,
				       _ValueType(std::__median(*__first,
								*(__first
								  + (__last
								     - __first)
								  / 2),
								*(__last
								  - 1))));
	  std::__introsort_loop(__cut, __last, __depth_limit);
	  __last = __cut;
	}
    }

__depth_limitが0になるとpartial_sortを実行している。なぜpartial_sortをするのかというと単にここではpartial_sortをヒープソートで実装しているからである。

(partial_sortはヒープソートで実装すると効率がいい)

また、要素数が_S_threshold以下になるとイントロソートを終了する。_S_thresholdはstl_algo.h内で以下のように定義されている。

  enum { _S_threshold = 16 };

上記以外の場合、クイックソートを実行する。これは__unguarded_partitionで実現されている。(クイックソートのpartition操作にあたる)


partial_sortは以下のようになっている。

  template<typename _RandomAccessIterator>
    void
    partial_sort(_RandomAccessIterator __first,
		 _RandomAccessIterator __middle,
		 _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      // concept requirements
      // アルゴリズムと関係ないので中略

      std::make_heap(__first, __middle);
      for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
	if (*__i < *__first)
	  std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
      std::sort_heap(__first, __middle);
    }

見ての通りヒープソートのようである。


ということでSTLのsortは最悪時でも高速そうだということが分かったので安心した。


ついでに普段ローカルで使用しているVC++2010についても調べてみた。

(インストールするとSTLのソースが付いてきます)

書き方やパラメータは多少異なるが考え方は同じで、イントロソート+挿入ソートで書かれていた。

以上から類推するに、sortの実装はイントロソート+挿入ソートが一般的に効率的な手法なんでしょうね。

*1:Red Hatのglibcは色々バグ修正などがバックポートされていたりするので正確にはコミュニティ版とは異なるところもありますが、アルゴリズムに大きな違いはないだろうと思うので今回はコミュニティ版で確認しています。正確を期すなら、RedHatからSRPMをダウンロードする必要があります。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111023

2011-10-13SRM521 Div1

  • 250:238.04(+75), 500:276.77, 1000:641.16, score:1230.97, rank:4, rating:2247(+168)
  • 奇跡の全問正解で4位・・・ありえん
  • TopCoderを始めて2年余り、ようやくRedcoderになりました。これを維持できるかが問題ですが。

SRM521 Div1 250 MissingParentheses

| 00:43 | SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) SRM521 Div1 250 MissingParentheses - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何か左括弧と右括弧の数の差を取ればいいような気がするが・・

絶対反例ありそう。

・・・

あった。")("←こんなやつ。

えーと・・・左から順番に見て行って、閉じられてない左括弧の数を覚えておけば良いかな

で、閉じられてない左括弧数がマイナスになると、左端に左括弧が必要だから解を+1して左括弧数を0にする。

書けた。

サンプル合った。

提出。


ついでに左括弧と右括弧の数の差を取るプログラムを書いてみる。

こちらもサンプルは全部通る。

反例がチャレンジで使えることが分かった。チャレンジ祭りになりそう。


チャレンジフェーズ

分かりやすいやつは一瞬で誰かに落とされてしまった。

でも2人おかしい人が残っていたので+100。1ミスして-25。儲かった。


ソースコード

続きを読む

SRM521 Div1 500 RangeSquaredSubsets

| 00:43 | SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは・・・いくら何でも問題文が意味不明すぎ

if and only ifってあるけど、ifのほうが成り立つとするなら正方形内の全ての点がPに含まれないといけないんだけど・・・そんな点って無限に存在するんですが・・・

しかも正方形に含まれるというのが、境界線にあるもののみのようにも読み取れるので更に良くない

何とかサンプルから類推すると、与えられたセット内の点のうち、あるサブセットをPとして、P以外のセット内の点が正方形に入ってはいけないということらしい

(一応後でメッセージで補足があったので無限に存在しないというのは分かるようになったようだが・・・)

ともかく題意を理解するのに10分以上かかった。解いた人が少ない原因の一つはこの意味不明な問題文だろう・・・


解法自体はとりあえず登場する全てのx座標とy座標で格子を作って、それで点集合を区切るのが良さそうである

要素数は40だから、セットの数は最大でも40^4/4くらいで64万程度。

重複するものを除くためにstd::setを利用したとしても十分に間に合うと思われる。


適当に書いた。

サンプルの最後が合わない。答えより1多い。

空集合を除くのを忘れていた。。。

修正。サンプルあった。

コーナーケースはないだろうか。ないようだ。

最大ケースで0.1秒くらい。楽勝っぽい。

提出。


ソースコード

続きを読む

SRM521 Div1 1000 Chimney

| 00:43 | SRM521 Div1 1000 Chimney - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 1000 Chimney - SRM diary(Sigmar) SRM521 Div1 1000 Chimney - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

珍しく時間が余っているから1000でも読んでおこうかな

見た感じどうも適当に状態を定義して行列の累乗をすれば良いように見える。

あるレイヤーがチムニー4個未満で構成されるようなパターンがどの程度あるのか考えてみたが、かなり少ないようだ。

1つのチムニーの下に2つのチムニーがあることを考慮すると、最大でも4個未満のレイヤーは、下から3個、2個、1個の3段にしかならない。

他にも4個未満がないもの(初期状態と同じ)とか、1個だけとか、2個だけとか、2個、1個の2段とか、色々考えると10通りくらいか。

(9通りにできなくもなさそうだったけど)

ある状態から別の状態への遷移は1個のチムニーをどのように載せるか考えるだけだから、あんまり難しくない。

行列を作ってみた。

まあ、こんな簡単に答え合うわけないよね。と思ったらサンプルが一発で全部通ってしまった。

残り2分くらいだから記念に提出しとこう。Hardの問題出したこと無いし。

で、結局システムテストも通ってしまった。うーむ。500より簡単じゃないの。。。これ。。。


ソースコード

続きを読む

prosho007prosho0072011/10/14 13:33赤おめでとうございます!

kojingharangkojingharang2011/10/14 17:46すごいっす、おめでとうございます~

SigmarSigmar2011/10/14 21:54prosho007さん、kojingharangさん、ありがとうございます!
何とかこの色を維持できるよう頑張ります。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111013

2011-10-10Google Code Jam Japan 2011 決勝(復習)

Google Code Jam Japan 2011 決勝 C ワイルドカード

| 13:41 | Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

smallを解いているときに思いついたDPでLargeを解いてみたら普通に解けた

大まかには以下のような感じ


aのai文字目まで、bのbi文字目までそれぞれマッチする文字列表現をdp[ai][bi]とする

ただし、最後に*があると何文字目までマッチというのが分からないので最後に*がないものを扱う

次に、aのai+1文字目以降で適当に部分文字列を取り出す(nab~nae文字目まで取り出したとする)

その文字列をbのbi+1文字目以降で検索し、最初に見つかったものをnbb~nbe文字目までとする

dp[nae][nbe]をdp[ai][bi]+"*"+a.substr(nab, nae-nab)で更新する

bのbi+1文字目以降でその文字列が見つからなかった場合、(必要に応じて)末尾に"*"を追加して解の候補とする

解の候補の数があまり多くならないので現実的な時間で解ける


最初と末尾の"*"ありなし辺りで多少コーナーケースのケアが難しくなるがそれ以外には特に難しい点はない

こんなんで通るんならもっと解かれてても良さそうなもんだが・・・


ソースコード

続きを読む

Google Code Jam Japan 2011 決勝 D クローゼットルーム

| 23:02 | Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Smallのみ後で解いた

せいぜい8箇所くらいしか置けないし、あまりパターン数がないのでDFSで全探索するだけ


ソースコード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111010

2011-10-08Google Code Jam Japan 2011 決勝

  • A-small/A-Large:Passed, score:15, penalty(time):1:30:31, rank:281
  • 順位を気にせず、ずっとBをやっていたらとんでもない順位になってしまった

Google Code Jam Japan 2011 決勝 B バクテリアの増殖

| 20:56 | Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

A^A mod Cって普通にbinary methodで計算するだけでは?

全然違った。指数のほうはmod Cではダメらしい。

Aの2乗、3乗、4乗、、、と順番にmod Cで計算してみて、同じものが出てくるまでやってみる

Cが素数のときはC-1回で循環するはずである。Cが素数でないときでも鳩の巣原理でC-1回を超えることはない。

X回で循環したとすると、指数をX減らしても同じ結果になるということだから、指数はmod Xで計算すれば良いのか?

サンプルの最後が合わない。

指数の計算がA^A mod Xとかでやってたけどこれがだめっぽい気がする。指数の計算用の指数も考える必要が・・・?

・・・

1時間半も経った。無邪気にやりすぎた。

Aに浮気。

解いて戻ってきた。


smallなら解けるだろうか?A乗1回するだけなら本当にbinary methodするだけでは?

1WA。違った。A乗を最大2回だった。結局smallの何がLargeより簡単なんだろう。よく分からない。


再びLargeを考える。

指数の計算方法も同じである気がする。Aの2乗、3乗、、、と順番にmod Xで計算すると、どこかで循環する

循環の長さは当然Xより小さいはずだから、これを繰り返していけばいつかXが1になるはずだ

mod 1なら常にAは0になるので、ここで収束する

実装してみる

サンプル合った

WA。原因は想像がついている。

A mod Xを何乗かしたとき、必ずしもAに戻ってくるわけではない。例えばA^5=A^2だがA^4!=A^1みたいなのがあると、指数が2~5の間で循環するわけだから、必ずしも常にmodを取っていいわけではない。

うーーーーーん

時間切れ


以下終了後

実は2~5で循環する場合でも、2以上のXの場合は((X-2)%3+2)乗すれば良いわけだから、結局mod 3で見ればX%3と合同であることは変わらない

ってことは、最大でも1000乗すれば循環が始まっていると見て間違いないのだから、単に1000以上になる場合だけ、modで合同の1000以上の最小値を保持しておけば良いはずだ

書いてみた

small/largeともにPass

コンテスト終了後1時間以上も経っていた

もっと頭の回転早くないと無理だな


ソースコード

続きを読む

Google Code Jam Japan 2011 決勝 A アンテナ修復

| 20:56 | Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Bから浮気してきた

よく分からんけど大きいやつ同士をくっつけたほうが面積大きくなるだろ

Greedyに大きいのをくっつけるコードを書いた。

small通った。

largeも通った。

何かBと比べてえらい簡単だな・・・


ソースコード

続きを読む

Google Code Jam Japan 2011 決勝 C ワイルドカード

| 20:56 | Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

終了後にsmallだけ解いた。

というか基本的に全探索するだけ。こっちのほうがB-smallより簡単な気がする。


ソースコード

続きを読む

NiiqiitoNiiqiito2013/02/17 11:57I hate my life but at least this makes it braeable.

xkhqsmsgifxkhqsmsgif2013/02/19 15:16E9CxwG <a href="http://cdmchajbiebt.com/">cdmchajbiebt</a>

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111008

2011-10-05SRM520 Div1

  • 250:218.59, 500:Opened, score:218.59, rank:204, rating:2079(-5)
  • 500が最近全然解けない。だめだ・・・・

SRM520 Div1 250 SRMCodingPhase

| 22:21 | SRM520 Div1 250 SRMCodingPhase - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM520 Div1 250 SRMCodingPhase - SRM diary(Sigmar) SRM520 Div1 250 SRMCodingPhase - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

どう見てもイテレーションするだけ。

随分計算量が余裕すぎる。まあいいか・・・

書いた

ストレートフォワードに書いたらえらくもっさりしたコードになった


ソースコード

割り振るluckを全探索して、解く順番を全探索する

しかし、解く問題を2^3のビットマスクで決めて、得点の高い問題からGreedyにluckを割り振ったほうが書くのは楽そうだと思った

続きを読む

SRM520 Div1 500 SRMIntermissionPhase

| 22:21 | SRM520 Div1 500 SRMIntermissionPhase - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM520 Div1 500 SRMIntermissionPhase - SRM diary(Sigmar) SRM520 Div1 500 SRMIntermissionPhase - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

仮にways[i][val](=i番目の人がval点取る場合の数)を計算できたとすると、

愚直にやれば、dp[i-1][val+j]+=dp[i][val]*ways[i-1][val+j]でi-1番目の人がval+j点取るようなDPが計算できる

まあでもjの範囲が広くDP更新の計算量が200000とかあって全然無理・・

ways[i][val]の計算方法も全然分からん。だめだ・・・

色々考えたが結局無為に1時間のコーディングフェーズを過ごしてしまった

こんな難しい問題で100人も解けるなんてどうなってるんだ。みんな頭いい


後で

色々調べたらすごく典型的なDPで解ける問題だった。むしろ100人しか解けなかったのが不思議なくらい。

なんでこんな解法に気づかなかったのか。。。


かなり色んな解法があるみたいだけど、簡単なのは以下のようなsumを計算する方式と思う。(こういうのはいっぱい解いてるはずなのだが・・)

dp[i-1][val+j]+=dp[i][val]*ways[i-1][val+j]という更新式を考えていたが、

dp[i][val]+=dp[i+1][val-j]*ways[i][val]という式に変えてみる。

jをイテレートするので、更に変形すると

dp[i][val]=(dp[i+1][val-1]+dp[i+1][val-2]+...+dp[i+1][0])*ways[i][val]

というわけで、dpsum[i+1][val-1]みたいな変数で、dp[i+1][0]+...+dp[i+1][val-1]の和を計算しておけばO(1)で更新できる

これが分かれば、waysの計算も全く同じような方法で計算できることがわかる。

(waysの場合は、各問題ごとに得点の上限が決められているため、引き算が必要になる)


ソースコード

色々書きやすいように変形してるので、上記で書いたまんまの式は使ってません

書いてみて思ったが、直感的な感覚よりかなりコーディングが複雑になる

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111005

2011-10-03Google Code Jam Japan 2011 予選(復習)

  • そうじゃないかと思ったがやはりBにもっと楽な解法があった
  • 大反省会が必要。。。

Google Code Jam Japan 2011 予選 B 最高のコーヒー

| 00:43 | Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Greedy

K日目から1日目に向かって遡っていく

その時点で最も満足度の高いコーヒーを飲むようにする

これで前のやり方(満足度の高いものから消費する日を決める)より全然楽にコードが書ける


ソースコード

続きを読む

tozangezantozangezan2011/10/04 16:12満足度順にとっていくのでも区間を持たないとこれより楽に実装できると思うのですが

SigmarSigmar2011/10/05 20:42コメントありがとうございます。
勝手ながら検索してtozangezanさんのコードを読ませていただきました。
区間を持たないというのは、飲んだ日の分、日数を圧縮するようなイメージで、その区間より後ろにある期限を単純に日数分前に持ってくるという手法ですね。これは思いつきませんでした。紹介の意味でリンクさせていただきます。

odoroimodoroim2019/10/22 12:47http://mewkid.net/buy-xalanta/ - Amoxil <a href="http://mewkid.net/buy-xalanta/">Amoxicillin No Prescription</a> iut.crgg.topcoder.g.hatena.ne.jp.ghm.rj http://mewkid.net/buy-xalanta/

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111003

2011-10-02Google Code Jam Japan 2011 練習問題

  • 練習問題ってGCJ2010の予選問題かと思ったらBだけ違った

Google Code Jam Japan 2011 練習問題 B 数の集合

| 01:46 | Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

区間篩ぽい問題

エラトステネスの篩で素数を作って

区間篩っぽくUnion-Findで結合していくだけ


ソースコード

続きを読む

TommyTommy2013/02/18 19:38A really good answer, full of raitonatliy!

CharlCharl2013/02/18 19:38It's like you're on a misison to save me time and money!

fxtvbyplipfxtvbyplip2013/02/21 14:42YzF6wS <a href="http://wazxjswkbbtm.com/">wazxjswkbbtm</a>

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111002

2011-10-01Google Code Jam Japan 2011 予選

  • A-small/A-Large/B-small(1WA)/B-Large/C-small/C-Large:Passed, score:54, penalty(time):1:53:00, rank:31
  • 真面目に頑張った割にはBのデバッグで余りにも時間を使ってしまっていまいちな結果だった

Google Code Jam Japan 2011 予選 A カードシャッフル

| 20:14 | Google Code Jam Japan 2011 予選 A カードシャッフル - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 A カードシャッフル - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 A カードシャッフル - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

シミュレーション

正順でやるとLargeで時間に間に合わないため、逆順でシミュレーションする

こういう逆からなら計算量が削減できるというのは慣れていないと分かりにくい気もする

提出時間:Large 14m46s


ソースコード

続きを読む

Google Code Jam Japan 2011 予選 B 最高のコーヒー

| 20:14 | Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Greedy

まだコーヒーの種類が確定していない日の集合をvector <pair <ll, ll> > empで表す

満足度が高いものから順番に、期限ぎりぎりから消費していく

期限ぎりぎりのコーヒーより満足度の低いコーヒーを使っても、満足度の低いほうのコーヒーが余分に減るだけで、何もいいことがない

ということで以上の方針で問題ない

vector <pair <ll, ll> >で表される期間とか、こういうものの管理はとてつもなく面倒くさい。最悪。

案の定バグりまくり。

一通り直してサンプル合った。

Small合わない。

気分転換にCを解くことにする。

・・・

Cを解いて戻ってきた。

とりあえず簡単に全探索のコードが書けるので、それでSmallだけ解いてみる。

解けた。提出。Correct。

先ほどのLarge用の回答と答えが違うところを調べる。

余計なbreak文が一つ入っていたことに気づく。修正。Small合った。

Large提出。

提出時間:Large 1h49m00s


ソースコード

Large用

続きを読む

Google Code Jam Japan 2011 予選 C ビット数

| 20:14 | Google Code Jam Japan 2011 予選 C ビット数 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 C ビット数 - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 C ビット数 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

DP

下の桁から順番に、aとbの1,0を決めていく

状態はdp[2][70]で、添字はそれぞれキャリーの有無、桁数を表す

初期状態でdp[0][0]以外は無効な値であることに注意

Nは2進数で最大59桁であるはずだが、念のため61桁まで計算し、最終的にdp[0][61]を解としている

64桁とか計算するとオーバーフローに注意しないといけないので、適度に打ち切る必要がある


ソースコード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111001