ABC133 E - Virus Tree 2
解法
探索か何かをしつつ、今いる頂点について色を決ようとすると、その頂点から距離2以内で、すでに色が決まっている頂点がいくつあるかを調べる必要があり、とても大変です。
そこで、今いる頂点から行くことができる頂点について、色を決めることについて考えてみます。
上のような木について考えてみます。白い頂点が既に通過済みの色を塗られている頂点で、青い頂点が今いる頂点です(ここも色はすでに決まっています)。そして、クリーム色の頂点が、今から色を決める頂点になります。
3つのクリーム色の頂点に、順番に色を塗っていくことを考えると、
1番目の頂点には、2番目は
、3番目は
通りの塗り方が考えられます。
1番目の頂点は、白と青の頂点の分だけ色の選択肢がなくなり、2番目以降の頂点は、今塗ったクリーム色の頂点の色だけさらに選択肢が消えていきます。
同様のことがこの後も続きます。
例えば、先ほどの図から実はさらに頂点が存在していたとします。先ほど、青い頂点にいる際に、クリーム色の3つの頂点に色を塗りました。そして、今緑色の頂点に移動してきたとします。
緑色の頂点から行ける、親を除く頂点について色を塗ります(今回は水色の頂点になります)。
この場合も、水色から距離2以下の頂点のうち、すでに色が塗られているのは、今いる緑の頂点と、その親である青い頂点の2つのみになり、色塗り方は1番目の頂点が、2番目が
、3番目が
通りとなります。
ということで、
DFSか何かで頂点を探索しつつ、今いる頂点から次に行くことができる頂点について、
ただし
は
以上(次に行くことができる頂点数
)以下の任意の数字
をかけていけばよいです。
が、一番最初の根は通りであることと、そこから行ける頂点のみ、
であることに注意しなければなりません。
これを繰り返していけば、答えを求めることができます。
感想
この問題結構面白いと思いました。
コーナーケースに引っかからずに書けるようになりたいですね(今回はサンプルが合わないのでいいのですが…)
ABC133 D - Rain Flows into Dams
解法
番目の山に降った雨の量を
とします。
すると、以下のような式が成り立ちます。
ということで、これらの式をまとめてを求めることを考えてみます。
上の式から順番に、式1,2,...Nと名付けると、
式番号が奇数のものはそのまま、偶数のものには両辺に-1をかけてから、全てを足し合わせてあげます。すると、
となり、左辺をまとめると、
となります。
よって、結局について、正負を反転させつつ足し合わせていくだけで
を求めることができます。
そのほかの答えについては、最初の式に一つ一つ当てはめていけば良いです。
感想
この手の問題はとりあえず立式することが大事そうです。焦ってよくわからない方向に行きかけたのですが、今回は冷静に考え直すことができました。
ICPC2019模擬国内予選参加記
ICPC2019模擬国内予選に参加しました。
いろいろあって今年のチームメンバーは
Tsuzu君(@Wp120_3238)とmi_tesseract君(@mi_tesseract)です。
チーム名はCoprimEです。
コンテスト中の動き
ざっくりと…
開始直後
予定通り、自分がAを解き、残りの2人がB,C以降を読みました。
5分ぐらいでA問題を解き、自分も合流しました。
BをTsuzu君がやり、Cをmi君がやっていたのですが、とりあえずCはある程度いけそうな雰囲気で、Bは自分が慣れている系だったのでTsuzu君にDへ行ってもらい、バトンタッチ。 40分前後でACしました(intとboolを間違えてバグらせました)。
その後、Dは編集距離のDPをいじればよさそうとのことだったので、Cを飛ばしてDの実装へ行きました。自分はCへ合流しました。
開始から1時間程度
Cはコーナーケースが怖いが場合分けをすれば良さそうとのことだったので、Dの実装をいったん止めてCの実装をすることにしました。→WA。
のコーナーケースがあったので、それを追加すると無事にAC。Tsuzu君に再びDの実装をしてもらい、僕とmi君でE以降を読むことになりました。
その後...
Dのサンプルがシンプルな実装だと合わず、無理やり合わせにいく形でサンプルを通しましたが、もちろんWA。
E~Hを読み、Eを解くことになりましたが、Eを3人でフローっぽい！と適当な決めつけをし、考察が明後日の方向に行きました。
結局、Dのコーナーケースと、それっぽい解法まではTsuzu君が思いついたので実装をしてもらったのですが、数分間に合いませんでした。
その解法自体は正解で、終了後他のチームのコードによるアウトプットとの一致を確認しました。
結果
3完で全体47位でした。今回は僕らのチームの上に2チームいたので、このままいくと予選落ちです…
jag-icpc.org
反省点
声をかけられていない
C以降のそれぞれの問題について、数人ずつで対応できたといえばできたのですが、それでもお互いが遠慮していたように思いました。
最後、E問題の考察が終わっていないにも関わらず、実装を始めてしまった結果D問題が間に合わなくなってしまったので、もっと声を掛け合った方がいいのかなと思います。実力が足りない
実力が足りません。DやEをすぱっと解けるようになりたいです。
とりあえず国内予選までにできるところまで精進したいです。
結論
頑張ります(頑張ります)
目標は大学内で2位になり、無事に通過することです…
AOJ 2298 - Starting Line
解法
が間に合うことに注目すると、任意の距離1の区間
区間それぞれについて、速度
で走るか
で走るかを決めていけば良いです。
にんじんを食べるタイミングは貪欲に決めることができ、
今スピードアップしてなければ拾ったタイミングで食べる
今スピードアップしてれば、とりあえずキープをしておく
今スピードアップしていてかつ、キープが満タンであれば、仕方なく食べる
の3択になります。
今いくつのにんじんをキープしているか、そしてスピードアップをしているならば、それが終わるのは距離がいくつの時か、を更新しながら、速度で走る距離と
で走る距離を調べていけば、その距離をそれぞれの速度で割ったものの和によって答えが求まります。
感想
貪欲っぽい、というところからいろいろ迷走した結果とてつもない時間がかかってしまいました…
丁寧に調べることと、制約に注目することを忘れないようにしたいですね。
