Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-02-24

Codeforces Round #109 (Div. 2) 反省

| 03:04 | Codeforces Round #109 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #109 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #109 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 981/1284

Score: 492

Solved: ox-x-

Rating: 1451 -> 1383 (-68)


フルボッコキタ――(゚∀゚)――!!

の割には,あまり下がってない様子.

いずれにせよ,今回のDは勉強になりました.


155A

最大値・最小値が更新されたらcount++するだけ.

https://github.com/k-mats/codeforces/blob/master/150/155A.cpp


155B

a[n]とb[n]を用意しておき,b[i] > b[i+1]になるようにaとbをソート.b[i] == b[i+1]の場合は,a[i] > a[i+1]になるようにソート.

その後,i == 0から順にcount_b == 0になるまでcount_a += a[i], count_b += b[i]すればいいだけ.


が.実際に書いたソートが間違っていたカウントする際の処理を間違えていた/(^o^)\

SRM533 Div2 250のピカチュウの時もそうだったけれど,解法が思いついた状態でさっさと書いたコードの中にケアレスミスがあっても見つけようがないなあ・・

https://github.com/k-mats/codeforces/blob/master/150/155B.cpp


C (154A)

前から順に貪欲法で解いて死亡.

abbaaaのときはbを全て潰し,abbaaabbbbのようなときはaを全て潰す必要があることに気付いたのはCを飛ばしてDをsubmitしてから..


D (154B)

何も考えずon/offの状態を配列で保持し,二重ループするとO(10^10)になって死亡する.

ので,on状態のcolliderのみset<long> colsに保持し,offのリクエスト時にはcols.findしてoffを判断.

onのリクエスト時にも同様にcols.findし,無ければリクエストされた番号とcolsの中の番号をしらみつぶしにユークリッドの互除法.


で死亡.そりゃあいくらfindで計算量減らしても,ループの中で全探索やってりゃ結局O(10^10)になるわな・・


診断人さんの放送(http://com.nicovideo.jp/community/co78570)を見ていたら,”整数のペアを共に素因数分解し,同じ素数を持っていたら互いに素ではない”ということを利用すれば良いと知る.なるほど.


k番のリクエストが来たらk番と一緒にkの素因数もon状態と考えておけばユークリッドの互除法は必要なくなる.

更に,使用中の素因数を覚えておけば,k番を削除するときにも役立つ,と.


ついでに,整数が非常に多く出てきても,出てくる素因数はそんなに多くない,というのも有用な情報だと思った.


E (154C)

読んだだけで解いていないが,u, vを使ってる時点でグラフ問題だなあ,という感想.

ノードが2つのみの木を構成するペアおよびその他のノード全てとつながっているノードのペアを探せ,ということですね.


反省点

  • ”互いに素”に対してユークリッドの互除法しか対処法を知らなかった

教訓

  • "互いに素" = "共通する素因数を持たない"と言えるので,素因数分解が有効

TopCoder SRM534 Div2 反省

| 23:39 | TopCoder SRM534 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM534 Div2 反省 - iwbtr - kmats TopCoder SRM534 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 282/943

Points: 353.65

Solved:oo-

Challenge: 1 failed

Rating: 940 -> 964 (+24)


250で許されざる時間ロス&チャレンジ失敗.何とか500を通したものの,その500も糞コードすぎて解いた気がしない・・

20分後のCodeforcesも頑張ります.


534 Div2 250

ただイテレータスワップするだけ.するだけだったのだが・・


後ろ2つが"."か".."であることを確認するために

vector<string>::iterator it = files.end();
advance(it, -1);

等とするところを,

it = advance(it, -1);

としてたorzorzorz


一発で解けなかった時点で半分パニック状態に陥り,大幅に時間ロスしてしまった・・

イテレータの基本的な使い方を復習しないと・・


どう見ても撃墜できるだろう,という回答が一つあったのに弾かれた.

Codeforcesが終わってから要確認.


534 Div2 500

"o"マーク(checker)を左から右に移動させていき,移動できなくなった方が負けるゲーム.

対戦形式のゲームなのでミニマックス法的な考え方が必要なのかと思いきや,今回は特に各プレイヤーの最適解を考える必要はなく,操作する人が一人だけと考えてしまって良い.

  1. 最も左のチェッカーを操作対象として選ぶ
  2. 右端に到達するか,他のチェッカーが邪魔で移動できなくなるまで移動させる
  3. まだチェッカーが残っていれば1に戻る
  4. 全てのチェッカーを移動し終わったら,操作回数の偶奇で勝利プレイヤーを判定する.

またもや実装しながら考えていたため,二度と見たくないような糞コード爆誕.

なぜか2度もチャレンジされてた.


534 Div2 1000

ちらっと問題文を読むも,解いた人がほとんどいなかったため投げた.

結果的に0%..


反省点

  • イテレータの扱い方を忘れていた
  • 考えながら実装した

教訓

  • 基礎的な文法やアルゴリズムを復習すべし
  • せめて大まかな方針を固めてから実装し始める

2012-02-20

Codeforces Round #108 (Div. 2) 反省

| 02:48 | Codeforces Round #108 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #108 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #108 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 696/1260

Score: 1288

Solved: oox--

Rating: 1501 -> 1451 (-50)


Cのaccept率826/1260なのにTLEで通せなかったorz


152A

vector<string>に成績を格納し,各科目における最高点を記憶.

別途0で初期化したint a[n]を用意しておき,その最高点と等しい人iはa[i] = 1とする.

最後に,1となった人(=1度でも最高点を取ったことある人)の数を数えればOK.

https://github.com/k-mats/codeforces/blob/master/150/152A.cpp


152B

各ベクトルi < kに対し,一回適用するごとにステップ数stepをインクリメントを繰り返す.

それ以上適用できない(フィールドを超える)場合は次のベクトルi+1に移り,同じように一回適用してはインクリメントを繰り返す.

最後にstepを出力・・するとTLEになる.


ので,まずはベクトルiを最大何回適用できるかを数え,その数aの分(dxi * a, dyi * a)だけ一気に移動&step += aする.

aの算出は,ベクトルの向きに気を付けつつ,x方向とy方向それぞれ移動できる回数を求め,小さい方をaとすればよい.

https://github.com/k-mats/codeforces/blob/master/150/152B.cpp


152C

TLE@pretest 7の文章を見ること約20回orz


前回"TLEになるようなら大元の処理を見直せ”と反省したものの,何が違うのかさっぱり.

dpしても探索範囲を狭めても処理を軽くしてもTLE


で,他の人のコードを見て納得・・

生成されうる文字列の数 == m文字の各位置で取りうる文字を取った時に生成される文字列の数

なので,各文字列のj<m番目の文字の種類の数を数え,順位掛け算すればよい.</ppp>

正答率が高いのは,この手の問題は頻出もしくは典型的なものなんだろうと予想.

純粋に練習量が足らない・・

https://github.com/k-mats/codeforces/blob/master/150/152C.cpp


152D

みてない


152E

みてない


反省点

  • よく考えずに愚直にコードを組んだ
  • 練習量が足らない

教訓

  • Cで愚直な方法は弾かれやすい.アプローチをよく考えるべし
  • 精進すべし

2012-02-18

TopCoder SRM533 Div2 反省

| 04:39 | TopCoder SRM533 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM533 Div2 反省 - iwbtr - kmats TopCoder SRM533 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 428/1535

Points: 424.1

Solved: xo-

Challenge: 3 succeeded

Rating: 915 -> 940 (+25)


ピカチュウで笑いピカチュウで泣くorz

問題文で笑ったりMidの方針間違えてタイムロスしたり3つも撃墜できたりピカチュウ落としたり色々なことがあった・・

撃墜成功は初めてだったから心臓バックバクやったぞ!


533 Div2 250

お!ピカチュウー!


ただ文字列を前から調べていくだけ,いくだけだったのに・・

インデックスのインクリメント後にword.size()を超えていないか調べるタイミングを間違えていた・・

Easyといえど油断してはならない・・


一方で,"pi", "ka", "chu"の部分文字列があったらそれを空文字列と置き換える人が割といたので,撃墜させていただいた.

例)この手法では"pkai"はYESになってしまう

他の部屋を覗いてみるとEasyが撃墜されていたので,何事かと思いコードを読んだところ,これを発見.

Challenge中に他の部屋の様子を見る,というのは割と良い作戦だなあと思った.


533 Div2 500

お!東方ゥー!


Div1 Easyとほとんど同じ問題だったらしいが,向こうは最大50 elements.こっちは10 elements.

よって全探索しても8!=40320通りにしかならないので,普通に再帰で深さ優先探索した.


が,その前に”greedyでいけるんじゃね?”と思いしばらく格闘.

ある程度組んだところで,生半可なgreedyでは死ぬケースを思いつき急遽全探索に切り替え.

systestで死んだ人はgreedyで提出したのだろう・・

一方,div1の方は全探索できないのでdpか何かで解く・・はず.


533 Div2 1000

お!魔法少女ゥー!


時期的にまどマギかしらん?と思いながら解くも500で大分時間を食ったためにtime up.

各魔女の情報は日付順にソートしてから処理する必要があるはず・・


反省点

  • Easyを舐めた

教訓

  • Easyといえど侮る無かれ
  • Challengeでは他の部屋の様子も見ると良い

2012-02-17

Codeforces Round #107 (Div. 2) 反省

| 02:59 | Codeforces Round #107 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #107 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #107 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 400/1401

Score: 1366

Solved: oox--

Rating: 1418 -> 1501 (+83)


ギリギリ青キタ――(゚∀゚)――!!

Cを通せなかったのは残念だけど,最近多かったケアレスミスやWA@pretest 1がなかったのは良かった.


151A

入力する値がたくさん出てきてうぜーーと思うも,Noteの通りに実装したら他のSampleでも通ったのでそのまま提出.

何かコーナーケースがあるんじゃないかと少し気になるも,まあAだし・・と思ってしまった.危険である.

https://github.com/k-mats/codeforces/blob/master/150/151A.cpp


151B

入力するデータがたくさん出てきてうry

名前name, タクシーの番号の数t,ピザ屋の番号の数p,女の子の番号の数gを持つFriendクラスなるもの

class Friend {
public:
  string name;
  int t;
  int p;
  int g;
}

を用意しておき,上から順番にインスタンスを作ってはvector<Friend> vfに突っ込む.

と同時にt, p, gの最大値max_t, max_p, max_gを取得しておき,各maxに等しい値を持つFriendのnameを最後に出力していけばOK.


電話帳の登録数が0のときの処理方法が書いていなかったので,何かコーナーケースがあるんじゃないかと気になるも,まあBだしry

https://github.com/k-mats/codeforces/blob/master/150/151B.cpp


C (150A)

6はlosing number,30は6を取ればいいのでwinning number,素数はlosingでもwinningでもない・・ということは,各i < qに対し,losing or winning or primeを順々に判定していけばいいのでは?と考えた.

winning numberとは,因数の中にlosing numberを持っている数.

losing numberとは,winningではない&&素数ではない数.


が,この方法だと各i < qに対し一々素数判定をすることになるために当然TLE

losing numberは上の考え方ではなく,”素因数分解したときに素因数が2つしかない数”とするのが正しい.

すると,qを素因数分解して,残りの素因数が2つになるような値を取ればよくなる.

例)q = 120 = 2*2*2*3*5に対し,残りが2*2になるように値を取る,すなわち2*3*5 = 30を取ればプレイヤー1の勝ち.

https://github.com/k-mats/codeforces/blob/master/150/150A.cpp


D (150B)

Cと同じ1500点だったので,解かれた数を見つつCが無理そうならDに移ろうかと思うも,Dはほとんど解かれていなかったので結局ほとんど見てない.


E

みてない


反省点

  • 場合分けの条件を精査しなかった

教訓

  • TLEになるような場合分けの場合は小細工よりも大元の条件を吟味し直すべし

Codeforces Round #106 (Div. 2) 反省

| 21:02 | Codeforces Round #106 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #106 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #106 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 654/1347

Score: 486

Solved: oxx--

Rating: 1448 -> 1418 (-30)


Bはpretest 1が通らず,Cはsystestで爆死.

意地になってBで時間をかけすぎたのが失敗だった.

以前のWA@pretest 1のこともあったので入念にチェックするのは大切だけど,かと言って1問に時間をかけすぎるのも考えもの,


149A

月毎の値を降順にソートして,値の大きいものから取得.値がkに達すればその時の取得回数を返し,12個全て取得してもkに達しなければ-1を返す.

ただし,k=0のときのみちゃんと0を返すようにすること.

https://github.com/k-mats/codeforces/blob/master/140/149A.cpp


149B

文字列処理の問題.

まずは文字列aが"0N"のように2桁目が0,1桁目がN”以下”の値になってないか,かつ,文字列bが"0Z"のように,2桁目が0,1桁目がZ"以下"の値になってないか(実質的に1桁目の値は無視)調べる.そのような文字列は全基数を取りうるので-1を返して終了する.

例)例えば"11:0Z"はa="11"が二桁の時点で取りうる基数が制限される.なぜなら,aを整数化した時に23以下にならないといけないからである.

また,a="0P"のような場合は,23以下となるために取りうる基数が存在しない.よって,これもこの時点では無視する.

一方,a="0N"のような場合,基数をどのように取っても整数化した値は23以下に収まってしまう.したがって,a, b共にそのような文字列であった場合,取りうる基数は無限に存在してしまうので,-1を返して終了する.


次に,文字1つ1つを整数化する関数を作っておき,まずは取りうる基数の下限を調べる,

例)14:50の場合は5が含まれるので,基数の下限は6でないといけない


次に指定した基数に基づいて文字列を整数化する関数を作っておき,ある基数rでa, bを整数化した値が23もしくは59に収まるかどうかをrをインクリメントしながら調べ,基数の上限を見つける.


以上で発見された取りうる基数を順に表示していけばよい.


・・・のはずが,pretest 1でWA.また初期化ミスか?と思うもそれらしいミスは見つからず・・

終了後改めてsystestに通してみると,手元の環境では

input: 11:20

output: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

となるものが,systestでは

input: 11:20

output: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

となっていた.工エエェェ(´д`)ェェエエ工


どうやら,文字列->整数変換の関数の中で,int c = a^bを計算するのに

int c = (int) pow((double) a, (double) b)

としていたのが原因だったようだ・・

確かにアレなキャストだとは思っていたけど・・誤差を生みかねない処理はするもんじゃないなあ・・

https://github.com/k-mats/codeforces/blob/master/140/149B.cpp


149C

20分でpretestは通ったけれどsystestでfail.

tutorialを見てぐうの音もでないほど納得・・

プレイヤーを実力順に並べ,偶数の位置(0, 2, 4, ...)にいるプレイヤーは1つ目のチームに,奇数の位置(1, 3, 5, ...)にいるプレイヤーは2つ目のチームに振り分ける.これだけで3つの条件は全て満たされる.

実力差が最も上手い人の実力以下になることは幾何的に証明する.

実力の値を軸とする一次元上にプレイヤーを並べ,0番目と1番目,2番目と3番目,4番目と5番目・・といった各人毎の実力差の和=チーム全体の実力差は原点と最も上手い人の位置をつなぐ点線になり,決して最も上手い人の実力を超えることはない.

https://github.com/k-mats/codeforces/blob/master/140/149C.cpp


149D

みてない


149E

みてない


反省点

  • 1問に時間をかけすぎた
  • doubleを挟むキャストをしてしまった

教訓

  • 1問に1時間以上使わない
  • doubleを挟むキャストは誤差の温床.整数だけでできる処理は極力整数だけで行う

2012-02-09

Topcoder SRM532 Div2 反省

| 03:58 | Topcoder SRM532 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM532 Div2 反省 - iwbtr - kmats Topcoder SRM532 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 554/1361

Points: 234.58

Solved: ox-

Rating: 930 -> 914 (-16)


registerした後仮眠を取って起きたら0:59.250を理解するのに時間がかかった..

systestでは600点問題大虐殺.ただのgreedyで解くとx.xの場合に引っかかることに終盤気付くも950が気になってそっちを優先してしまったorz


532 Div2 250

Mr. Dengklekが数えそこねたアヒルの数の最小値を求める問題.

アヒルに付いた数字の最大値をmax_num, 最小値をmin_numとして,

return (max_num - min_num + 1 + 1 - ducks.size());

するだけ.


532 Div2 600

できるだけ綺麗な鎖の列を作る問題.

鎖を場合分けすると,

  1. "xyz"のように錆のない鎖
  2. "x.."や"xy.", "..z", ".yz"のように片端が錆びている鎖
  3. "x.z"のように中央が錆びている鎖
  4. ".y."のように両端が錆びている鎖

の4通りになる.1番目は何も考えず連結に使えるので,int sumに値を保持しておく.

2番目はそれぞれ左端もしくは右端にしか使えず,3番目は左端・右端両方に使える.

そこで,2番目もしくは3番目に属する鎖は別途vectorなどに保存しておき,そこから"最も値が大きくなる左端・右端の組み合わせ"を探す.

ただし,"x.z"型の鎖はそれ一つで両端に使うことはできないので,そのことに注意する必要がある.

4番目は連結不可なので,4番目に属する鎖の内最も値が大きいものと,1〜3番目を連結した鎖の値を比べる必要がある.


引っかかるポイントはおそらく2つ.

  1. 4番目の鎖の処理を最後に行うのを忘れる
  2. 3番目の鎖の処理を間違う

この内1つ目はExamplesの中にあるので,大抵の人が気付くはず.

2つ目は,初めにint left, rightという左端・右端用の変数を用意しておき,chainsを順に見てその場で大小比較することにより左端候補・右端候補を決めてしまうgreedyな方法を思いついてしまうとハマる.

この方法の場合3番目の鎖の処理で迷うが,それっぽい条件でleftもしくはrightと比較する処理を書くとExamplesは通ってしまう.自分がこれだったorz


例)"..3", "2..", "5.4", "6..", "111"

正解は"5.41116..."で13になる.

しかし,greedyな方法の場合,"5.4"を見たときにこの鎖を右端候補としてしまう可能性がある.

(まだ"6.."を見ていないので,左端候補で間違いないといえるような処理は書けないはず.)

よって,"..31115.4"で12・・というような誤答を返す可能性がある.


コードを書いている途中も"greedyだと無理じゃないかなあ"と思いつつもExamplesが通ってしまったので"まあいいや"と思ってしまった・・

950を解いている途中で無理だということに気付くも時すでに遅し・・Easyはともかく,Mediumは回答の妥当性をちゃんと確かめないと駄目だと痛感..


532 Div2 950

愚直に全探索するとオーダーが大きすぎてしまう問題.

dpでなんとかするのかな.

なんかdpが必要そうな問題は毎回ほとんど手を付けずに終わってる気がする・・


反省点

  • 起きたら開始直前だった
  • 回答の妥当性を確かめずに提出してしまった

教訓

  • 仮眠しなくてもいいように前日・当日の睡眠を調整する
  • 回答の妥当性をちゃんと確かめる,もしくは気になったケースは手でちゃんと確かめてからsubmitする

2012-02-02

Codeforces Round #105 (Div. 2) 反省

| 05:16 | Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #105 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 427/1320

Score: 1628

Solved: 2 (A: 980, 00:05 / C: 748, 01:28)

Rating: 1350 -> 1448 (+98)


出題者による問題点の不適当な設定を避けるために5問すべてが1000点になったRound.

148A

お姫様がd匹のドラゴンをなぎ倒していく,

姫は4つの攻撃手段を持っており,各攻撃手段では”各”第k, l, m, n番目のドラゴンを倒すことができる.

全部で何匹のドラゴンを倒すことができるか?という問題.


問題文だけ読むと(゚Д゚)ハァ?な問題だが,sampleを見れば一目瞭然.

i番目のドラゴンに対し,iがk, l, m, nのいずれかで割り切れる = そのドラゴンは倒せる,ということ.

https://github.com/k-mats/codeforces/blob/master/140/148A.cpp


148B

お姫様がドラゴンの巣から城へ逃げ帰る.城までの距離はc.

姫が逃げてからt時間後,ドラゴンは脱走に気づき追いかけ始める.

姫(速度vp)がドラゴン(速度vd)に追いつかれた場合,宝玉をその場に捨てる.

するとドラゴンは宝玉を一旦持ち帰り時間fをかけて宝玉を整頓し,その後追跡を再開する.

このとき,上手く逃げ帰るのに必要な宝玉の数はいくつか?という問題.


姫の位置をxp, ドラゴンの位置をxd, 追いつくまでにかかる時間をdtとおき,dt時間後に追いつく

-> 宝玉の数++

-> ドラゴンが帰って整頓するまでの時間分xpを進める

-> xd = 0にする・・

というのを,xp >= cになるまで続ければOK.


・・が,systestで撃沈.よくよく考えればvp > vdの場合(もちろん宝玉は0個)を忘れていたorz

https://github.com/k-mats/codeforces/blob/master/140/148B.cpp


148C

お姫様が花婿を探している.姫は複数の候補者と順番に謁見するが,その比較基準はお金.

ある候補者がそれまでの候補者よりもお金持ちなら,姫は"Oh..."と言う.

ある候補者がそれまでの候補者全員のお金の和よりもお金を持っていたら,姫は"Wow!"と言う.

1人目の候補者に対しては何も言わない.

候補者の数をn人,Oh...と言った数をa, Wow!と言った数をbとした場合,あり得る候補者の列を答えよ(候補者iは整数,すなわち所持金tiで表す),という問題.あり得る列がない場合は-1を出力.


初めにWow!と言い切らせ,次にOh...と言い切らせる作戦.

お金は1から50000までなので,候補者1人目はt1 = 1とする.

その後,bの数だけti = sum + 1を繰り返す.(sumはi-1までの和)

その後,aの数だけti = t(i-1) + 1を繰り返す.

最後に,残りの候補者はすべて1にする.

例)10 2 3

1 2 4 8 9 10 1 1 1 1


ただし,n - a = 1の場合は-1になる.なぜなら,a = n - 1の場合,2人目以降の全候補者に対しOh...と言わせないといけないのだが,1人目がどのような数であろうと,2人目に対しては何も言わない or Wow!しか言えないので.

例)t1 = 1 に対し,t2 = 1なら何も言わないし,t2 = 2ならWow!と言ってしまう.


途中で使ったbool flagの初期化を忘れてかなりタイムロス.

ずーーーーーっとpretest 1が通らず,もうだめだあああと思っていたらオチがこれだとは・・

手元の環境では上手く動いてしまったのが運の尽き.

https://github.com/k-mats/codeforces/blob/master/140/148C.cpp


148D

姫とドラゴンによるネズミを使ったゲーム.

姫が勝つ確率を求めよ,ということなので,数学の問題だなあ,と思いつつ試行錯誤していたところでタイムアップ.

ちょっとしたことに気をつければ,なんてことはない問題・・な気がする.

白ネズミwと黒ネズミb,およびそこから求められる確率をdpで保存していくと上手くいく?


148E

みてない


反省点

  • 初期化忘れに気付かずタイムロス

教訓

  • 初期化を忘れるべからず
  • 何をやってもpretest 1で通らなかったら問題文の読み間違いやコードのケアレスミスを考慮する