Dijkstra

ダイクストラ法 単一始点から全ての終点までの最短経路を求める ダイクストラの結果は全域木になる（最短経路木） https://snuke.hatenablog.com/entry/2021/02/22/102734関数詳細 DijkstraResult Run(wgraph& g, ll s, ll inf, ll mod = 998244353) 重み付きグラフ g に対して頂点 s から全ての終点までの最短経路を求める（到達できない頂点は inf を返す） 戻り値 DijkstraResult について min_cost[i]: パス s->i 最短経路コスト pass_count[i]:…

AtCoder Beginner Contest 252 です。 6完ペナ込み 97:22 でした（5ペナ）。 6完したのに激渋なんですが…。 A - ASCII code 問題文 文字コードが与えられるので変換して出力します。 fn main() { input! { n : u8 } println!("{}", n as char); } 提出 B - Takahashi's Failure 問題文 嫌いな食べ物のうち、1つでもおいしさ最大のものがあったら、嫌いな食べ物を食べる可能性があります。 先に $A$ の最大値を求めておいて、 $A_{B_i}$ が最大値と一致するか見たら良いで…

少し前になりますが、3月23日に、渋川よしきさんの著された「Goならわかるシステムプログラミング 第2版 」が発売されました。初版と比べてかなり加筆されておりパワーアップしているので、初版をすでにお持ちの方でもさらに興味深く読むことのできる内容に仕上がっている、というのが第一印象です。 残念ながら初版発売時に記事にする機会がなかったのですが、あらためて今回書評したいなと思いましたので、徒然書いていきたいと思います。 この本は実はシステムプログラミングの本ではないかもしれない 「システムプログラミング」とは何でしょう。正直私にもわかりません。その語をはじめに思い浮かべた人は、プログラミングという…

05/09(月) 午後2時前に起床。1時間ほど布団でゴロゴロした後、シャワーを浴びて購買に向かった。この時間帯、すでに購買のパンやおにぎりは売り切れている。仕方なくお菓子とカロリーメイトを買って、帰り道でコンビニに寄り昼食を確保した。 先週金曜日の配信アーカイブを改めて確認していると、チャットリプレイができないことに気づいた。設定を弄った記憶はなかったが、調べてみるとカット編集を行ったアーカイブはそれができないようになってしまうらしい。配信画面にコメントを表示するのはこれの対策という意味もあったのだと知った。昔は設定していたものの、いろいろソフトの連携が必要で面倒になり、最近は止めてしまってい…

05/02(月) 先週の週記を投稿してからの話。徹夜を決めた。ついでに新幹線の予定も早めることにしたので、時間的な余裕はすでにほぼなく、そそくさと出発。高校生の通学ラッシュと重なってしまい、駅から吐き出されてくる人々に逆らって歩くことになった。 仙台駅に着いて、朝食のパンをコンビニで購入して乗車。さすが朝早めの新幹線、さらに仙台駅始発ということもあってか、中はガラガラだった。 車内ではラノベを読んでいた。ふとTLを見ると、日曜日のOpenCup-Aが怪しいという話が流れてきた。詳しくは先週の週記に追記しておいた。解説のリンクをまだ手に入れられていないため、想定解がどのようになっているのかわから…

問題 atcoder.jp 解法の前のお勉強 辺のコストの持ち方以外は難しくない。制約的に、Dijkstra法を用いることで解ける。さて、問題はコストが負になりうるという点である。 Dijkstraのアルゴリズムは、負の辺があると動作しない。ならば、負の辺を消してしまえば良い。 具体的には、ポテンシャルという概念を導入する。 ここでは、ながたかなさんの記事とできるだけ同じ記法を使って説明してみる。下の参考文献にもリンクがあります。（感覚的には、最短経路の性質が壊れないように、適当な値を加えて辺を変える。多分) 頂点 を結ぶ辺を とする。各頂点ごとにポテンシャルを考え、ポテンシャル導入した辺をを…

かなり前に、DijkstraとWirthがAPLの話をIversonから聞いて「俺たちの目が黒いうちはこんな言語は絶対流行らせない」と言ったという話をどこかで読んだ気がしていてソースを探していたのだけど、なかなか見つからずに残念に思っていた。 DijkstraがAPLのことを嫌っていたのは結構有名で APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new genera…

ペナントの世界大会のみに登場するレア名字をまとめているページです。 オリジナル選手作成時の参考にどうぞ。

自己紹介 どうも、ainem(あいねむ)と申します。 子供の頃からずっとプログラミングに憧れたまま、始められずにいた昭和生まれの社会人です。（chokudaiさんとドンパ*1） ハッカーにあこがれるainem 奥さんの妊娠をきっかけに、隙間時間で2人でできる趣味を探していて*2、プログラミングを使ったゲームがあるらしいとatcoderを始め、今や1年以上続いています。 この度入緑をキメたので、僭越ながら記事を書かせていただきました。 ainem - AtCoder レートグラフ 効率的な学習方法は効率よくレートが上がっている人の記事を参考にしていただくことにして、*3 私は「いかに楽しく競プロ…

GCJ Round1Aに参加しました AB + c(部分点)で865位なので無事通過できそうです A Double or One Thing ある文字について増やした方がいいか？を考えます abならaabとしたほうが、2番目に来る文字がbからaになるので得です baならbbaとしたほうが、2番目に来る文字がaからbになるので損です このように辞書順で次の文字より小さいなら増やした方がよいです ただし、同じ文字が連続しているときはそれをまとめて増やした方がよい(aabをaaaabにする)ので、ランレングス圧縮をして文字を持つと楽です。(AC 05:43) B Equal Sum 初見であまり思い…

AtCoder Beginner Contest 246 です。 A - Four Points 問題文 長方形の3点の座標が与えられるので、残り1点を求めて下さいという問題。長方形の各辺は $x$軸か $y$軸に平行になっているので、必ず2点はペアになっているはずです。ということで $x_1 == x_2$ なら $x_4$ は $x_3$ と同じになるはずです。他の組合せも同じ感じで場合分けして書きます。 fn main() { input! { (x1, y1) : (i64, i64), (x2, y2) : (i64, i64), (x3, y3) : (i64, i64) } le…

はじめに こんにちは！東京大学きらら同好会です！ 当会初となるプログラミングコンテストはいかがでしたか？まだ解いてない方はこちらから解くことができます！ ※HackerRankにログインする必要があります www.hackerrank.comこの記事では各問題の解説をしていきます！ 問題文はコンテストサイトを参照してください。 目次 はじめに 目次 相性 時差 原稿 刺客 テント 巨大迷路町 カフェ カフェ2 無限ループ 天体観測 ともだち 進捗報告 えんそく 宿題