グラフ理論
この記事では、先日行われたyukicoderのコンテストで出題された、No.416 旅行会社 - yukicoderという問題の解き方とその実装を、学習の記録も兼ねて示します。コンテスト中にはこの問題を解けなかったのですが、ほかの方が書かれた解説等を踏まえて、ようや…
ふと思い立ち、Prim(プリム)法とKruskal(クラスカル)法をPython 3で実装しました。これらは無向グラフの最小全域木を求めるアルゴリズムであり、競技プログラミングでも用いられることがあるようです。この記事では、学習の記録を兼ねて、最小全域木や上…
引き続き、私はAtCoderの過去問を解き進めています。この記事では、その一環として私が取り組んだB: 道路工事 - AtCoder Regular Contest 032 | AtCoderという問題について、それに対するいくつかの解き方と解答例を、学習の記録を兼ねてまとめておきます。
先日、私はCodeforcesで開催されたIndiaHacks 2016 - Online Edition (Div. 1 + Div. 2)というコンテストに参加しました。この記事では、私が制限時間内に解けた問題の一つである、B. Bear and Compressingという問題について、その解き方とPython 3(ただし…
最近、私は主にAtCoderやyukicoderの問題を少しずつ解いています。この記事では、今日私が解いたB: バウムテスト - AtCoder Regular Contest 037 | AtCoderという問題の解き方およびPython 3の解答例を、学習の記録を兼ねてまとめておきます。
グラフ理論における単一始点最短経路問題を解くアルゴリズムとしてはDijkstra法やBellman-Ford法が挙げられますが、Shortest Path Faster Algorithm (SPFA)もそのようなアルゴリズムの一つです。この記事では、SPFAの概要について述べるとともに、そのPython…
最近、私はAtCoder Beginner Contest (ABC)およびAtCoder Regular Contest (ARC)の過去問を解き、競技プログラミングの練習を行っています。その一環として解いたC: 友達の友達 - AtCoder Beginner Contest 016 | AtCoderという問題について、この記事ではそ…
競技プログラミングにおける実装力の強化とアルゴリズムの学習を主目的として、AOJ-ICPCを利用して、ICPC・JAG非公式難易度表に挙げられている問題に取り組んでいます。現時点ではおおむね難易度100-150程度の問題を解いているところです。この記事では、そ…