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

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

問題 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の桁数を比べ小さい方の桁数を返り値す…

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)。 この時…

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

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

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

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

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

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

問題 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 という並びになり、同じ数字が２…

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

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

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

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

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

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

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

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

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

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

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

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

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

問題 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点満点なので、満点解法ではない。 動的計画法を用いて経路数を算出する。 動的計画法を用いることができるのは以下の２つのポイントをおさえているから。 分割統治法: 部分…

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

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

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