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

AtCoder ABC056 C - Go Home

問題 時刻0に直線上の0地点にカンガルーがいる。時刻i - 1から時刻iにかけてカンガルーは現在地点pとするとp - i, p, p + 1のどれかに移動することができる。カンガルーが位置Xに到達する最短時間を求める問題。 C: Go Home - AtCoder Beginner Contest 056 …

AtCoder ABC057 D - Maximum Average Sets

問題 D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、…

AtCoder ABC057 C - Digits in Multiplication

問題 C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder 整数N(1 <= N <= 1010)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値す…

AtCoder ARC 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

B - 2点間距離の最大と最小 ( Maximum and Minimum ) B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest 004 | AtCoder N + 1個(0 ~ N)点がx,y平面上にある時、i番目の点とi+1番目の点との距離が与えられる(0 <= i < N)。 この時…

AtCoder ARC 004 A - 2点間距離の最大値 ( The longest distance )

A - 2点間距離の最大値 ( The longest distance ) A: 2点間距離の最大値 ( The longest distance ) - AtCoder Regular Contest 004 | AtCoder N個のx,y座標が与えられ、任意の2つの点の距離が最大となる値を出力する問題 解法 与えられる点の数がN(2 <= N <…

AtCoder ABC D - Mixing Experiment

問題 D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder 解き方 全列挙を考える 全列挙する場合、i番目の薬品を購入する場合としない場合を2パターンをN回行うので、計算量はO(2N)となりNは最大40なので間に合わない。 動的計画法を使う dp(i…

ツリーグラフにおける最短ルートの算出

問題 B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder 解法 与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。 それぞれのノードについて、巡回すべきノードであるか否かを…

優先度付きキューを用いてダイクストラ法によってたこ焼きを効率よく投げる ARC008 C - THE☆たこ焼き祭り2012

問題 C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008 | AtCoder 解法 以下のステップで解くことができる。 ダイクストラ法を用いて始点から各点までの最短時間を算出 始点から離れている点からたこ焼きを配る たこ焼きを受け取った時間が最も遅かっ…

漸化式を立てて「tree DP問題」を解く D - 塗り絵

問題 D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder N 個の島があります。 島には 1 から N までの番号がついています。 また、N−1 個の橋があります。 i 番目の橋は ai 番の島と bi 番の島をつないでいます。 どの島からどの島へも橋をいくつか経由…

AtCoder ABC027 D - ロボット

問題 D: ロボット - AtCoder Beginner Contest 027 | AtCoder 部分点解法 部分点解法は動的計画法を用いた解法となる。 文字列を1文字ずつ辿る。'M' の時に「右に行く場合」と「左に行く場合」の2パターンで分木していく。すると以下のような木構造となる…

AtCoder ABC050 C - Lining Up

問題 C: Lining Up - AtCoder Beginner Contest 050 | AtCoder 解法 「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」の並びを見てみる。 N = 5 の時 4, 2, 0, 2, 4 N = 8 の時 7, 5, 3, 1, 1, 3, 5, 7 という並びになり、同じ数字が2…

ドワンゴからの挑戦状 C - スキーリフトの相乗り

問題 C: スキーリフトの相乗り - 第3回 ドワンゴからの挑戦状 予選 | AtCoder 解法 リフトの定員は4人。乗客を効率よく載せて、使用するシフト数を最小にする問題。条件を満たすような乗客の載せ方は、なるべく多くのリフトに定員数の4人を載せること。4…

ドワンゴからの挑戦状 B - ニコニコレベル

問題 B: ニコニコレベル - 第3回 ドワンゴからの挑戦状 予選 | AtCoder ニコニコ文字列とは、25 を 0 回以上繰り返した文字列のことをいいます。たとえば 25 や 252525 や空文字列はニコニコ文字列ですが、123 や 225 はニコニコ文字列ではありません。 ある…

Mapのキーに独自キーを割り当てる D - すぬけ君の塗り絵 / Snuke's Coloring

問題 D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Beginner Contest 045 | AtCoder 解き方 ポイントは以下の通り。 Mapを用いて3×3の四角形とその範囲に存在する黒マスの数を管理する。 1つの黒マスが影響する四角形は9個(四角形の中央のマスを基…

重複組合せを用いた多重ループ

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 問題文の以下に注目 このプログラムの出力する答えは 1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数に等しい 公式の解説に則ってこの文章を以下のように変換して考える。 「…

計算量O(N)をダブリングによってO(logN)にする D: 阿弥陀

問題 D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder 満点解法 D回だけループさせ阿弥陀をシュミレーションするという実装もできるがTLEとなる。 よってダブリングによって計算量を小さくする。 ダブリングとは ダブリングを使ったべき乗計算はこちら…

AtCoder ABC D: 経路

問題 D: 経路 - AtCoder Beginner Contest 037 | AtCoder 解法 以下をポイントにして動的計画法により解く。 求めたいもの: 経路数 マスを進む度に変わるもの: (i, j) 現在いるマスがi行j列のマス 進めるマスが無くなったらを抜ける条件にして再帰関数で実装…

トポロジカルソートの組合せを数え上げる

問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満…

フェルマーの小定理による組み合わせ計算によって経路数を数え上げる

問題 D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder 解法 まず、この問題のポイントを抑える 問題のポイント 右と下にのみ移動可能なマス目の経路数の数え上げ 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105) AB…

Union-Findを用いてそれぞれの木の大きさを高速で求める

問題 D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder 解法 Union-Findを用いて、それぞれの国民の持つ条件によって作成される木(都市と道路の関係図)の大きさ(都市数)を求める。 Union-Findとは 木が持つ情報(高さ、大きさ、どの要…

大ジャンプ AtCoder ABC 011D

問題 D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder 解き方(満点解法) 以下のステップで解くことができる。 左右に移動する回数と上下に移動する回数の2パターンについて考える 左右に移動する回数をhorizon回と固定する すると上下に移動する回…

バレンタインデーの幸福度を最も高くするためにやるべき5つのステップ

問題 D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder 解法 グループにどの女子を含ませるか決まれば、どの男子を含めるべきかは貪欲に決定される。よって以下のステップで解くことができる。 グループに含める女子を固定 幸福度が最も高くな…

動的計画法が困難なナップザック問題

問題 D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder 解法 この問題はナップザック問題を応用したものである。入力値は以下の3つの条件のどれかが当てはまる N <= 30 のケース それぞれの荷物の価値Viが1000以下のケース それぞれの荷物の…

プライオリティキューを用いたダイクストラ法 ~トレジャーハント編 ~

問題 D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder 解法 流れ 滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを…

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

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

動的計画法を使うことでアスレチックで遊ぶ時に体力の消耗を抑える

問題 C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder 解き方 全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。 なぜ動的計画法が使えるか 部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。i…

動的計画法を使ってグリッドの経路数を求める

問題 C: 経路 - AtCoder Beginner Contest 034 | AtCoder 100点解法 ※この問題は101点満点なので、満点解法ではない。 動的計画法を用いて経路数を算出する。 動的計画法を用いることができるのは以下の2つのポイントをおさえているから。 分割統治法: 部分…

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

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

ワーシャル・フロイド法を使って全点間の最短距離を算出する(グラフ理論)

問題 C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder ソースコード 解説 AtCoder Beginner Contest 022 解説 ダイクストラ法で解けそうであるが、頂点Aから、どこかにいき再び頂点Aに戻ってくる経路は閉路なためそのままではダイクストラ法やワーシ…

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

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

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

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

漸化式を用いた動的計画法の関数の作り方

わんちゃんかわいいですね。 動的計画法勉強中で流れを掴むために関数の作り方を整理します。そのため間違った内容などもあるかもですがまとめてみます。 もし、間違っていたらコメントください。 動的計画法とは 動的計画法は以下の2種類の条件を満たすア…