読者です 読者をやめる 読者になる 読者になる

Codeforces Round #406 (Div. 2): C.Berzerk

問題

codeforces.com

解法

終点(x=0)から逆に辿って行く動的計画法

Mortyにx=0で手番が回ってくる(つまりMortyの敗北)前の手番では、Rickによってモンスターはx=n-s[0][i](ある0<=i<k1)から遷移してきているので、その座標にRickの手番が来た時はRickの勝利である。その座標に辿り着く場合は

①その座標がスタート地点

②Mortyの手番でx=n-s[0][i]-s[1][j](ある0<=j<k2)から遷移してきた

の二通りが考えられる。

②の場合は、問題の前提から、Mortyによってモンスターがx=n-s[0][i]へ遷移するのは他の全ての手もMortyの敗北である時だけと分かる。つまり、x=n-s[0][i]-s[1][j]からのMortyによる遷移はx=n-s[0][l](任意の0<=l<k1)のいずれかであることが保証できれば、x=n-s[0][i]-s[1][j]の座標でMortyが来た時は敗北する。ここまでを終点をx=n-s[0][i]-s[1][j]にして繰り返す。

終わったら、Rickにx=0で手番が回ってくる場合でもう一度計算をする。

確定されなかった点はLOOPになる。

 

ソース

 

 

 

参考

kimiyukiさんの実装を参考(というかそのまま)にした。

Codeforces Round #406 (Div. 1): A. Berzerk · うさぎ小屋

c++の論理否定!の代替表現のnotを初めて知った(小並感)

CとC++の演算子 - Wikipedia

POJ2104:K-th Number

2104 -- K-th Number

蟻本の3-3の問題。

非常に理解に時間がかかった。

bが1000の時は最初の提出ではACされたけど、その後の提出では何故かTLEになったのでbを調整した。

 

ABC001B

放置しっぱなしなので寂しいのでとりあえず更新。

今日はc++以外ほとんど書けない(c++も怪しいが)自分に危機感を感じてpython3をかじった

 

abc001.contest.atcoder.jp

 

print('%02d' % (m//100))  の部分は print('{0:02d}'.format(m//100))でも通る。

いずれの場合でも02dを2dにすればゼロスペースで埋めるのではなく半角スペースで埋まる

算数レベルの問題だけど、とりあえずのために更新

2016年ICPC国内予選参加記

2016年度ICPC国内予選にチーム「RINKAKU NO DANPEN」で参加して来ました。

私自身は競プロ歴が半年にも満たないレベルのひよっこで、競プロを知ったのが去年の11月、atcoderのABCをある程度真面目に取り組み始めたのが3月後半、ICPCの存在を知ってAOJと蟻本に時間を充て始めたのが5月からという経歴です。

チームは頼み込んでconf君(@confused_uec)、ふーらくたる君(@fooractal)と組ませてもらいました。

 

5月~前日

5月半ば辺りから同大学の別のチームの方も呼んで3時間3人で一つのPCだけで解くというICPCと同じ形式(2台持ち込んで、一人が一台に打ち込んでる間はもう一台は操作禁止みたいなこともしましたが)で毎週練習会を行っていました。チームメイト二人はICPC経験者だったので色々手取り足取り教えてもらって申し訳なさと感謝しかなかったです。

一週間前の練習会はある年度のICPCの問題セットで解いてみたり、前日は本番環境で解いてみるなど本番が近づくにつれ本番を意識した練習をしていきました。

f:id:llll_nosi:20160625040305p:plain

▲色々犠牲にした結果(1万ポイント行きたかった..)

 

当日

リハーサルは4完2位でした(私は特に何もしていない)

当初の作戦は、まず自分がAとBを倒してる間にconf君がC以降の幾何を、ふーらくたる君がC以降の他の問題を考えるというものでした。

しかし、A問題を瞬殺できると判断したconf君がまずAを6分でAC(はやい)、その間に自分がBを見て二人がC以降を見る態勢に。

Bはアルゴリズムは割とすぐに分かったけどコーディングを始めるとプレッシャーで頭が真っ白になりバグらせてしまいました。conf君に引き分け時は一番最初にやった方がいいとの助言を頂きとりあえずサンプルのバグを片っ端から取っていってなんとか開始46分でAC。コーナーを全く考える余裕がなかったので通ってよかった..という気持ちが大きかったです。

その後Cを14分でconf君が解いて、D以降を残り2時間で考えるという段階で詰まってしまいました。

私はグラフと幾何の問題の経験がほとんどなかったのでそれっぽい知識が必要なさそうなDを考えて、終了1時間前頃に消せるだるまのペアの両端の差が1以内の時だけ再帰で潜って、その種類の消せるだるまのペアがなくなったら、そうでない消せるだるまのペアを最後に一度に消すという方法を思いつくも証明も説明もうまく出来ず。しかも疑似コードの実装すらどうにもならなくて、最後20分ぐらいでconf君になんとかある程度趣旨伝えて実装を頼むもタイムアップ。

結果はABCの3完でした。

 

反省

まずBで詰まらせたのがダメでした。正直プレッシャーは慣れの問題と思っているのである程度仕方ない部分もあるとは思いますが..

(二番目の候補者を求める時に後でソートしてから二番目を取ればいいと聞いてマジかと思ってしまった)

次に、幾何とグラフの知識がない故にその系統の解法を聞いてもあまり理解できなかったり、Dの実装の丸投げをするなどの力不足が甚だしかったです。

チームの問題と言うよりも、まず協力体制を敷けるだけのレベル差を埋められてないことをひしひしと感じました。

 

感想

アジア予選へ通れなかったのがとにかく悔しいです。自分は院進はしないつもりなのでチャンスが後一回だけというのが厳しい。

後、本番が近づくにつれ問題数を積むことばかり考えて解き終わった後の別解の模索や綺麗なコードにするための見直し、また他人のコードを参考にすることをおろそかにしていってしまったので、自分のICPCが終わった今伸び伸びとしてこれらもちゃんと行っていこうと思います。

来年までにもっと鍛えて、実装力・思考力共に身に着けたいと思います(具体的には黄色くらい..行けたらいいな)

後言語能力(日本語英語問わず)