… Attack - AtCoder Beginner Contest 029 | AtCoder 解法 問題のタイトル通り虱潰しに出していく。Nの最大値が小さいのでfor文を何重にも書いても良いが、再帰関数を用いて書いてみる。 再帰処理を書くポイント 再帰処理を書く場合以下のポイントを押さえる 再帰処理を使うパターン 再起する度に変化するもの 再帰を抜ける条件 再帰処理で求めたいもの i回目からi+1回目の再帰を呼ぶ 再帰処理を使うパターン 再帰を使うパターンは以下の通り。 …

… 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder 解き方 問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず１人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持たない社員となる。また、問題の性質上、社長の給料は社長の直属の部下の全てのお給料が計算されて初めて決定する。よって社員を持たない部下のお給料から計算していけば最終的に社長の給料を決定することができる。 ソー…

…ue Bird - AtCoder Beginner Contest 022 | AtCoder ソースコード 解説 AtCoder Beginner Contest 022 解説 ダイクストラ法で解けそうであるが、頂点Aから、どこかにいき再び頂点Aに戻ってくる経路は閉路なためそのままではダイクストラ法やワーシャルフロイド法は使えない。よって以下のように一度頂点Aから頂点Bまでの経路の最短距離を求めるように問題を変換する。 １．「頂点1に隣接する辺を除いたグラフ」の全点 対の…

…直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder ソースコード一部 ソースコードの全体は最後に添付。 解説 今回の問題では、スタートからゴールまでの最短経路が複数存在し、その経路数を求める問題である。 よって、初めに行うことは与えられたグラフから最短経路でゴールにたどり着かない道を削ることである。そうすることで、残った経路のどの経路を通ったとして最短経路でゴールに辿り着くことができる。 つまり、まとめると以下のステップを行う。 …

… C: 壁抜け - AtCoder Beginner Contest 020 | AtCoder ソースコード 解説 問題文のxの値を固定し、xが最大となるものを出力する。xが取りうる値の最大値から順番に試し、スタートからゴールまで制限時間内にたどり着けたものを採用する。 まずは全探索を考える。深さ優先探索を使った全探索では、スタートからゴールまでの全ての行き方を全列挙するので、W,Hが小さい値のみでしか有効にならない。よって別の方法を検討する必要がある。そこでダイクストラ法…

…くんのバグ探し - AtCoder Beginner Contest 015 | AtCoder ソースコード 解説 バグを発見するためには、全ての質問に対してそれぞれ全ての選択肢をいずれかを選んだパターンを全列挙し、バグがあるか否かを判断しなければならない。 全列挙可能か 全列挙する場合、気をつけなければならないのが計算量だ。この問題ではN個の質問に対してそれぞれ、K個の選択肢が存在する。全列挙するためには0(KN)となる。仮にNの最大値が9辺りになると解けない。しかし、今…

…整理します。 問題 AtCoder ABC 014 C C: AtColor - AtCoder Beginner Contest 014 | AtCoder ソースコード 解説 まずは普通の解き方を見てみる。 いもす法使わない解法 これは、それぞれのアンケートに対して、その解答で得られた範囲の分だけループによって愚直にカウントしていく方法。 これだと、ループが２重になっているため最悪の計算量がO(N2)となる。今回のNの最大値は106のため解けない。 そこで「いもす法」とい…

…画法の立て方 題材はAtCoderの問題。 C: 節制 - AtCoder Beginner Contest 013 | AtCoder はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。 ・普通の食事: A 円の出費をして、満腹度が B 増える。 ・質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C<A かつ D<B） ・食事抜き: 出費なしで、満腹度が E 減る。 厳しく節約すれ…

…題 C: 節制 - AtCoder Beginner Contest 013 | AtCoder はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。 普通の食事: A 円の出費をして、満腹度が B 増える。 質素な食事: C 円の出費をして、満腹度が D 増える。 食事抜き: 出費なしで、満腹度が E 減る。 厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけ…

問題 C: 浮気調査 - AtCoder Beginner Contest 010 | AtCoder ソースコード 解説 スタートから浮気相手の家までの距離と、浮気相手からの家からゴールまでの距離を三平方の定理で計算し足し合わせる。 この数字がT*Vの値以内であれば浮気可能。 上記の処理を全ての浮気相手分行うことで判定することができる。

問題 AtCoder Beginner Contest 008 C C: コイン - AtCoder Beginner Contest 008 | AtCoder ソースコード 解説 全ての順列を列挙する計算量はN!となってしまい、満点解答できない。 そのため、それぞれのコインに着目し最終的に表になる確率を算出する。その後それらの確率を足し合わせる事で期待値を計算する。 よって、入力で与えられたコインそれぞれに着目する それぞれのコインに対して最終的に表になる確率を求める 0…

…: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder ソースコード 解説 問題文に書いてある通り、キューを用いた幅優先探索によって最短経路を算出する。 ポイント１ 幅優先探索の流れ 初めにキューに入れるノード(start)の初期化 startを訪問済みとする while キューが空になるまで { キューからノードpointを取り出す。 pointの子ノードchildrenを取得(pointから進むことのできるノード郡) for ne…

…こ焼きの焼き方 - AtCoder Beginner Contest 005 | AtCoder ソースコード 解説 AtCoder Beginner Contest 005 解説 from AtCoder Inc. www.slideshare.net AtCoderより こちらを参考に。 実装の流れ 1. ある点から始点(1, 1)までの範囲の美味しさの合計を算出 2. それぞれのサイズ(面積)で作られる長方形において、最大の「美味しさ」を算出 3. 書くプレイヤーが焼け…

問題 (AtCoder ABC002 D) abc002.contest.atcoder.jp ソースコード 解説 ビット操作により全探索をする。この問題はNの数が最大でも12なので、最大でも212 = 4096通り。 候補に対して、その要素を含むか否かの２パターンを12要素分行う。 その際、その要素を含むか否かをビットを用いて管理する。 含む=> 1 含まない=> 0 例 N = 4の時、N桁の２進数で管理「0000」。 0001: 一つ目の要素が含まれる 0100: ３つ…