草体にぼ日記

だらだらと

2020/02/21 ,22 精進録

2月21日,2月22日のブログ

今日学んだこと

  • ダイクストラ法は、負の辺がない時に使える。計算量は頂点の数に依存。(頂点一つずつ最短距離を求めていくため)
  • BFSとダイクストラ法、どっちもqueueを使うっていう意味では似ている気がした。(辺に重みがないのはBFS?)
  • ダイクストラ法はdijkstra法なので、vimでjkでノーマルモードに行くように設定しているとイライラすることになる。
  • ダイクストラ法は、ある頂点からの他の頂点への最短距離を求める方法で、全点間の最短距離は違う方法で求める

まえがき

天才になれる気がしてきた。 今日の夜のコンテストではまだ成果出ないだろうけど今後が楽しみ

昨日2月21日は、友人にニトリに連れて行ってもらいました。

3m40cm程度の突っ張り棒を探していたのですが見つかりませんでした。

購入したホワイトボードを使って、キャスで姿を映して数学の問題を解く。とか言う遊びもしていました。

ABC112 D- Partition

[最大公約数]

昔解いたことある問題ですね。解けませんでした えーん 2019年12月12日の記事 ここに解き方載ってます(偉い)

ABC067 D- Fennec VS. Snuke

[ゲーム、幅優先探索,queue,キュー,BFS]

ときかた

1を根とした時の各頂点への距離と、nを根として見た時の各頂点への距離を比較する。

前者の方が小さい(=も含む)フェネックが塗りつぶせるマスで、後者が小さいときすぬけが塗りつぶせるマス(敬称略)

頑張って入力からグラフを構築する(これはダイクストラ法の勉強で出来るようになりました。)。

その上で、BFSをして根からの距離を作って行って勝ちました。

めっちゃWA出しちゃったんですけど、なぜWAが出たかと言うと

フェネックが塗れるマスの数とすぬけが塗りつぶせるマスの数が一緒の時の処理を間違えました。

つまり、フェネックが3個塗って、すぬけも3個塗る。ってなったとき、フェネックはもう塗れないから負けなんですけど、フェネックの勝ちにしちゃってました。

ダイクストラ法の問題

第7回二本情報オリンピック予選(オンライン)

僕の提出AC(写経した後にもう一度自力実装した)

ダイクストラ法のやり方がなんとなく染み込んできました。

あとがき

ダイクストラ法での解き方分からん!ってときに、フォロワーが何回も助けてくれて泣いちゃった

(ってか俺がダイクストラで解いた人いたらコード見せて〜〜!って行ったらわざわざ書いてくれた…)