[C#] J – 地ならし [第一回 アルゴリズム実技検定]
第一回 アルゴリズム実技検定 J – 地ならし を解きたい C# で参加した第一回 アルゴリズム実技検定(PAST)は、AからI問題まで解けました。J問題は検定中に解けそうで解けなかった問題なので改めて解いてみました。 [C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り │ Web備忘録 AからIまで上の記事で解いてみたコードがあります。 ではJ問題を解いてみます。コー […]
アルゴリズム
AtCoder Beginner Contest 159 に参加した記録
AtCoder Beginner Contest 159 に参加した記録 AtCoder Beginner Contest 159 – AtCoder ABC159 に参加しました。結果はABCDの4問ACでした。 今回はD問題が20分しないで解けたので簡単な部類でした。E問題は時間をかけましたが実装しきれませんでした。 前回のAGCに続き、一応レート微増でした。とりあえずWA0でしっ […]
AtCoder パナソニックプログラミングコンテスト2020 に参加した記録
パナソニックプログラミングコンテスト2020 に参加した記録 前回のARC相当のコンテストはパスしていたので、水色チャレンジ1発目のコンテストでした。 結果ABCDの4問ACでしたが、C問題でやらかして6WAくらい重ねました。 全体的な印象として今までにない形式の問題が多かった風に思います。 やらかしたおかげでパフォーマンスは水色1420くらいでしたが、無事水色コーダーになれました!! A […]
AtCoder Beginner Contest 158 に参加した記録
AtCoder Beginner Contest 158 に参加した記録 AtCoder Beginner Contest 158 – AtCoder ABC158 に参加しました。結果はABCDの4問ACでした。 今回はD問題が15分ちょっとで解けたので簡単でしたたぶん。最近はE問題に結構時間を使えるのですがなかなか解けないです。 ですが、なんだかんだで順位がいつもよりよくて結構なパ […]
AtCoder Beginner Contest 157 に参加した記録
AtCoder Beginner Contest 157 に参加した記録 AtCoder Beginner Contest 157 – AtCoder ABC157 に参加しました。 結果はABCDの4問ACでした。事前の無事Dまで解けました。D問題よりC問題に苦戦しました。 C問題に2回WAを食らいました。 結果は パフォーマンスが1400くらいの水色、レーティングやや増でした。前回 […]
AtCoder Beginner Contest 156 に参加した記録
AtCoder Beginner Contest 156 に参加した記録 AtCoder Beginner Contest 156 – AtCoder ABC156 に参加しました。 結果はABCDの4問ACでした。今回はやらかしていません。無事Dまで解けました。全体的に数学チックな問題が多かった印象です。 E問題は30-50分くらいこねくり回しましたが。難しかったです。 パフォーマン […]
AtCoder Beginner Contest 154 に参加した記録
AtCoder Beginner Contest 154 に参加した記録 AtCoder Beginner Contest 154 – AtCoder ABC154 に参加しました。 結果はABCDEの5問ACでした。前回と同じく、全体的に優しい難易度のコンテストという印象を持ちました。累積和(もしくは尺取り法)、桁DPの典型問題がありました。 E問題が桁DPで解く問題だったのですが、 […]
[C#] ベルマンフォード法で単一始点最短経路問題を解くための実装方法
ベルマンフォード法とは ベルマン–フォード法 – Wikipedia ベルマンフォード法はダイクストラ法と同じく、単一始点の最短経路問題を解くためのアルゴリズムの一種です。開始点からすべての点への最短経路を求めることができます。 ダイクストラ法との違いは以下の2点です。 計算量はダイクストラ法よりもベルマンフォード法のほうが大きい。 ベルマンフォード法は負の重みを扱える。 ベルマンフォ […]
[C#] セグメント木を実装してみる
セグメント木とは セグメント木は名前の通り区間を扱うのが得意なデータ構造です。中身は完全二分木であり、区間の持つデータを管理します。 要素8件からなる配列のデータについて、セグメント木は具体的には以下のような形になります。 各ノードの中の数字は配列の区間データを格納します。 上記のような二分木のデータ構造を使うと、区間に関するクエリ(データの更新、取得)を計算量 O(log N)行えます。 なにが […]
AtCoder Beginner Contest 152 に参加した記録
AtCoder Beginner Contest 152 に参加した記録 2日連続のコンテスト参加でした。結果は残念ながらABCの3問しかACできませんでした。 前回ABCが5問ACしたことを考えると大きな落ち込みです。D問題は解けなければいけなかったです。 とりあえず問題を振り返ります。 A – AC or WA A – AC or WA 高橋君は、プログラミングコンテス […]