little star's memory

競プロの参加記など

AtCoder Beginner Contest 184

ぐわーーーーー

開始40分時点で1完だったパナソニックコンを思い出す。久々に大事故を起こした。最終的にABCEの4完だった。

昨日上げたレートがすべて溶けた。

コンテストページ

以下は参加した感想。

A - Determinant

答えが書いてある。

B - Quizzes

書いてある通りにやる。

C - Super Ryuma

やりたくない見た目をしている。1手で(r1,c1)から(r2,c2)に移動できるかを判定する関数isOne(r1,c1,r2,c2)を用意していたけど、これをisOne(r1,r2,c1,c2)として使っていたことに終了直前で気づく。1分前にAC

位置が等しいときは0回、isOne(r1,c1,r2,c2)がtrueのときは1回。グリッドを市松模様に塗って(r1,c1),(r2,c2)が同じときは2回。あとなんかがちゃがちゃ条件を入れて2回かを判定する(忘れた)。そうでないときは3回でできる。

D - increment of coins

$e _ {i,j,k}=\frac{i e _ {i+1,j,k} + je _ {i,j+1,k} + ke _ {i,j,k+1}}{i+j+k}+1$という式を立てて、$e _ {A,B,C}$を求める。

サンプル4が合わなくて、小数誤差のせいだと思ってたけど、式が間違っていた。冷静に考えれば直せたけど、他の問題も破滅していたため…。

E - Third Avenue

BFSをする。各英文字について位置のリストを作っておく。英文字の位置にたどり着いたら、そのリストにある座標へワープしていく。

これだとワープが大量にあるときにやばそうだなーと思いつつも提出したらやっぱりTLE。そこで一度ワープを使ったらそのリストを削除することにしたら通った。

2151msだけどもっと高速化できないかな。

F - Programming Contest

順位表みたらかなり通されてたから簡単なのかなーと思ってた。

見るとN≦40でナップサックっぽい問題だから、半分全列挙であることはすぐにわかった。

が、半分全列挙を使ったことがないのでおわってしまった。

本番ではD - ナップサック問題のコードをひたすら貼り付けてたけど、どうやっても2ケースTLEする。

アルゴリズムを勉強してないつけが来てしまったね。

いやだ!ボクは勉強したくない!ただゲームがしたいだけなんだ!