読者です 読者をやめる 読者になる 読者になる

湖の大きさを列挙する

問題 { {0, 2, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {0, 1, 0, 1} } が与えられる。0の部分が湖で、縦横斜めで0が連なっている所は同じ湖とする。全ての湖のサイズを列挙する問題。 ソースコード

再帰を用いて階乗を計算する Hacker Rank

問題 Programming Problems and Competitions :: HackerRank ソースコード

セグメント木を用いてRMQを実装する

セグメント木とは セグメント木とはある区間における状態を保持させておくためのデータ構造である。 区間を表すそれぞれのノードに様々な値を保持させておくことで、いろいろな機能を持つ木を作成することができる。 RMQとは Range Minimum Queryとは、配列…

ユークリッドの互除法を用いて最大公約数を高速に算出する

整数a, bの最大公約数を求める。 2つ整数a, bの最大公約数はユークリッドの互除法を用いる事で高速に算出することができる。 ユークリッドの互除法とは ユークリッドの互除法とは 2つの自然数a, b(a >= b)の最大公約数は、a, bの余りをrとした時にbとrの最…

順列(Permutation)のクラスを作る

順列とは nPkと表しn個の中からk個選んで並べる(順序を考慮)通りを算出するもの。今回は、全ての通りを列挙するクラスを作成する。 順列を作るメソッド 全体

Union-Findを用いて2つの要素が同じ集合に属してるかを高速で判定する

Union-Findとは Union-Findとは、2つの要素が同じ集合に属しているか否かを高速で判定することを実現するデータ構造である。Union−Findは、様々な実装パターンが存在するが木構造を用いた物を考える。また、Union-Findはその名前からも分るように以下の2つ…

bit操作と深さ優先探索の全列挙を比較する

問題 http://abc045.contest.atcoder.jp/tasks/arc061_a 解き方 全列挙できるか 全ての数字と数字の間に対して、「+」を入れる場合と入れない場合で全列挙。文字列の長さがNの場合、「+」を入れることができる箇所は全部で(N - 1)個。それぞれの箇所に「+」…

シンプルな再帰処理による全列挙

問題 C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder 解法 問題のタイトル通り虱潰しに出していく。Nの最大値が小さいのでfor文を何重にも書いても良いが、再帰関数を用いて書いてみる。 再帰処理を書くポイント 再帰処理を書く場合以下の…

深さ優先探索を用いて社長のお給料を決める

問題 C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder 解き方 問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず1人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持た…

最短経路DAGを作って経路の数え上げをする(動的計画法)

問題 C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder ソースコード一部 ソースコードの全体は最後に添付。 解説 今回の問題では、スタートからゴールまでの最短経路が複数存在し、その経路数を求める問題である。 よって、初めに行うことは…

深さ優先探索を使って全探索を行う AtCoder ABC 015 C

問題 C: 高橋くんのバグ探し - AtCoder Beginner Contest 015 | AtCoder ソースコード 解説 バグを発見するためには、全ての質問に対してそれぞれ全ての選択肢をいずれかを選んだパターンを全列挙し、バグがあるか否かを判断しなければならない。 全列挙可能…

食費を節約するために動的計画法を用いる

問題 C: 節制 - AtCoder Beginner Contest 013 | AtCoder はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。 普通の食事: A 円の出費をして、満腹度が B 増える。 質素な食事: C 円の…