競プロ日記

差分: +106

4完
1週遅れになってしまったからコンテスト終了後急いで書いている。
風邪を押して参加したけど最低限4完できてよかった。
ちなみに月曜日から5日間熱が出て、書いている今も咳はかなりひどい。

A問題

かんたん。

B問題

全探索に苦手イメージがあるものの、問題文に全探索してねと書いてあったのですぐに分かった。

C問題

ちょっと前のFにもあったスライム問題だ！
解説見ると少し難しそうなことを書いているが、1つ前の要素が異なれば答えに+1を繰り返していけば簡単に解けた。

D問題

三角形を作れる条件を正しく把握していなかった。
風邪が悪いよ風邪が。
紙に書いて把握し直してからは5分くらいで解けたイメージ。
ここまで44分。

E問題

これは解けても良かったなぁ。
燃料1回でどこまで行くべきか、をうまく表せなかった。
AからB、BからC、CからDのルートでA→Dを1回の燃料で行けるとすると、Bまで行った場合の残り燃料と、Cまで行った場合のBで補給した場合の残り燃料と補給しなかった場合の残り燃料と、Dまで行った場合のCで補給した場合の残り燃料とBで補給した場合の残り燃料と補給しなかった場合の残り燃料と・・・と、何通りも考えないといけない！どうしよう！が終始抜けなかった。
想定回答はワーシャルフロイド2回らしいが、最短経路求めてから最短経路求めるのは意味分からんけど頭良い。
言われてみれば確かにこういう何通りも道筋があるものを解けるのが最短経路問題だ。
結局補給すればその時点で燃料はMAXになるので、補給した後にいくつか消費した分の燃料を記憶するのではなくて、前回補給した場所から次にどこで補給できるかをグラフで全て記憶すれば確かに全通りを網羅できる。
この問題は解ける可能性十分あったと思っていたが、書いていたらグラフをどういうところで使えるか本当に知っているか？と問うてる問題に見えてきた。
だとすれば、間違いなく経験不足でグラフに苦手意識のある今解けなかったのは当然かもしれない。
ワーシャルフロイドは問題を解いた経験はないものの一応知識としてはあったのだが、今回は問題を解いたかどうかの経験はあまり関係なさそうに思える。

F問題

なんか解けそうだなぁと思いながら色々考えてみたがなんか解けなさそうだなぁになった。
全ての数字を横に並べ、同じ数字があれば上に重ねていくような図を想定し、だるま落としのように下から抜いていくような考え方かなぁと思って進めてみたものの、この形だと抜ける回数までたどり着けなかった。
問題文の「選び、食べる」の言葉選びのセンス○。


今回の反省ポイントはDで理解が浅いまま進めてしまったこと。
三角形の構成条件なんて簡単やろと思ったら確かに簡単だったけど抜けてた。
やっぱり風邪が悪いよ風邪が！