今日やったこと - わくのメモ

　今日もHCPCの活動に参加しました。AOJ Virtual Arenaを利用した練習会でした。

JOI予選の過去問ということで、見覚えのある懐かしい問題が並んでいました。

簡単です。4つと2つに分かれてますが、大したことはないです。全部足してからそれぞれの一番点数が低いのを引くのが良いかもしれません。

愚直にシミュレーションしてもO(NM)で済むのでそれでいけます。

白で塗る行数と、青で塗る行数を全探索しても十分間に合うので全探索をします。

時間がある程度経過したときに、住民の動きとしては「おしゃべりをしている」「右に歩いている」「左に歩いている」のいずれかです。方針は、時間が十分に経過したときに住民がおしゃべりをするポイントを予め確認しておいて、あとは重要人物が与えられた時間内におしゃべりポイントにたどり着くかを調べます。

実装が色々混乱して大変でした。慣れも必要だしミスを初めからしないようにするのが良いです。頑張ろう。

思い出として、最初にこれを見たときはシミュレーションをしたのを思い出しました。あの時は計算量を数えるという概念を持っていませんでした。

難しくてわからなかったです。危険な街を調べるのはBFS的なものだろうとは気付いたのですが、グラフを与えられたときのBFSがわかりませんでした。連結リストが必要と聞いたので、簡単な問題で慣れたらリベンジです。

この手の、重みの付いたグラフの最短コストで目的地に着くのは典型問題らしく、これも解いておかないと類題が出てもわからないので練習が必要です。