競プロ日記

差分: +36

3完
3完再び・・・。
またこのレベルでレート下がるのか・・・と思ったけど下がらなかった。
ちょっとDが難しめだったみたい？
みんながどこで間違えたか分からないからどこがネックなのかは分からないが、自分のミスはこの問題に対するものではなく競プロ全般に対する知識が甘かったせいなので、たまたまみんなが解けなくてよかった。
それを除いて今回も細かいミスやらかした。
私の人生は常にミスとともにあることを再認識した。

A問題

かんたん。めんどくさい。
最近この手の問題は連想配列を使うことにしている。
問題文ではシングルクォーテーションで囲まれてて少しむっとなりながら全部手打ちしたが、置換とか使った方が良かったかな。

B問題

このループする系でかなり悩んで結局スマートに実装できなかったのがあるのだが、今回はそんなことなく簡単だった。
かなり悩んだ問題が競プロだったかどうかも分からないが、足して余り取って足してってしてたら元に戻っちゃってうわあああってなったの思い出す。
他の人の解法で見たが、Z超えたら26引くの方が簡単だったな。

C問題

びっくりするくらいすぐに二分探索だと分かった。
成長ポイント。
こっちはめぐるちゃんに二分探索教えてもらってるんだが？そんな問題でどうにかなると思ってるのか？
るんるん気分で15分溶かした。

問題文読んで二分探索と認識
+30秒

入力とか二分探索部分とか全体の実装
+2分

d(N)は十進表記での数・・・？それNと違うの？Nは何進法？よく見たら桁数だった。
改行位置の妙。
+1分

実装終わり！
・・・サンプルケースの計算が終わらない。
途中経過とか色々出力してmid=(ok+ng)/2であるべき部分を、mid=(ng-ok)/2にしていることに気づく。
+10分以上

mid=(ok+ng)/2よりもmid=(ng-ok)/2+okの方がより直感的だなと感じる人間なので、その感性と普段mid=(ok+ng)/2で書いてるのがすごく悪い感じに合わさってしまった形。
せっかく二分探索がすごく簡単になるように教えたのに、midの計算間違えるような人は知りませんってめぐるちゃんに言われそう。

D問題

あーうんうんグラフの探索ね。
色数は必ず二色でいけるのでは？と謎なこと思いながら木ってなんだっけと調べ直す。
木ってこんなんだっけと思いながら色数は頂点に集まる辺の数だなと分かる。
彩色する問題だし深さ優先探索でいけそうだ。
グラフの実装もだいぶ慣れてきたし特に確認もせず最後まで実装しちゃったが、サンプルケースは合ってるし提出したらTLE+MLE+RE。ひええ。
3つくらい解法試したが全部だめ。
詳しくは次の記事に書く。
結局はdp[10^5][10^5]の配列を作ったのが間違いで、mapに入れたら通った。
方針も実装も間違っていなかったのが悔やまれる。

E問題

え、うそなんでD解けないの・・・と絶望しながら見た。
うーーーーーん、難しいのか簡単なのか分からない。
こういう問題は手を出さない方が良い。

コンテスト終了後に軽く解説を読んだだけでは理解できなかった。
-1すれば個数を考える必要がないというのはなるほどという感じだが、何通りかを計算するのはどうやるんだろう？

ちなみにEの方が難しい問題は参加したコンテストでは初。

F問題

全く見てない。
コンテスト後に軽く解説を読んだら結構すぐに分かった。
本番でも(Dさえ解ければ)解けたかも？

1が続く部分では、多少損しても1の開始地点近くから始めないと1の連続を飛び越えることができないので、その辺どうしようというのが第一感想。
よく考えてみれば、なるべく多く進むようにして1が連続する手前で進む数を調整して例え1しか進めなくても良いとする場合と、何らかの良い感じに1が連続する手前に止まれるように進む方法を考える場合とでは、移動するサイコロを振る総回数は変わらなさそう。
どこで止まるべきかを再帰的に考えていくと、[0*a][1*b][0*c]みたいな1を0で挟む列になって、aの値はなるべく多く進むようにするかそうしないかでは回数的には一緒だなってことになる。
ならない？

回数求まったら、1の手前まで6,6,3みたいに進んでたのを3,6,6にすれば良いので、今度は再帰的の逆に一番短い[0*a][1*b][0*c]から増やして考えていくと、難しそうだなーってなる。
短い列から考えていくの再帰的って言うのか？
難しそうだなーってなりながらも、後ろから大きくすれば良いんだなと気付けた。
ってこれさっきやったやないかーいってことで、後ろからなるべく多く進めば良いと。

本番思いつけるならこの解法の可能性が高いが、この貪欲法よりもグラフ的な解法の方が勉強になるなぁと感じた。
マスXから行けるマスはX+1～X+Mなので、Xからそれぞれに辺を張ったグラフとして考え、各頂点からゴールまでの最短経路を考える。
ここまで考えられたらRMQ使えそうっていうのは分かる。
辞書順最小にしたいので、振る回数が最小になるものの中から一番手前にあるものを選んでいく。

この既にある情報を使ってグラフを作成する、というのはかなり身につけたい内容。
ABC143 E Travel by Carでも出てきたテクニックで、次のレベルに進む第一歩という気がしている。

ちなみにEでも軽く解説を読んでるが、参加したコンテストが終了した後は解けた解けてないもうすぐ解けそうに関わらずとりあえず軽く解説を読むことにしている。
結局時間内に解ききらなければいけないので、このレベルの考察をするためにはこの問題のこの部分が無駄だったという感覚を磨きたいから。
今の所ミスが無駄だったで終わってるのが悲しいところ。


そんな感じでまた3完。
今回のDのミスは二度としないという誓いのために個別に記事を書きます。
はー悔しい。