Hatena::Grouptopcoder

k_operafanのTopCoder日記

2012-01-02

[]TopCoder SRM 528 09:15

Easy(250点)

10の倍数でかつ小さいうさぎから優先に切っていくだけのコードを投げた

Passed System Test(242.84)

Medium(525点)

作れる文字列を全生成して,それを見たす文字列のパターン数をDPした.

Passed System Test(267.34)

Hard(950点)

最小費用流とかばかなことを考えていたら時間が過ぎさった.

Opened

Challenge Part

10の倍数を優先的にしていないコードを撃墜

+1/-0 50pts

Result

得点:242.84+267.34+50+0=560.18点

順位:64位

レート:2183(+53)

EasyもMediumも落ちなくて良かった

ChanChan2012/09/01 12:55So true. Honesty and eevryhting recognized.

rkmpvvafnrkmpvvafn2012/09/02 04:275VCfUH <a href="http://bohtnkuyzsgn.com/">bohtnkuyzsgn</a>

cyrqyocphcyrqyocph2012/09/04 05:56mv1for <a href="http://igcigimqsdjc.com/">igcigimqsdjc</a>

vtfrranivtfrrani2012/09/04 17:50EVsglb , [url=http://ryxggkwridun.com/]ryxggkwridun[/url], [link=http://ptwcixtrbdry.com/]ptwcixtrbdry[/link], http://upbdbicxbqrg.com/

2011-12-14提出前チェックリスト

Competitive Programming Advent Calendarの第14日目の記事です.

わたしにとって競技プログラミングをやっていて一番悔しいことは,本質に関係の無いちょっとしたミスで正解を逃すことです.

そういうミスを避けるために,陥りやすいミスをまとめてみました.

提出してしまうとRuntime Errorになってしまうミス 23:59

スタックオーバフロー

再帰の深さが大きくなりすぎると,スタックオーバーフローを起こしてしまいます.

特にメモ化再帰で深さが10000を超える場合は注意が必要です.

巨大なケースを試してみて,正常に終了するかを確認して,メモ化再帰だったらDPに書き換えたり,末尾再帰等ならループに書き換えるようにしましょう.

対策
  • 巨大なケースを試す.
  • ローカルで実行するならスタック領域を増やす.
  • メモ化再帰→DP

などなど

配列外アクセス

配列外アクセスは例えばDPなどで起こりやすいです.

char型配列で文字列を持つ場合の最後の'\0'は忘れがちなので気を付けましょう.

対策
  • 巨大なケースで試す
  • ある程度多めに配列を確保するようにする
  • char型配列を使わずにstringを使う

などなど

オーバーフロー

.NET系の言語ではオーバーフローは例外になります

提出してしまうとWrong Answerになってしまうミス 23:59

初期化忘れ

テストケースが複数ある問題の場合,初期化を必ず忘れないようにしましょう.

対策
  • 複数ケースの場合をかならずチェックする

など

オーバーフロー

各型の保持出来る値の範囲は以下のようになっています.

C++ Java .NET(C#/VB) 値の範囲
char char char/Char -128~127
short short short/Short -32768~32767
int int int/Integer -2147483648~2147483647(≒-2*109~2*109)
long long long long/Long -9223372036854775808~9223372036854775807(≒-9*1018~9*1018)
- - decimal/Decimal -79228162514264337593543950336~79228162514264337593543950335(≒-7*1029~7*1029)

これを超えることが無いかあらかじめ計算するようにした方が良いです

対策
  • 巨大な数のケースをチェックする
  • 多倍長整数を使う

などなど

浮動小数の誤差

整数に対してpowやsqrtを用いた場合も若干の誤差を生じることがあります.

実装依存ですが,例えばa=5,b=2の時に,(int)pow(a,b)=(int)24.9999999999=24になってしまったりすることがあります.

これを防ぐために,答えが整数であることを期待している場合でも(int)(pow(a,b)+1e-7)のように適当な小さい値を足すようにした方が良いと思います.

対策
  • 微小値を足す
  • powの場合はループで,sqrtの場合は二分探索などで自前実装する

などなど

MODの値のミス

問題によっては答えの値をMで割った余りの形で出力させるものがありますが,Mを間違えると当然答えが変わってしまいます.

108+7と109+7はともに素数で間違えやすいので特に気を付けましょう.

対策
  • 問題文からコピーペーストする

など



提出してしまうとTime Limit Exceedになるようなミス

メモ化忘れ

メモ化再帰においてメモ化を忘れてしまうと,TLEしてしまいます.

大きなケースでチェックするのを忘れないようにしましょう.

対策
  • 大きなケースでチェックする
  • 最初からメモ化するようにする

などなど

入出力方法

入力の数がとても多い問題の場合,遅い入力方法を使うとTLEしてしまうことがあります(特にPKUでは顕著).

入力が多いとき,

C++でcinを使っている場合はscanfやreadを

Javaでscannerを使っている場合はBufferedReaderを

使うようにしましょう

対策
  • 入力を早い方法に変える

非正規化数

kou_miyamさんのhttp://d.hatena.ne.jp/komiyam/20111210/1323503019に詳しくかつ分かりやすく載っています.

遅い標準ライブラリ

時間制限が厳しい問題の場合,hypot関数やstd::setなどのように若干遅い関数等を使うとTLEしてしまうことがあります.(これもやっぱりPKUで顕著 -O2欲しい)

対策
  • 自前で実装した高速なものを使う

通る人通る人2011/12/15 23:52challenge Integer.MAX_VALUE ?

k_operafank_operafan2012/01/02 09:11Challenge Succeed!

BoomerBoomer2012/11/15 08:57All of my questions setlted-thanks!

xmimisyrhxmimisyrh2012/11/17 05:22IMxCtU , [url=http://qdasntgfcpon.com/]qdasntgfcpon[/url], [link=http://njumodhpdivd.com/]njumodhpdivd[/link], http://culsmafenbge.com/

lupbuvhlupbuvh2012/11/17 12:2177HEfx <a href="http://yzztpjtvxzxi.com/">yzztpjtvxzxi</a>

iuqchfunkaiuqchfunka2012/11/17 21:47MK9m7k , [url=http://lgglcwpigfob.com/]lgglcwpigfob[/url], [link=http://wnxysjrvjnzr.com/]wnxysjrvjnzr[/link], http://khcneckuryza.com/

2011-12-04

[]Codeforces Beta Round #96 Div1 13:23

A問題

最初は問題文の意味が付かめず,与えられた文字列から数列を作るものだと勘違いしてしまい,答えが合わずに詰んでしまった.

結局問題文の下の方にあるNoteに気づき,それで問題文を理解し,修正してSubmit.

Accepted(466点)


BとCで悩んだ結果解いている人が多そうなC問題に

C問題

一次元上のロボットを命令によって動かす(ただしN回はかならず命令を変更しないといけない)問題

ある命令まで見た時に,ある方向を見ていて,ある回数だけ命令を変化させた時の最大の距離をメモして解いてみる.

サンプルが合ったので提出してみた所,"Wrong Answer(Pretest4)".

問題文を再読した所,"(one command can be changed several times)."を考慮していなかったのが不味そうだったので修正してSubmit.

Accepted(466点)


DとBで悩んだ結果,Bはただの実装ぽかったのでB問題に

B問題

愚直にシミュレートすると間に合わなそうだったので,ある点からある方向に出来るだけ進んだ時の座標をあらかじめ計算しておくことにした.

後は実装するだけ.

Accepted(1128点)

D問題

一番下の桁から見ることにすると,その桁に対して加算or減算or何もしない を選択することになる.

そこで,現在見ている桁と繰り下がりがあるかどうかでDP

経路復元に思ったより手間取ってしまい,かなり時間を掛けてしまった.

Accepted(1344点)

E問題

問題を見た瞬間,UTPC 2011 Hみたいな問題だと思ったので,それをベースに経路復元を追加する感じで解いた.

経路復元は逆辺にフローが流れているかどうかを用いて行なった.

Accepted(1340点)

Hack

何も出来なかった

結果

点数:466+1128+1222+1344+1340+0=5550

順位:3位

レート:2032(+158)

AwaAwa2012/08/30 20:55Four score and seven minuets ago, I read a sweet article. Lol thanks

xvouymqyzkmxvouymqyzkm2012/08/31 15:57ndXart <a href="http://zwliwohkpkgq.com/">zwliwohkpkgq</a>

lvdogjlvdogj2012/09/01 04:02rDY7uh , [url=http://mikwbavebwlo.com/]mikwbavebwlo[/url], [link=http://bgzmsnxtujrk.com/]bgzmsnxtujrk[/link], http://zprrvkeurgip.com/

znlwyeznlwye2012/09/02 02:35y4tvBR <a href="http://esubbkldtdey.com/">esubbkldtdey</a>

ovavislifalovavislifal2012/09/02 08:45a7cPNc , [url=http://jmkzpwwebqwx.com/]jmkzpwwebqwx[/url], [link=http://wpyqgwkmmxos.com/]wpyqgwkmmxos[/link], http://xycrfemhhsfs.com/

2011-11-29

[]TopCoder SRM 525 Div1 00:18

2回連続の大敗北

Easy(300点)

範囲を決め打ちして試してみる

k=0のケースを忘れていたけど,入力に無かったので安心

Passed System Test(276.43)

Medium(525点)

解けなかった,何故か全探索で2^32とおもってしまった.

Opened

Hard(950点)

Unopened

Challenge Part

525の計算量を知りました

+0/-0 0pts

Result

得点:276.43+0+0+0=276.43点

順位:186位

レート:2075(-8)

2011-11-20

[]Unknown Language Round #4 03:20

Befunge言語.

資料は大体Wikipedia(ja).

A問題

とりあえずやるだけ

&::2**\-.@

B問題

スタックを用いる

0v      >v
 >~:5-5-|> 
        $ >v
        >:|>,
          @

C問題

Bよりも簡単

0&v        >v
  >\&+\ 1-:|>
           >$.@

D問題

プログラム上に数値を記録することが出来る

&55p&00p&66p1v    >v
             >00g:|> \55g*66g%\ 1-00p
                  >\.@

E問題

プログラム上には0~255の数字しか記録出来ないことに注意.

v       >v
>001&:1-|> 2-v
        >0.@ 
v            <
  >1-v
>:|  >:99*/ 00p 99*%11p 10p 20p 20g+ 10g+ 99+8+% 30p 20g 10g 30g 00g99** 11g+
  >$.@

F問題

200p&v     >00g1+00pv          >v 
     >:00g%|      >>> 00g 88*- |>
           >00g:./^            >v   >.@
                                >:1-|
                                    >@  

2から順番に割っていくだけ

G問題

v       >v       >v                 >v
>~:5-5- |>:348**`|>:9999997++++++2*`|>,    >
        >@       >,                v>84*-, ^ 
                                   >       ^

場合分け.小文字だったら32を引く

H問題

競技プログラミング的には典型問題.スタックを使う.

0v      >v     >v  >v
 >~5-5-:|>:65*-|>\:|>  1-\      >$    
        v          >"ON",,@         
        v      >            \1+\^
        
          >"ON",,@ 
        >$|>"SEY",,,@
          >^

結果

8問解けて14位だった.

80x25ということを忘れててソートが解けなかったのが悲しい.

PinkPink2013/02/18 18:37IJWTS wow! Why can't I think of thgins like that?

uaihaxeuuaihaxeu2013/02/19 02:16ZLCb5g <a href="http://vabroxfdkcxh.com/">vabroxfdkcxh</a>

ilwxvxveyjtilwxvxveyjt2013/02/19 11:23pc2xpX , [url=http://wekxaiffbfix.com/]wekxaiffbfix[/url], [link=http://kerpjdelhbaq.com/]kerpjdelhbaq[/link], http://whkudnhelhpy.com/

ncrsjpgmtttncrsjpgmttt2013/02/21 14:19mk7dWi <a href="http://jltigiodwqay.com/">jltigiodwqay</a>

seghehldrlcseghehldrlc2013/02/21 18:44ogW4WC , [url=http://egwmtxsovhrv.com/]egwmtxsovhrv[/url], [link=http://dxfjfzicqbjq.com/]dxfjfzicqbjq[/link], http://vjmyyqqivqif.com/

StitchesStitches2016/05/03 06:48Inlntligeece and simplicity - easy to understand how you think.