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

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

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

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

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

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

問題 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 解き方 問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず１人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持た…

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

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

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