Matsushita's Blog

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つのポイントをおさえているから。 分割統治法: 部分問題を解き、その計算結果を用いて全体問題を解く メモ化: 部分問題の計算結果を保存し、再利用する 上記のポイントをこの問題に当てはめてみる。 分割統治法: 部分問題を解き、その計算結果…