AtCoder の検索結果:

AtCoder ABC056 C - Go Home

…Go Home - AtCoder Beginner Contest 056 | AtCoder 解法 X = 12に場合を考える。毎時刻、右に進むとき以下のようになる。(p = 位置(t = 時間)と表す) 0(0) →1(1) →3(2) →6(3) →10(4) →15(5) この時、時刻t = 5の時の現在地はp = 15となりXとの差は3である。上の進み方の内、時刻2から3に変わる時に「動かない」という選択をすると最終地点は3だけマイナスとなりt = 5の時p = …

AtCoder ABC057 D - Maximum Average Sets

…ge Sets - AtCoder Beginner Contest 057 | AtCoder N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、その最大の平均値となるように品物を選択する通り数を出力する問題。 解法 まずは、全列挙できるか考え見る。 全列挙による解法 品物を選択する方法を全列挙し、平均値を計算するという方法を…

AtCoder ABC057 C - Digits in Multiplication

…ication - AtCoder Beginner Contest 057 | AtCoder 整数N(1 <= N <= 1010)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値する関数と定義されている。 解法 約数を全列挙する方法を考えてみる。整数iを1 ~ Nの範囲でforループさせ、Nがiで割り切れる時、A = i, B = N / iとなりA…

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

…nimum ) - AtCoder Regular Contest 004 | AtCoder N + 1個(0 ~ N)点がx,y平面上にある時、i番目の点とi+1番目の点との距離が与えられる(0 <= i < N)。 この時、0番目の点とN番目の点の距離で取り得る最大の距離と最小の距離を出力する問題。 解法 最大距離 最大距離は与えられた各点の距離を全て足し合わせることで取得することができる。この時、与えられた点は全て一直線上に存在することになる。 最小距離 与えられた点…

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

…ce ) A: 2点間距離の最大値 ( The longest distance ) - AtCoder Regular Contest 004 | AtCoder N個のx,y座標が与えられ、任意の2つの点の距離が最大となる値を出力する問題 解法 与えられる点の数がN(2 <= N <= 100)なので、任意の2点を全列挙すると計算量はO(104)となり、問題なく間に合う。 任意の2点を決めたら、三平方の定理により2点間の距離を算出し、最大となる値を出力する。 ソースコード

AtCoder ABC D - Mixing Experiment

…eriment - AtCoder Beginner Contest 054 | AtCoder 解き方 全列挙を考える 全列挙する場合、i番目の薬品を購入する場合としない場合を2パターンをN回行うので、計算量はO(2N)となりNは最大40なので間に合わない。 動的計画法を使う dp(i, x, y)を以下のように定義する。 dp(i, x, y) := {i番目までの薬を使用した時、物質aの和がx, bの和がyとなる、最小コスト} 漸化式を立てる dp(i, x, y)は漸…

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

… ツリーグラフ - AtCoder Regular Contest 030 | AtCoder 解法 与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。 それぞれのノードについて、巡回すべきノードであるか否かを判定し、巡回すべきノードであれば距離を加算していく。 深さ優先探索を使う。親ノード以外進むノードがなくなった時に、そのノードに宝石があるか否かをチャック。宝石がある場合はそのノードは必ず巡回する必要がある…

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

…き祭り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パターンで分木していく。すると以下のような木構造となる。 dp(i, j) := i番目操作した時、座標jにいる時に最大の幸福度 なぜ、このようにおけるのか。i番目まで操作した時、座標jいるパターンが複数ある時、その後の操作はどのパターンも同じとなる…

しゃくとり法を用いて計算量を減らす AtCoder C - 単調増加

問題 C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder 解法 以下のようにしゃくり法を用いて計算量O(N)で算出する プラスされている箇所を見ると等差数列の和となっているので、等差数列の和の公式を用いることでさらに計算量を減らす事ができる。 ソースコード

AtCoder ABC050 C - Lining Up

…ning Up - AtCoder Beginner Contest 050 | AtCoder 解法 「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」の並びを見てみる。 N = 5 の時 4, 2, 0, 2, 4 N = 8 の時 7, 5, 3, 1, 1, 3, 5, 7 という並びになり、同じ数字が2回登場する(0は1回)。つまり、ある数字が当てはまる箇所は2通り。N個の中から前半の半分が決まれば後半は選択していない方を選んでいく。後半を選択する通…

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

…の挑戦状 予選 | AtCoder 解法 リフトの定員は4人。乗客を効率よく載せて、使用するシフト数を最小にする問題。条件を満たすような乗客の載せ方は、なるべく多くのリフトに定員数の4人を載せること。4人乗ったリフト数を最大化するように乗客を載せることで使用するリフト数を最小化することができる。 何人グループが何組存在するかを配列で保持。 nums[1] = 1人グループの数 nums[2] = 2人グループの数 nums[3] = 3人グループの数 nums[4] = 4人…

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

…の挑戦状 予選 | AtCoder ニコニコ文字列とは、25 を 0 回以上繰り返した文字列のことをいいます。たとえば 25 や 252525 や空文字列はニコニコ文字列ですが、123 や 225 はニコニコ文字列ではありません。 ある文字列 S がその連続した部分文字列として含む最長のニコニコ文字列の長さを S の ニコニコレベル といいます。 たとえば 52525, 25025, 12151 のニコニコレベルはそれぞれ 4, 2, 0 です。 ニワンゴくんは 0 から 9…

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

…oloring - AtCoder Beginner Contest 045 | AtCoder 解き方 ポイントは以下の通り。 Mapを用いて3×3の四角形とその範囲に存在する黒マスの数を管理する。 1つの黒マスが影響する四角形は9個(四角形の中央のマスを基準とする) 全ての黒マスについて、影響する四角形が登場した数だけプラス。 黒マスが含まれない四角形の数は全体から引く。 Mapのキーに独自キーを割り当てる。 今回のMapのデータ構造はキーを独自クラスのPoint(x, …

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

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

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

… D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder 満点解法 D回だけループさせ阿弥陀をシュミレーションするという実装もできるがTLEとなる。 よってダブリングによって計算量を小さくする。 ダブリングとは ダブリングを使ったべき乗計算はこちら。 keita-matsushita.hatenablog.com これはX10を計算する時に10回ループを回して計算するのではなく。 X10 = X8 * X2 として計算することでXNの時…

AtCoder ABC D: 経路

…題 D: 経路 - AtCoder Beginner Contest 037 | AtCoder 解法 以下をポイントにして動的計画法により解く。 求めたいもの: 経路数 マスを進む度に変わるもの: (i, j) 現在いるマスがi行j列のマス 進めるマスが無くなったらを抜ける条件にして再帰関数で実装 dp[i, j] = 経路数とする 漸化式を考える。 漸化式 f(i, j)の経路数は、上下左右の4つのマスの経路数の和に1加えた数になる。1加えるのは、今回の問題では1マスも動…

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

… D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満たすかをチェック)の方法で部分点が取れる。 満点解法 以下のように動的計画法により解く。 公式解説 http://abc041.contest.atcoder.jp/data/abc/041/e…

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

… a Grid - AtCoder Beginner Contest 042 | AtCoder 解法 まず、この問題のポイントを抑える 問題のポイント 右と下にのみ移動可能なマス目の経路数の数え上げ 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105) ABによって作成される四角形内は進入不可 それぞれ見ていく 右と下にのみ移動可能なマス目の経路数の数え上げ これは、座標(0, 0)から(x, y)までに行く経路数はx+yCx(x+y個の中からx個選ぶ組み…

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

…化対策について - AtCoder Beginner Contest 040 | AtCoder 解法 Union-Findを用いて、それぞれの国民の持つ条件によって作成される木(都市と道路の関係図)の大きさ(都市数)を求める。 Union-Findとは 木が持つ情報(高さ、大きさ、どの要素を持つか)を状態別に管理することで、それらの情報を高速に求めるためのデータ構造。 詳しくは以下の記事を参照 keita-matsushita.hatenablog.com Union-Fi…

大ジャンプ AtCoder ABC 011D

…: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder 解き方(満点解法) 以下のステップで解くことができる。 左右に移動する回数と上下に移動する回数の2パターンについて考える 左右に移動する回数をhorizon回と固定する すると上下に移動する回数はvertical = N - horizonとなる 左右のみの移動を考えた時に最終的にXにいる通り数を考えたい よって、右に移動する回数はright = (horizon + X) / …

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

…レンタインデー - AtCoder Beginner Contest 018 | AtCoder 解法 グループにどの女子を含ませるか決まれば、どの男子を含めるべきかは貪欲に決定される。よって以下のステップで解くことができる。 グループに含める女子を固定 幸福度が最も高くなるように、男子を決定 固定した女子の状態で最大の幸福度を算出 どの女子をグループに含めるかを全てのパターンを列挙 最終的に幸福度が一番高いものを出力 bit操作によって女子のパターンを全列挙 グループにある…

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

…ップサック問題 - AtCoder Beginner Contest 032 | AtCoder 解法 この問題はナップザック問題を応用したものである。入力値は以下の3つの条件のどれかが当てはまる N <= 30 のケース それぞれの荷物の価値Viが1000以下のケース それぞれの荷物の重さWiが1000以下のケース それぞれのケースについて考える。 1. N <= 30 のケースはDPできない このケースでは価値と重みに制約がないため、動的計画法は困難。 今回の問題では、価…

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

…レジャーハント - AtCoder Beginner Contest 035 | AtCoder 解法 流れ 滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを全ての頂点の場合を列挙し得られる得点が最大の物を出力する。 ダイクストラ法 この問題はスタート地点から各頂点の最短経路を求めることで解が得られるので、最短経路問題である。よってダイクストラ法を用いて頂点…

マージソートを使って文字列を辞書順を並べる

… さかさま辞書 - AtCoder Regular Contest 003 | AtCoder 解き方 この問題は以下のステップで解くことができる。 全ての単語を前後反転させる ソート 更に前後反転し元に戻す Javaの標準のソートメソッドを用いる Javaには標準でArraysというクラスあり、ソートメソッドArrays.sort()が実装されている。このメソッドはジェネリックスを用いて実装されているので、数字以外でもソートが可能である。文字列をソートする場合は勝手に辞書順…

幅優先探索を用いてリモコン操作を最小限に抑える

…B: リモコン - AtCoder Regular Contest 001 | AtCoder 解き方 貪欲法でも解けるが、境界線を考慮するのが面倒。そんな時は幅優先を使って全列挙してしまう。 幅優先探索とは 幅優先探索とは、複数の選択肢がある時に、全ての選択肢を順番に試していくというものだ。今回の問題では、リモコンでの操作が6つある。これらの操作を片っ端から順番に行っていく。 幅優先の探索順序は、ルートノードから浅いノードを順番に探索していく。よってリモコンの操作回数とルー…

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

…5.contest.atcoder.jp/tasks/arc061_a 解き方 全列挙できるか 全ての数字と数字の間に対して、「+」を入れる場合と入れない場合で全列挙。文字列の長さがNの場合、「+」を入れることができる箇所は全部で(N - 1)個。それぞれの箇所に「+」を入れるか否かの2通りを行うので計算量はO(2N - 1)。 今回のNの最大値は10であり、210は1024なので全列挙は可能。 深さ優先探索を用いた全列挙 まずは深さ優先探索を用いた全列挙を考える。 再帰関数…

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

…: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder 解き方 全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。 なぜ動的計画法が使えるか 部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。i番目の柱に到達する方法は、i - 1番目からとi -2番目から到達する2つの方法がある。またi番目のコストはi - 2, i - 1番目時点でのコストに、i番目に来るのに必要なコストを足せばOK…

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

…題 C: 経路 - AtCoder Beginner Contest 034 | AtCoder 100点解法 ※この問題は101点満点なので、満点解法ではない。 動的計画法を用いて経路数を算出する。 動的計画法を用いることができるのは以下の2つのポイントをおさえているから。 分割統治法: 部分問題を解き、その計算結果を用いて全体問題を解く メモ化: 部分問題の計算結果を保存し、再利用する 上記のポイントをこの問題に当てはめてみる。 分割統治法: 部分問題を解き、その計算結果…

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

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

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

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

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

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

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

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

ダイクストラ法を用いて最短経路で目的地に着く

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

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

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

いもす法を用いて計算量をO(N^2)からO(N)に減らす

…整理します。 問題 AtCoder ABC 014 C C: AtColor - AtCoder Beginner Contest 014 | AtCoder ソースコード 解説 まずは普通の解き方を見てみる。 いもす法使わない解法 これは、それぞれのアンケートに対して、その解答で得られた範囲の分だけループによって愚直にカウントしていく方法。 これだと、ループが2重になっているため最悪の計算量が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 ソースコード 解説 問題文に書いてある通り、キューを用いた幅優先探索によって最短経路を算出する。 ポイント1 幅優先探索の流れ 初めにキューに入れるノード(start)の初期化 startを訪問済みとする while キューが空になるまで { キューからノードpointを取り出す。 pointの子ノードchildrenを取得(pointから進むことのできるノード郡) for ne…

美味しいたこ焼きの焼き方 AtCoder ABC 005 D

…こ焼きの焼き方 - 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通り。 候補に対して、その要素を含むか否かの2パターンを12要素分行う。 その際、その要素を含むか否かをビットを用いて管理する。 含む=> 1 含まない=> 0 例 N = 4の時、N桁の2進数で管理「0000」。 0001: 一つ目の要素が含まれる 0100: 3つ…