"コンテスト参加感想"カテゴリーの記事一覧
-
×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
-
三井住友信託銀行プログラミングコンテスト2019
順位: 827パフォーマンス: 1421新レーティング: 977差分: +885完
配点がABCと一緒だったのと、年内に水色なっておきたいんだけどなーという気持ちがあったので、初めてABC以外に参加してみた。
最初に思ったのが、コンテスト名長いし略せないーーー。
コンテスト毎にフォルダ作ってコードを保存しているのだが、フォルダ名とかブログの記事名とかどうしようかと迷う。
フォルダ名はAOJとかではURLを参考にしているので今回もそうしたが、ブログ記事はみんな略してないしsumitrust2019だとなんのこっちゃなのでそのままで。
中身の話だと、まともな解法で初めてEを通せたのが非常に良し。
かなりすらすら解けた。
頭が回る・・・!
こんな幸せな気持ちで解けるなんて初めて・・・。
もう何も怖くない!
と思ったら単純に簡単な問題だった。
A問題
かんたん。
4つの入力のうち3つが要らないなんてことが!?
かなり怪しんだけどやっぱり要らなかったね。
B問題
ほぼまんまの問題小学生の頃解いた記憶がある。
確か税込みの値段としてありえる値段には、数列として考えると増加値に規則性があったなーとか思い出していたが、今回はそこまで考えなくても良さそう。
切り下げだから割った値と+1した値を計算すれば十分かなーと思ったら良さそうだった。
余分な計算する分には問題ないと言い聞かせて、そこまで深く考えずに解けた。
C問題
ある数以上は絶対作れそうだなーと思ったが、その数どうやって求めようかすぐに思いつかなかったのでこの方針はパス。
個数決め打てば制約的にも問題ないなとなった。
これはある値を決め打って二分探索の経験が完全に生きている。
Cにしては難しいと感じた。
D問題
桁DPかぁ!?
と思ったけど桁DPにすると状態がかなり複雑になるのでは・・・?
桁DPしなくても全探索とかもっと簡単に解ける問題もあるんだよとABC114 C 755で学んだので、別の解き方を考える。
出てくる数字は10種類しかないから、O(10^3)ならlogとかNとかついても行けそう!となったので、000~999を全探索する方針にする。
ここで直近のコンテストの経験がまた生きる。
記事には解いた部分を書いていないが、ABC146 E Rem of Sum is Numで、「ある数が出てくるインデックスを記録する」という方針を解いたばかりだったのですぐに思いついた。
別にこの問題に限った方針ではないし、過去に何度か自力で解いているので直近で解いていなければ解けていないということはないだろうが、経験は力だなぁとかなり感じた。
左の桁から考えると、異なるインデックスから取った同じ数字は分けて考える必要がないので、数字を選ぶ際は次に選べる数を多くするように、なるべく左のインデックスから選ぶべき。
1桁目は、必ず左端なので、数が数列に存在するかどうかのみで良いのでO(1)。
2桁目は、1桁目より右側でなるべく左なので、upper_boundでO(logN)。
2桁目は、2桁目より右側に存在すれば良いので、upper_boundでO(logN)。
合計でO(10^3*log^2(N))。
N=30000のとき225000くらい。
解説でO(100N)とO(3N)で解けるよ!って書いてたうちのO(100N)に近いが、そうなら普通にlog入れてくるような気もするからどうなんだろう。
問題を見た時ちょっと難しそうだったので小休憩として、「確か上位入賞者は賞金あったな。上位は今どれくらい解いてるのかな?」と順位表を見に行ったら1人全完してて笑った。
化け物かよ。
E問題
ここまで32分。
うわ場合の数だうわああああああ。
ぼーっと考えてたらちょっとひらめいた。
前から考えて、その時点であり得る色の選び方を順番に掛けて行けば良さそうだなー。
試しに実装してみたらサンプルケースも合うし、提出したらACもらえた。
か、かんたん・・・。
ほんとに500点問題なのかと思わず確認したね。
後から知ったが、矛盾する入力で答えが0となるケースもあるらしい。
ありえる色の選び方を順番にかけているので、途中で0が入ればそれは0になるから問題ない。
別の実装だったらちょっと問題になるのかなーという感じはする。
「すべての人の発言が正しい」という文章は、答えが0でも良いと捉えるより、答えが0になるような矛盾がないと捉える方が普通だと思う。
F問題
ここまで46分。
残り90分以上!?
もしかして初全完!?
・・・残念ながらそんなことはなかった。
グラフで考える、場合分けも合ってる、T1が終わった後に2人の差がちょうど0だったら+-1が生まれる、とかなり惜しいところまで考察できてたと思うんだけど数学力が足りなかった。
ワンチャン小学生の頃なら旅人算チックに解けてた可能性あるが。
まず愚直にシミュレートしたら色々思いつくかなーと実装。
なんか奇跡的に通ったらいいなーと提出したらTLE+WA。
WAは見ないことにしてやっぱりTLEかーとなる。
これ提出した時点で残り20分切ってるんだよね。
考察にかなり時間取られたとは言え、愚直に実装する部分だけで少なくとも30分以上は取られているはずなのは非常に良くない。
愚直は頭の中か紙の上だけでやろう・・・。
愚直が終わってとりあえず場合分け。T1+T2でAとBが進む距離が同じなら無限に出会う。
T1+T2でAの方が多く進むのに、T1の時点でAの方が多く進んでいたら1回も出会わない。
n回目のT1の後に2人の差がちょうど0なら-1する必要がある。
ここから不等式書いたり色々したが、時間が残り少なくて色々ミスしてしまった。
ミスなくてもおそらく間違いだが、もっと落ち着けば解けたかなー。
後からYouTubeの解説を見てAC。
1回目のT1の後の時点をc、1回目のT2の後の時点をdと置くと、cから毎回d引かれていくというのがいまいちピンとこなかった。
進む距離がT1とT2で違うのに?というのが解決できなかったのだが、今考えてみると×2していることから、T1とT2の後のそれぞれの差を考えているわけじゃなく、T1の後の差のみを考えているんだなと気付いた。
とりあえず2人の差から考えるという部分だけ学んで、T1とT2を分けて考える方針で実装してみると見事に計算部分がほぼ同じになった。
不等式を解いている途中にも気付いたが、そもそも最初にT1+T2の時点でAがBよりも大きいと仮定しており、T1の時点の差は大きくなることはなくだんだん小さくなっていくので、T1の時点でBの方が小さければ必ず交差する。
それすなわちT2の方は考える必要がなく、×2するだけで事足りる。
まとめ
記事に考えを整理して文字に起こすと新たに理解が深まるの良いなぁ。
今回はFで2つも理解してしまった・・・。今回初まともな5完だが、やたらと簡単だったからなぁという気持ち。
5完なら青パフォーマンスくらい欲しいところだが、今回は水色パフォーマンス。
AtCoder Problem的にもかなり簡単だったのであまり達成感がない。
もうちょっと難しい問題で5完できれば達成感とともに水色いけるかな。
4完でもそこそこの速度なら後2回くらいで水色行けると思うんだけどどうだろう。
後2回くらいコンテスト開催して年内水色行かせてくれー。PR -
パフォーマンス: 1100
新レーティング: 889差分: +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のミスは二度としないという誓いのために個別に記事を書きます。
はー悔しい。 -
パフォーマンス: 1529
新レーティング: 853差分: +175
5完
申し訳程度に初5完。
申し訳程度に初水色パフォーマンス。
申し訳程度に緑になった。
Eで終了5分前にTLE3回出して終了17秒前に提出したのがAC。
ジャッジ中に終了通知が来て焦った。
EはACしたものの、いわゆる嘘解法ってやつな上にその嘘解法も未完成。
未完成なのは提出段階から分かっていたが、その部分直すのは時間間に合わ無さそうだったので、出さないよりも出した方がワンチャン!と思ったら通ってしまった。
後で(嘘解法を落とすのとは別の)ダメそうなテストケース考えてチェックしたら普通に間違ってる。
A問題
かんたん。
でも最後の中括弧間違えて消して提出しちゃってCE。
焦って再提出したのは次解くぞと開いていたB問題用のファイル。
つまりテンプレートをそのまま提出してしまった。
CEはジャッジに時間かかるし、テンプレートも入力形式も合ってなくてジャッジに時間かかるし、無駄に時間潰した+WA。
かなり凹んだ。
B問題
かんたん。
C問題
焦ったからなのかちょっと理解できなかったけど10分くらいでAC。
サンプルケース使って解くのはもはやただのパズル。
最初は以下のように考えていた。
町iから町jへの行き方はN-1通り。
それらは全て同じ確率のはずだから、iを固定してjをN-1回ループし、それぞれの距離の合計をN-1で割ったものをsumに足す。
町iをN回ループした後のsumが答え。
でも答えが合わない。
N-1で割るんじゃなくてNで割るようにしたらサンプル全部と合ってAC。
D問題
方針はすぐ立ったのに解き方がアホ。
解説PDFと同じように、n+2m=X, 2n+m=Yの連立方程式を立てた。
なんなら変数名まで同じだった。
そこからnを全探索した(?)。
どう考えても不定形の連立方程式じゃないので、解は一意に定まるはずである。
でも答えが何通りでMOD取るってことは、不定形のパラメータ付きの解になるんじゃないかと思い込み、nを1からXまで全探索した。
もちろんオーダーは計算して全探索にしたのだが、連立方程式を立てた意味が皆無である。
しかもひどいことに、係数2がかかる部分を勘違いして実装していて、全然気づかずに方針が間違っているのかと15分以上溶かした。
連立方程式活用してたらこんなことには・・・。
これ解いた時点で45分+1WA。
E問題
本番ACコード - スーパー嘘解法
スーパー嘘解法修正版(正しい嘘解法)
問題の嘘解法。
特に工夫するところも見つからず単純だけど難しいなぁという印象。
またお得意の問題理解ミスなのだが、「T-0.5分後以降に注文できない」を、「T+0.5分後までなら注文できる」と思い込んでいた。
もはや無茶苦茶である。
それに気付いたのが終了15分くらい前で、実装が大きく変化することはなかったものの、細かい部分はおかしかったり無理矢理だったりする。
無駄なソートをしていたり謎にdp[T]の値を使っていたり。
TLEしてるんだからせめてソート部分は消すべきだった・・・。
まずちょっとミスがあった状態でTLE(残り5分)。
ミス直して(時間に関わる部分は直していないので当然だが)TLE。
setをunorderd_setに直して、ソートされていないことに関わる部分も直してTLE。
unorderd_setの代入部分を参照変数に直してAC(残り17秒)。
以下色々書いて修正したけどそもそも方針が間違いだったというお話。
この嘘解法がTwitterでも報告されていたが、自分はその嘘解法すら未完成だった・・・。
未完成のスーパー嘘解法を嘘解法に昇華させる謎の考察だが、せっかく書いたので残しておく。
一番最初に考えたのは、「最後に注文する料理を決めてそれぞれに最大値求めたい!」というお手本のような方針だったのになぜこうなったのか・・・。
方針としてはDP。
dp[i分まで] = pair{おいしさの最大値, 今まで食べた料理の種類}
おいしさの種類がsetからunorderd_setに変えた部分。
iを0~T-1まで計算した後、全てのiに対して、dp[i]のおいしさの最大値+まだ食べていない料理の最大値を調べ、それの最大値が答え。
全体的には間違っていない(と思う)のだが、同じおいしさの時の処理をしていないのがダメ。
(2分, おいしさ2), (2分, おいしさ2), (4分, おいしさ4)という3つの料理があった場合、4分でおいしさ4を得る方法は、0,1番目を選ぶ方法と2番目のみを選ぶ方法があるが、最後に1つ好きなものを足せることを考えた場合、前者は+4できて後者は+2しかできないので、前者を選ぶべきである。
同じ美味しさだと処理しない実装なので、先に2番目が選ばれてていると間違えてしまう。
例えば、嘘解法のコードに[3 5 2 2 2 2 4 4]を入力すると誤った答えが出力される。(正:8, 誤:6)
これを解決するには、まだ選んでいない料理のおいしさの最大値を持てば良い。
が、それを確認するにはO(N)かかって辛いので、選んだ料理のおいしさの最大値を持つと良さそう。
選んだ料理のおいしさの最大値が小さい方が最後においしさが大きい料理を取れる。
あるいは、dpの情報を増やす代わりに、おいしさの小さい順にソートするのも良さそう。
こちらはあまり自信がないが、おいしさが小さい方から見るようにすれば、おいしさの合計値が同じ時に更新しなかった場合、おいしさが小さい料理が積極的に使われているはずである。
例えばおいしさ1,2,2,3,4,7からおいしさ7を作りたい場合、遷移をdp[i]=max(dp[i], dp[i-料理jの時間]+料理jのおいしさ)とする。
2を作る場合は、2のみ。
3を作る場合は1+2のみ。
4を作る場合は3+1が優先されるが、3には1が使われているので2+2。
5を作る場合は4+1が優先されて4+1。
6を作る場合は5+1が優先されるが、5には1が使われているので4+2を見るが、4には2が両方とも使われているので、3+4。
7を作る場合は、6+1が優先されるが、6には1が使われているので5+2を見るが、5には2が両方とも使われているので、4+3。
・・・とここまで書いて、使われているかどうかで優先されても選ばれないかもしれない可能性がありそうなので、うまく行かなさそうな感じがする。
ちょっとその辺の証明できるほどの実力はまだない。
素直に最大値持つことにする。
と言っても嘘解法でACしてしまっているので本当に正しいか分からない。
※正しくないです
F問題
ちょっと見たけど問題文の理解するよりE考えたほうが良さそうと思った。
初めて嘘解法って奴を通してしまった。
初の5完が嘘解法はちょっと嫌だなぁ。
実質4完である。
うまく行かないだろうなと気付いたものの、時間的に厳しそうでそのまま突っ走ってしまった。
Dの勘違いのタイムロスがなければ、最大値を持った正しい嘘解法はできてそう。
新ABC制覇してかなりコツ掴んできた感あったんだけどうまくいかないなぁ。
目下の目標は全体的な速度アップと間違った思い込みをなくすことだ。
今回嘘解法で不本意に緑になったが、その緑すら落とすようなことはないようにしたい。 -
パフォーマンス: 892
新レーティング: 687差分: +39
4完
Dに時間がかかりすぎた。
苦手だったわけではないが、単純に舐めていた。
真剣に解いていたつもりだけど真剣じゃなかったというのかな・・・。
後50分は縮められたはず。
A問題
かんたん。
B問題
かんたん。
C問題
相当悩んだ。
なるべく差が小さい2つの値の積でNを表せれば良いというまではすぐ分かった。
「同じ周の長さの長方形なら面積を最大にできるのは正方形である」というのはなぜか昔から何度も考えたことがあったので、この方針に疑いはなかった。
ただそれを全く実装できない!
とりあえずNを素因数分解して、あとはその組み合わせの積でなるべく差が小さくなるようにする、ナップサック問題的な問題なんじゃないか?とずっと考えていた。
でもそうするとおそらく間に合わないし、そもそもC問題レベルではないと思ったのでそういう解き方ではないと考えた。
あるときふと思いついた、「√Nから探索始めればいいじゃん!」と。
頭カチカチって感じ。
かなりの長時間考えていた気がするが、改めて確認してみると意外と20分しかかかっていなかった。
ここまで24分。
D問題
これ解くのにおよそ1時間!遅い!
算数の問題だな!と思って紙とペンで頑張ってみたのだが全く進まない。
小学生時代相当頭良かったので解けるだろうと高をくくっていたので解いている途中ずっとショックとも戦っていた。
"数学"ではなく"算数"だと完全に認識してしまっていたので、三角関数なんていう概念はなかったのが敗因。
なんとかして相似とか合同とかで解こうとしていた。
角度が30°とか45°とかで固定で、どれだけ溢れるでしょうとかが算数の問題で、サンプルの回答に無限小数らしき実数が出てくる時点で三角関数が出てくるのは明白だ。
サンプルを見るのが遅すぎたのもよくない。
なんならサンプルを見た後にも、今までの算数の思考が残りすぎて、「無限小数?なんで?どうやって出てくるの?長さの掛け算割り算で角度がそんなことになる?」となかなか理解できなかった。
それもあって三角関数使えると気づいてからもすんなりいかなかったが、それでも10分程度でACまで持っていけたと思う。
二分探索でも解けるみたいだが、角度ごとに溢れるかどうか計算できるならそんな遠回りせずに普通に最大角度求められるんじゃないか?と思う。
深く考えていないが、溢れるかどうかだけでも条件分岐が必要とは書かれていたものの、直接求めるよりは単純に計算できるんだろうか。
これを解いた時点で82分。
さすがにきつい。
E問題
Dを解けるはずという確信はあったので、Dを解いている途中にはちらっとしか見ていない。
18分弱で一応考えてみたが、さすがに無理だった。
消化コストAiと食べにくさFiを小×大となるようにソートするところまでは思いついたが、その先がうまくいかなかった。
完食にかかる時間XとFiのペアーをsetに入れて、最も大きいものを取り出してFi減らしてまたsetに入れて~というのをやろうにも、あまりにもKが大きすぎる。
Fiの最小公倍数を求めれば、全ての人が(LCM/Fi)回修行すれば、最初のsetの順番はそのままで全ての要素がLCMだけ減る!という方針が思いついた中では一番考えている感がある。
考えている感はあるが、Fiに10^6, 10^6-1があった時点で終わってしまうのでたいぶしょうもない。
あまり解放について調べていないのだが、答えを決め打ちして二分探索するっぽい。
その解き方自体はどこかでそういうのがある見たレベルにはあるのだが、詳しくは知らないので勉強ポイント。
F問題
未だに問題すら読んでいない。
これから算数の問題っぽいものも数学の問題と心構えて解きます・・・。
最近件の3完のEを解いたのだが、何も見ずに解けてしまった。
参加したコンテストのEで想定解が新しい知識を必要としないものは一番最初だけだったので、久々に自力で解けて嬉しい。
時間的にもそんなにかからなかったので、D解けてたらEも行けたかもなあと惜しい気持ちもある。
この3完は置いておいて、少なくとも練習だとEもたまにじゃなくて安定して解けるようにならないと始まらない感じがたいぶ出てきたので、頑張って経験積んでいきたい。 -
パフォーマンス: 1061新レーティング: 639差分: +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で理解が浅いまま進めてしまったこと。
三角形の構成条件なんて簡単やろと思ったら確かに簡単だったけど抜けてた。
やっぱり風邪が悪いよ風邪が!