C - Triangular Relationship
はじめに
競技プログラミング、AtCoder Beginner Contest 108
C - Triangular Relationship
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
整数 N,Kが与えられます。 N以下の正の整数の組 (a,b,c)であって、a+b,b+c,c+aがすべて Kの倍数であるようなものの個数を求めてください。 ただし、a,b,cの順番を入れ替えただけの組も異なるものとして数えます。 また、a,b,cの中に同じものがあっても構いません。
制約
・1≤N,K≤2×10^5 ・N,Kは整数である
入力
入力は以下の形式で標準入力から与えられる。 N K
出力
N以下の正の整数の組 (a,b,c)であって、a+b,b+c,c+aがすべてKの倍数であるようなものの個数を出力せよ。
解き方
以下の記事がとても分かり易いです。
pyteyon.hatenablog.com
qiita.com
上の記事が分かり易いので、
ここでは流れを見るだけにとどめます。
解き方の詳しい内容はありません。
備忘録
以下のコードを参考にしています。
atcoder.jp
この問題を解くうえで重要なことは、modの使用です。
問題文の「Kの倍数」という部分に反応してmodの使用を疑います。
次に、
「N以下の正の整数の組 (a,b,c)であって、a+b,b+c,c+aがすべて Kの倍数であるようなもの」
の個数を最終的に答えなければいけないので
どんなものが(a,b,c)の組になり得るかを考えます。
(a,b,c)では考えにくいので、
初めに(a,b)で考えてみます。
ここで、
modの考え方を適用し
・aとbがどちらもKの倍数であること ・Kが偶数であるとき、aとbがa%K=K/2かつb%K=K/2
であることに気づきます。
これは(a,b)が(a,b,c)になってもそのまま適用できるので
このまま実装にうつります。
先ほど、考えた条件のうち
・aとbとcが全てKの倍数であること
はK偶数、奇数どちらでも使えるのでまずこれを入れます。
N以下のKの個数を数えたいので
N以下のKの倍数=N/K;
で出します。
また、出した個数の組み合わせは
当てはめる場所が(a,b,c)と三か所あり
問題文より数の重複が許されるので
aとbとcが全てKの倍数であるときの(a,b,c)の組の数 =(long)Math.Pow(count, 3);
となります。
longへのキャストはoverflow防止です。
次に以下の条件を考えます。
Kが偶数であるとき、aとbがa%K=K/2かつb%K=K/2かつc%K=K/2
Kが偶数であるときに適用するので
Kが偶数であるかどうかをまずフィルターします。
if (K % 2 == 0)
{
//処理
}
次にN以下の整数の中で
Kで割ると余りがK/2になる整数の個数を出します。
Kで割ると余りがK/2になる整数の個数 = (N + (K / 2)) / K;
ここでNに（K/2）を足したものをKで割っていることが
少し混乱するので入力例1で考えてみます。
入力例1
3 2
これをそのまま先ほどの式に入れると以下のようになります。
(N + (K / 2)) / K =(3 + (2 / 2)) / 2 =4/2 =2
(a,b,c)に入る数はN以下でなければならないはずですが
Kを2で割ったものをNに足したものを
Kで割り、個数を出しています。
4以下の2の倍数は
2と4なので4はNである3を超えてしまいますが
Kを2で割ったときに（K/2）の余りがある数が欲しいので
実際には
2と4ではなく、それぞれから（2/1）を引いた
1と3のことを数えています。
そして、ここでも
出した個数の組み合わせは
当てはめる場所が(a,b,c)と三か所あり
問題文より数の重複が許されるので
Kで割ると余りがK/2になる整数の(a,b,c)の組の数 =(long)Math.Pow(count, 3);
偶数の場合は両方の条件の組の数を足した数、
奇数の場合は初めの条件に当てはまる組の数を出力します。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var nk = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var N = nk[0];
var K = nk[1];
var ans = 0L;
//aとbとcが全てKの倍数である
var count = N / K;
ans += (long)Math.Pow(count, 3);
//Kが偶数であるとき、aとbがa%K=K/2かつb%K=K/2かつc%K=K/2
if (K % 2 == 0)
{
count = (N + (K / 2)) / K;
ans += (long)Math.Pow(count, 3);
}
Console.WriteLine(ans);
}
}
C - String Transformation
はじめに
競技プログラミング、AtCoder Beginner Contest 110
C - String Transformation
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
英小文字のみからなる文字列S,Tが与えられます。 文字列Sに対して、次の操作を何度でも行うことができます。 操作: 2つの異なる英小文字c1,c2を選び、Sに含まれる全てのc1を c2に、c2を c1に置き換える 0回以上操作を行って、SをTに一致させられるか判定してください。
制約
・1≤|S|≤2×10^5 ・|S|=|T| ・S,Tは英小文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。 S T
出力
SをTに一致させられる場合は Yes、そうでない場合は No を出力せよ。
解き方
こちらの解き方を参考にしています。
https://img.atcoder.jp/abc110/editorial.pdf
atcoder.jp
問題文に書かれている「操作」を行い、SをTに一致させられるかを考える。
まず例題を見ながら考え方を考えていく。
入力例１
azzel apple
「azzel」を「apple」に書き換える。
①一番初めの「a」は両者共通の位置にあるので放置する
②二番目の文字は「azzel」は「z」だが、「apple」は「p」なので
「操作」を行い、
「azzel」の「z」を「p」に置き換え、「p」を「z」に置き換える。
「azzel」は「p」を含まないので「z」だけが「p」に置き換わり「appel」になる。
③三番目の文字は②の「操作」によって両者とも「p」になっているので放置する
④四番目の文字は「appel」は「e」だが、「apple」は「l」なので
「操作」を行い、「appel」の「e」を「l」に置き換え、「l」を「e」に置き換える。
「appel」は「e」「l」をどちらも含むので
それぞれが置き換わり「apple」になる。
⑤「azzle」は「apple」になるので答えは"Yes"
入力例2
chokudai redcoder
①一文字目は「c」と「r」で異なっているので「操作」を行い、
「chokudai」の「c」を「r」に「r」を「c」に置き換える。
「chokudai」は「rhokudai」になる。
②二文字目は「h」と「e」で異なっているので「操作」を行い、
「rhokudai」の「h」を「e」に「e」を「h」に置き換える。
「rhokudai」は「reokudai」になる。
③三文字目は「o」と「d」で異なっているので「操作」を行い、
「reokudai」の「o」を「d」に「d」を「o」に置き換える。
「reokudai」は「redkuoai」になる。
④四文字目は「k」と「c」で異なっているので「操作」を行い、
「redkuoai」の「k」を「c」に「c」を「k」に置き換える。
「redkuoai」は「redcuoai」になる。
⑤五文字目は「u」と「o」で異なっているので「操作」を行い、
「redcuoai」の「u」を「o」に「o」を「u」に置き換える。
「redcuoai」は「redcouai」になる。
⑥六文字目は「u」と「d」で異なっているので「操作」を行い、
「redcouai」の「u」を「d」に「d」を「u」に置き換える。
「redcouai」は「reucodai」になる。
ここで③で置き換えた「d」が「u」に置き換わってしまうことに注目する。
「u」を「d」に置き換えたいが、
そうすると⑥の「d」が「u」に置き換わってしまうので
どちらも置き換えるということができない。
⑦「chokudai」は「redcoder」にできないので答えは"No"
ここで入力例1と2を見てみると以下のような違いがあることに気づく。
入力例1
a→a z→p z→p e→l l→e
つまり
a→a z→p e→l l→e
が成り立ち、かつ
a→a p→z p→z l→e e→l
つまり
a→a p→z l→e e→l
が成り立つ。
入力例2
c→r h→e o→d k→c u→o d→d a→e i→r
は成り立つが
r→c（衝突A） e→h d→o（衝突B） c→k o→u d→d（衝突B） e→a r→i（衝突A）
は成り立たない。
衝突Bは先ほどの⑥で起こった衝突である。
衝突Aが起こる前に成り立たないことが分かったので、
最後の「r」の置換までは進めていないが
そこまで進めれば
⑥の衝突Bと同じようにAも衝突することが分かる。
つまり、文字列SとTでそれぞれ文字列の置換表を作成し
置換表に合わないものがあれば
「操作」によってSをTにすることはできないということになる。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var S = Console.ReadLine();
var T = Console.ReadLine();
//対応表
//S→T
var dicST = new Dictionary<char, char>();
//T→S
var dicTS = new Dictionary<char, char>();
//答え
var ans = "Yes";
//SとTの文字数ぶん、ループを回して
//それぞれの文字の対応表への登録と照らし合わせを行う
for (int i = 0; i < S.Length; ++i)
{
//S→T
//登録されていない場合は登録する
if (!dicST.ContainsKey(S[i])) dicST.Add(S[i], T[i]);
//登録されている場合
else
{
//対応表通りの文字になっているかを確認
if (T[i] != dicST[S[i]])
{
ans = "No";
break;
}
}
//T→S
//登録されていない場合は登録する
if (!dicTS.ContainsKey(T[i])) dicTS.Add(T[i], S[i]);
//登録されている場合
else
{
//対応表通りの文字になっているかを確認
if (S[i] != dicTS[T[i]])
{
ans = "No";
break;
}
}
}
Console.WriteLine(ans);
}
}
C - /\/\/\/
はじめに
競技プログラミング、AtCoder Beginner Contest 112
C - /\/\/\/
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
数列 a1,a2,...,anが以下の条件を満たすとき、 /\/\/\/ と呼ぶことにします。 ・各 i=1,2,...,n−2について、i=ai+2 ・数列に現れる数はちょうど 2種類 偶数長の数列 1,v2,...,vnが与えられます。 要素をいくつか書き換えることでこの数列を /\/\/\/ にしたいです。 書き換える要素の数は最小でいくつになるか求めてください
制約
・2≤n≤10^5 ・nは偶数 ・1≤vi≤10^5 ・viは整数
入力
入力は以下の形式で標準入力から与えられる。 n v1 v2 ... vn
出力
書き換える要素数の最小値を出力してください。
解き方
こちらの解き方を参考にしています。
https://img.atcoder.jp/arc103/editorial.pdf
atcoder.jp
問題文の以下の条件から
・各 i=1,2,...,n−2について、i=ai+2 ・数列に現れる数はちょうど 2種類
入力で与えられる配列を
偶数番目を全て同じ値、奇数番目を全て同じ値にすれば
「/\/\/\/」になるということが分かる。
また、
この問題で答えることは
「/\/\/\/」にするために
元の配列の要素を書き換える最小個数なので
元の配列の偶数番目と奇数番目、それぞれで
一番出てくる頻度が高い数字に書き換えたほうが
書き換える数字の数は少なくなる。
そのため、
基本的には
偶数番目と奇数番目で
「それぞれの一番出てくる頻度の高い数字」ではない要素の個数
（書き換えなければいけない個数）を数えて足せば答えになる。
しかし、偶数番目と奇数番目で
それぞれの一番出てくる頻度の高い数字が同じだった場合は
もしその数字に書き換えてしまうと
配列が全て同じ数字で構成されることになるので
もう一手間かける必要がある。
全てを一番頻度の高い数字に書き換えられないとなると
次に候補として上がるのは二番目に出てくる頻度の高い数字である。
そして、この二番目の候補が
偶数番目と奇数番目で二つあるので
偶数番目と奇数番目、
どちらをそれぞれの二番目に出てくる頻度の高い要素に書き換えれば
より書き換える数字の個数が少なくなるかを計算し、
少なくなる方で書き換えた要素の個数が答えになる。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
var v = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
if (v.Distinct().Count() == 1)
{
Console.WriteLine(N / 2);
return;
}
//偶数番目用のDictionary(keyが要素、valueが出てくる回数)
var evenDic = new Dictionary<int, int>();
//奇数番目用のDictionary(keyが要素、valueが出てくる回数)
var oddDic = new Dictionary<int, int>();
for (int i = 0; i < N; ++i)
{
//偶数番目
if (i % 2 == 0)
{
if (evenDic.ContainsKey(v[i])) evenDic[v[i]]++;
else evenDic.Add(v[i], 1);
}
//奇数番目
else
{
if (oddDic.ContainsKey(v[i])) oddDic[v[i]]++;
else oddDic.Add(v[i], 1);
}
}
//出てくる頻度の高い順に並び替え
evenDic = evenDic.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
oddDic = oddDic.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
//書き換える数字の数
var cost = 0L;
//偶数番目で出てくる頻度の最も高い数
var evenFirst = evenDic.First();
//奇数番目で出てくる頻度の最も高い数
var oddFirst = oddDic.First();
//偶数番目、奇数番目、それぞれの要素の個数
var half = N / 2;
//偶数番目と奇数番目で最も出てくる頻度の高い要素が同じとき
if (evenFirst.Key == oddFirst.Key)
{
//偶数番目で出てくる頻度が二番目に高い数
var evenSecond = 1 < evenDic.Count() ? evenDic.Skip(1).First().Value : int.MinValue;
//奇数番目で出てくる頻度が二番目に高い数
var oddSecond = 1 < oddDic.Count() ? oddDic.Skip(1).First().Value : int.MinValue;
//偶数番目、奇数番目のどちらかを二番目に出てくる頻度の高い数に書き換える
//偶数番目が最も出てくる頻度の高い数、奇数番目が二番目に出てくる頻度の高い数
//に書き換えた場合の
//書き換えなければいけない要素の個数
long plan1 = (half - evenFirst.Value) + (half - oddSecond);
//偶数番目が二番目に出てくる頻度の高い数、奇数番目が最も出てくる頻度の高い数
//に書き換えた場合の
//書き換えなければいけない要素の個数
long plan2 = (half - evenSecond) + (half - oddFirst.Value);
//上の二つで書き換えなければいけない要素の数が小さいほうを採用
cost = Math.Min(plan1, plan2);
}
//偶数番目と奇数番目で最も出てくる頻度の高い要素が違うとき
else
{
cost = (half - evenFirst.Value) + (half - oddFirst.Value);
}
Console.WriteLine(cost);
}
}
C - Pyramid
はじめに
競技プログラミング、AtCoder Beginner Contest 112
C - Pyramid
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
古代すぬけ国では, AtCoder 社長「高橋君」の権威を高めるために, ピラミッドが建てられていた. ピラミッドには 中心座標 (CX,CY)と 高さ Hが定まっており, 座標 (X,Y)の高度は max(H−|X−CX|−|Y−CY|,0)であった. 探検家の青木君は, このピラミッドの中心座標と高さを求めるために調査を行った. その結果, 次のような情報が得られた. ・CX,CYは 0以上100以下の整数で, Hは 1以上の整数であった. ・上記と別に N個の情報が得られた. そのうち i個目の情報は, 「座標 (xi,yi)の高度は hiである」 この情報は, ピラミッドの中心座標と高さを特定するのに十分であった. 情報を手掛かりに, これらの値を求めなさい.
制約
・Nは1以上 100以下の整数 ・xi,yiは0以上100以下の整数 ・hiは0以上10~9以下の整数 ・N個の座標(x1,y1),(x2,y2),(x3,y3),...,(xN,yN)はすべて異なる ・ピラミッドの中心座標と高さをちょうど1つに特定することができる
入力
入力は以下の形式で標準入力から与えられる。 N x1 y1 h1 x2 y2 h2 x3 y3 h3 : xN yN hN
出力
特定した中心座標と高さを表す整数CX,CY,Hを空白区切りで, 1 行に出力しなさい.
解き方
こちらの解き方を参考にしています。
https://img.atcoder.jp/abc112/editorial.pdf
atcoder.jp
まず問題文の中で注目するポイントは以下の部分です。
座標 (X,Y)の高度は max(H−|X−CX|−|Y−CY|,0)
入力から座標(X,Y)とその高度を得られるので
この式を変形すれば
ピラミッド全体の高さであるHを出すことができそうです。
使えそうなので、とりあえず変形しておきます。
座標 (X,Y)の高度をhとすると、以下のように変形できます。
h=max(H−|X−CX|−|Y−CY|,0)
0の場合はhも0になることは分かるので、ひとまずのけます。
h=H−|X−CX|−|Y−CY|
-H=-h−|X−CX|−|Y−CY|
-H×(-1)=(-h−|X−CX|−|Y−CY|)×(-1)
H=h+|X−CX|+|Y−CY|
これで高さを出す式に変形できました。
次に問題文の以下の部分に注目します。
（C問題は問題文や制約の中で数が小さいものがあれば、
そこを基準に考えていくと答えに辿りつけることが多い気がします。）
CX,CYは 0以上100以下の整数で, Hは 1以上の整数であった.
頂点のCX、CYは0以上100以下ということは
全てのパターン（組み合わせ）を考えても
101×101通りしか存在しないことになります。
ここから、
中心座標を一つずつ列挙していきながら
入力されたもののうちhiが0以外のもの
（hiが0だと中心座標が変わっても常に高さが0になってしまい、正しい答えが得られない）から
一つ（xi yi hi（iは任意））をとって、
先ほど変形した式で高さ（H）を求め
その高さ（H）を使って求めた
それぞれの頂点(x1 y1,x2 y2,…,xN yN)の高度（max(H−|X−CX|−|Y−CY|,0)）が
他の入力されたもの(h1,h2,…,hN)と一致すれば
その時点での頂点と求めた高さが
答えになると言えそうです。
文章では分かりにくいので、
コードにすると以下のようなイメージです。
//中心座標をループで全パターン列挙
for (int i = 0; i <= 100; ++i)
{
for (int j = 0; j <= 100; ++j)
{
//基準とする入力を（X,Y,H）（Hは0ではない）とする。
//基準の入力から高さを求める。
var height = H + Math.Abs(X - i) + Math.Abs(Y - j);
//全ての高度が一致するかどうか
var isCorrect = true;
//上で出した高さから、それぞれの入力の高度を求め
//実際に入力された高度と数が一致するかを確認する。
for (int k = 0; k < N; ++k)
{
if (Math.Max(0, height - Math.Abs(xi - i) - Math.Abs(yi - j)) != hi)
{
//一致しないので、この中心座標は間違い
isCorrect = false;
}
}
if (isCorrect)
{
//全ての高度が一致したので、この中心座標は正しい
}
}
}
後はすべての高度が一致した時点で、
その時点の中心座標と求めた高さを出力すれば完了です。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
var list = new List<long[]>();
for (int i=0;i<N;++i)
{
var xyh = Console.ReadLine().Split(' ').Select(num => Int64.Parse(num)).ToArray();
var x = xyh[0];
var y = xyh[1];
var h = xyh[2];
list.Add(new long[3] { x, y, h });
}
//入力されたものの中で高度が0以外のものから適当に「基準」を一つ選ぶ
var kizyun = list.Where(x=>x[2]!=0).First();
//中心座標をループで一つずつ列挙
for (int i=0;i<=100;++i)
{
for (int j=0;j<=100;++j)
{
//「基準」から高さを求める
var height = kizyun[2]+ Math.Abs(kizyun[0] - i) + Math.Abs(kizyun[1] - j);
//全ての高度が一致するかどうか
var isCorrect = true;
//全ての入力で高度が一致するかどうかを調べる
for (int k = 0; k < N; ++k)
{
//問題文にある条件式に「基準」から求めた高さと入力された座標をそのまま入れて、高度を求める
//計算結果と入力された高度が一致するかどうか
if (Math.Max(0,height- Math.Abs(list[k][0] - i) - Math.Abs(list[k][1] - j)) != list[k][2])
{
//一つでも一致しなければ、中心座標は正しくないので次の中心座標にうつる
isCorrect = false;
break;
}
}
//全ての高度が一致したら中心座標は正しいので、出力する
if (isCorrect)
{
Console.WriteLine($"{i} {j} {height}");
return;
}
}
}
}
}
D - Match Matching
はじめに
競技プログラミング、AtCoder Beginner Contest 118
D - Match Matching
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
ちょうどN本のマッチ棒を使って作れる整数の中で最大のものを求めてください。 ただし、以下の条件を満たさなければなりません。 ・作る整数の各桁は、1から9までの数字のうちA1,A2,...,AM(1≤Ai≤9)のいずれかでなければならない。 ・数字1,2,3,4,5,6,7,8,9を1つ作るには、それぞれちょうど2,5,5,4,5,6,3,7,6本のマッチ棒を使う。
制約
・入力は全て整数である。 ・2≤N≤104 ・1≤M≤9 ・1≤Ai≤9 ・Aiは全て異なる。 ・ちょうどN本のマッチ棒を使って条件を満たすように作れる整数が存在する。
入力
入力は以下の形式で標準入力から与えられる。 N M A1 A2 ... AM
出力
問題文の条件下でちょうどN本のマッチ棒を使って作れる整数の最大値を出力せよ。
解き方
こちらの解き方を参考にしています。
goo.gl
まず、
この問題で出す答えは
「問題文の条件下でちょうどN本のマッチ棒を使って作れる整数の最大値」
なので、
整数を最大化する条件を考えます。
整数をなるべく大きくするためには、
まず桁数を大きくすることが必要です。
そして、
大きい桁に大きい数字をおけば
数は大きくなります。
ここから、
この問題の答えを出すには
以下の二つの条件があることが分かります。
・与えられた条件下でなるべく桁を多くすること
・大きい桁には大きい数字を置くこと
上の二つを念頭に置いて、実装を考えます。
すると、以下の2ステップになります。
・動的計画法でマッチ棒を○本使ったときに、最大で×桁作れることを割り出す
→桁数の最大化
・上で出した桁数をもとに、マッチ棒で作れる適当な数字を作る
→大きい桁に大きい数字を配置する
実装を順番に見ていきます。
✩動的計画法でマッチ棒を○本使ったときに、
最大で×桁作れることを割り出す
まず、dpの配列のかたちは以下のようになります。
dp[i]=マッチ棒 i 本で作れる最大桁数
dpの配列の大きさは
マッチ棒0～N本のときの桁数の情報が欲しいので
N+1（0～N）とします。
//dp用の配列 var dp = new int[N+1];
コードを見ながら解説していきます。
使用できる数字と、その数字で使用するマッチ棒の本数は以下のようにしています。
//使える数字
var A= Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderByDescending(x=>x).ToArray();
//それぞれの数字で使用するマッチの本数（index+1=数字）
var cost = new int[] { 2,5,5,4,5,6,3,7,6};
動的計画法の部分は以下です。
//マッチ棒を0本使用してできる桁はないので、0を入れる
dp[0] = 0;
//dpの配列にintの最小の数を入れる（inde=0以外）
for (int i = 1; i <= N; ++i) dp[i] = int.MinValue;
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
if (i != 0 && dp[i] == int.MinValue) continue;
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
0. 準備
使用できる数字と、数字を作るのにかかるマッチ棒の本数を使える状態にします。
//使える数字
var A= Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x=>x).ToArray();
//それぞれの数字で使用するマッチの本数（index+1=数字）
var cost = new int[] { 2,5,5,4,5,6,3,7,6};
「使える数字の配列」(A[M])は大きい順にしていますが、
これは動的計画法ではなく
その後の、
最終的にマッチ棒で作ることのできる数字を出す（問題の答え）
ときのために並び替えを行っています。
「それぞれの数字で使用するマッチの本数の配列」(cost[9])は、
1から9までの数字で、必要となるマッチ棒の本数を順番に入れています。
数字からマッチ棒のコストを取り出したいときは
数字から1引いた数を添え字にします。
//1 //数字1で使用するマッチ棒の本数は2 cost[1-1/*=0*/]=2; //7 //数字7で使用するマッチ棒の本数は3 cost[7-1/*=6*/]=3;
1. dp配列の始点に「0」を入れる
マッチ棒0本で作れる数字はないので、
dp[0]に0を代入します。
ここが、動的計画法の始点になります。
//マッチ棒を0本使用してできる桁はないので、0を入れる dp[0] = 0;
2. dp配列の準備
dpの0以外のindexにint.MinValueを代入します。
これは、
後で配列の値が更新されたかどうかを
確認したいので初期値として入れています。
まだここでピンとこなくても、
後でループを回す段になると分かり易くなると思います。
//dpの配列にintの最小の数を入れる（inde=0以外） for (int i = 1; i <= N; ++i) dp[i] = int.MinValue;
3. ループを回してdp配列を埋めていく
以下の部分を見ていきます。
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
if (i != 0 && dp[i] == int.MinValue) continue;
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
まず、このループの目的は
dp[マッチ棒を使用する本数]=「マッチ棒を使用する本数」で最大何桁の数字が作れるか
を埋めていくことが目的です。
外側のループでは「i」を「N」になるまで1ずつ増やしています。
この「i」はdp配列のindexであり
このdp配列を埋めていく上での基準です。
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
//if (i != 0 && dp[i] == int.MinValue) continue;
//for (int j=0;j<M;++j)
//{
// if (N < i + cost[A[j] - 1]) continue;
// dp[i+cost[A[j] - 1]] = dp[i]+1;
//}
}
中の動きを「i」を増やしながら順番に見ていきます。
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
if (i != 0 && dp[i] == int.MinValue) continue;
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
まず「i==0」のとき
if (i != 0 && dp[i] == int.MinValue) continue;
は条件式に当てはまらないので、そのまま下に進みます。
下に進むと内側のループにあたります。
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
このループでは
外側のループの「i」、
そして使用できる数字を基準として
dp配列の値をうめていくということをしています。
①index「j」
「j」は0～(M-1)までの値を取りますが
これは使用できる数字を一つずつ見るためです。
for (int j=0;j<M;++j){}
②if文
ループ内のif文の条件と
下のdp配列のindexを見ると
中身が同じになっていることに気が付きます。
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
上のif文は下のdp配列のindexがエラーにならないように
チェックしているだけなので、
dp配列に値を入れるために存在しているわけではありません。
③dp配列に値を入れる
dp[i+cost[A[j] - 1]] = dp[i]+1;
上の部分で配列に値を入れています。
まず、cost[A[j] - 1]は数字A[j]で使用するマッチの本数です。
A[j]は使用できる具体的な数字なので、
そこから1を引いたindexを
コストに入れると使用するマッチの本数が出てきます。
ここから
dp[i+cost[A[j] - 1]]は
「i」が「0」であることから
dp[使用するマッチの本数] =dp[i]+1;
となることが分かります。
右辺は左辺がdp[i+cost[A[j] - 1]]であることから
「i」本にさらに
使用できる数字のマッチの本数を追加しているので
dp[i]+1となります。
（i=0のときはdp[0]=0なので、全て1になります。）
以上より、
i=0のときdp配列は
使用できる数字とちょうど同じ
マッチ棒の使用本数のdp配列のindexが1になります。
i=1以降の場合
i=1以降の場合にはif文で見ている条件が一つ追加されます。
外側のループの中にある以下のものです。
if (i != 0 && dp[i] == int.MinValue) continue;
これはdp[i]の値が初期値かどうかを見ています。
初期値の場合にはcontinueして処理を飛ばしています。
例えば、
使える数字が3と6だとすると
使えるマッチ棒の数は5と6です。
i=0のときに
dp[5]とdp[6]に1を入れます。
5と6で作れる数字を並べてみると「5,6,10,11,12,15,16,17,18,20…」
となり、
いずれも「5と6」に
「5か6」を足した数しか作れないことが分かります。
「5,6,5+5,5+6,6+6,5+5+5,5+5+6,5+6+6,6+6+6,5+5+5+5…」
ここから
i=0の時点で値が入っていなかったdp配列のindexは
処理をせずに飛ばすということをしています。
i==1以降はこれを繰り返して
dp配列を最後まで埋めていきます。
✩上で出した桁数をもとに、
マッチ棒で作れる適当な数字を作る
コードは以下のようになっています。
//答えを格納する文字列を用意
var ans = string.Empty;
//数字の文字列を作成する
var match = N;
while (0<match)
{
for (int j=0;j<M;++j)
{
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
}
}
①答えを格納する文字列を用意
出力が64ビット整数型におさまらないので、文字列で答えを入れる変数を用意します。
//答えを格納する文字列を用意 var ans = string.Empty;
②数字の文字列を作る
//数字の文字列を作成する
var match = N;
while (0<match)
{
for (int j=0;j<M;++j)
{
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
}
}
まず、match=Nを定義していますが
これはマッチの本数です。
マッチをN本使ったときの数字を作りたいので
match=Nとしています。
while文の条件は
数字を答えの文字列に増やすたびに
match(＝使用するマッチ棒の数)を減らしていくので
matchが0以下になるとループが終了するようにしています。
次に、内側のループでは答えの文字列に実際に数字を入れています。
ここでは、一桁ずつ数字を当てはめています。
数字はなるべく大きいものを使いたいですが
一番初めにA[]を大きい順に並び替えているので
「j」を0から順番に当てはめていくと
自然に大きいものから当てはめていっていることになります。
for文の中身を見ていきます。
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
まず一番初めのif文は
dpのindexが外にでないかどうかを確認しています。
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
次のif文は以下のように変形できます。
dp[match - cost[A[j] - 1]] == dp[match] -1
dp[現在のマッチの本数 - 数字A[j]を作ったときに使用するマッチの本数] == dp[現在のマッチの本数] -1
dp[index]に入っているのは、
マッチ棒index本でできる数字の最大桁数なので
この条件式が成り立てば
A[j]が今追加されるべき数字だということが分かります。
そのあとは、
ansにA[j]を追加して
現在のマッチ棒の本数からA[j]を作るのに使うマッチ棒の本数を引き
また処理を使用できる最大の数から始めるために
breakしています。
これをマッチ棒が0になるまで繰り返せば、
答えの数字の列が出ます。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Dmondai {
static void Main()
{
var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = line[0];
var M = line[1];
//使える数字
var A= Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderByDescending(x=>x).ToArray();
//それぞれの数字で使用するマッチの本数（index+1=数字）
var cost = new int[] { 2,5,5,4,5,6,3,7,6};
//dp用の配列
var dp = new int[N+1];
//マッチ棒を0本使用してできる桁はないので、0を入れる
dp[0] = 0;
//dpの配列にintの最小の数を入れる（inde=0以外）
for (int i = 1; i <= N; ++i) dp[i] = int.MinValue;
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
//index確認
if (i != 0 && dp[i] == int.MinValue) continue;
//使用できる数字を一つずつ追加していく
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
//i本+数字で使用する本数ぶんを足すと、dp[i]+1桁の数字が作れる
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
//答えを格納する文字列を用意
var ans = string.Empty;
//数字の文字列を作成する
var match = N;
while (0<match)
{
for (int j=0;j<M;++j)
{
//index確認
if (match - cost[A[j] - 1] < 0) continue;
//現在のマッチの本数から、作る数字で使うマッチ棒の使用本数を引いた、本数で作ることのできる最大桁数と
//現在のマッチ棒で作ることのできる最大桁数-1が同じなら
//その数字を使用する
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
}
}
Console.WriteLine(ans);
}
}
C - Monsters Battle Royale
はじめに
競技プログラミング、AtCoder Beginner Contest 118
C - Monsters Battle Royale
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
N体のモンスターが居て、 それぞれ 1,2,...,N と番号付けられています。 はじめ、モンスターiの体力はAiです。 以降、体力が1以上のモンスターを生きているモンスターと呼びます。 生きているモンスターが1体になるまで以下を繰り返します。 ランダムに1体の生きているモンスターが ランダムに別の生きているモンスターに攻撃します。 その結果、 攻撃されたモンスターの体力を 攻撃したモンスターの体力と同じ値だけ減らします。 最後に生き残ったモンスターの最終的な体力の最小値を求めてください。
制約
入力は全て整数である。 2≤N≤10^5 1≤Ai≤10^9
入力
入力は以下の形式で標準入力から与えられる。 N A1 A2 ... AN
出力
最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。
解き方
こちらの解き方を参考にしています。
goo.gl
goo.gl
goo.gl
まず、モンスターが二体しかいない場合を考えてみます。
入力を以下とします。
2 48 30
これを問題文の通りに、戦わせてみると以下のような流れになります。
48 30 18 30 18 12 6 12 6 6 0 6
そして、この流れをよく見てみると
ユークリッドの互除法と同じであることに気づきます。
48%30=18 30%18=12 18%12=6 12%6=6 6%6=0
つまり、最大公約数が答えということになります。
三体目以降は
一、二体目で出した最大公約数の体力を持ったモンスターと
次のモンスターがいると考えて
最大公約数を順番に出していきます。
最終的に出てきた最大公約数が答えです。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var ans = A[0];
for (int i = 1; i < N; ++i)
{
//大きい方をaに入れる
var a = ans < A[i] ? A[i] : ans;
//小さい方をbに入れる
var b = a == ans ? A[i] : ans;
//最大公約数を得る
ans = GetGcd(a, b);
}
Console.WriteLine(ans);
}
//最大公約数を出す
static long GetGcd(long a, long b)
{
while (b != 0)
{
var r = a % b;
a = b;
b = r;
}
return a;
}
}
D - Ears
はじめに
競技プログラミング、みんなのプロコン2019
D - Ears
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
数直線上にすぬけ君がいます。 すぬけ君は L個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。 ・座標0未満の点や座標がLより大きい点を通ることはない ・整数座標の点で散歩を開始し、整数座標の点で散歩を終了する ・整数座標の点でのみ、進む方向を変えることができる すぬけ君は、座標が整数iを用いてi−0.5と表される点を通るたびに、i番目の耳に石を1個入れます。 すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、 各iに対しすぬけ君のi番目の耳にはAi個の石が入っているようにしたいです。 すぬけ君の耳をひとつ選び、石を1個入れる石が1個以上入っているすぬけ君の耳をひとつ選び、石を1個取り出す すぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。
制約
・1≤L≤2×10^5 ・0≤Ai≤10^9(1≤i≤L) 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。 L A1 : AL
出力
必要な操作の回数の最小値を出力せよ。
解き方
こちらの解き方を参考にしています。 goo.gl goo.gl goo.gl goo.gl
りんごさんの操作の回数は
すぬけ君がどれだけ入力に沿って歩けるかどうかによって決まるので
まずすぬけ君が歩いて作れる石のパターンを考えます。
すぬけ君が歩いて作れる石のパターンを考えると
次の5パターンがあることが分かります。
・0偶奇偶0
・0偶奇0
・0奇偶0
・0偶0
・0奇0
このパターンをよく見ると
一番上の「0偶奇偶0」が下の4つのパターンを全て含んでいることが分かります。
そのため、ここからは一番上の「0偶奇偶0」だけに着目していきます。
・0偶奇偶0
・0偶奇偶0
・0偶奇偶0
・0偶奇偶0
・0偶奇偶0
（この時点では少し分かりにくいですが、
dpを回す段になると
なぜ一番上だけでいいのか少し分かり易くなると思います。）
このパターンをもとに動的計画法でこの問題を解いていくのですが
dpの形は以下のようになります。
dp[Ai,すぬけ君が歩いて作れる石のパターンの区分け]＝ここまでで、りんごさんが操作を行う最小回数
「すぬけ君が歩いて作れる石のパターンの区分け」は、先程の「0偶奇偶0」です。
動的計画法ができるように、
これらの区分けに以下のように番号をふっておきます。
0→0（領域0） 偶→1（領域1） 奇→2（領域2） 偶→3（領域3） 0→4（領域4）
これらをもとに
例えば、dp[0,0]は
「「A0」を「領域0」としたときの、りんごさんが操作を行う最小回数」という意味になります。
コードを見ながら具体的に値を入れてみていきます。
✩準備
まず動的計画法を始めるために配列を用意します。
//A1～ALを格納する配列
var A = new List<long>();
for (int i = 0; i < L; ++i)
{
A.Add(Int64.Parse(Console.ReadLine()));
}
//LはAi
//5は領域0～領域4
var dp = new long[L, 5];
Lの部分をA[0]から順番に埋めていきます。
✩A[0]
まず領域0は「0偶奇偶0」の一番初めの「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[0]」となります。
（すぬけ君が歩かないので、りんごさんがA[0]回石を入れる操作を繰り返す）
dp[0,0]=A[0];
次に領域1は「0偶奇偶0」の一番初めの「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[0]==0?2:A[0]％2」になります。
（A[0]が0なら2回、偶数なら0回、奇数なら1回）
dp[0,1]=A[0]==0?2:A0％2;
次に領域2について見ていきます。
ここは、「0偶奇偶0」の「奇」の部分です。
ここはすぬけ君が「奇数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[0]==0?1:(A[0]+1)%2」になります。
（A[0]が0なら1回、偶数なら1回、奇数なら0回）
dp[0,2]=A[0]==0?1:(A[0]+1)%2;
次に領域3について見ていきます。
ここは、「0偶奇偶0」の二番目に出てくる「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[0]==0?2:A[0]％2」になります。
（A[0]が0なら2回、偶数なら0回、奇数なら1回）
dp[0,3]=A[0]==0?2:A[0]％2;
領域4は「0偶奇偶0」の二番目に出てくる「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[0]」となります。
（すぬけ君が歩かないので、りんごさんがA[0]回石を入れる操作を繰り返す）
dp[0,4]=A[0];
✩A[1]
次に、A[1]について見ていきます。
まず領域0は「0偶奇偶0」の一番初めの「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[1]」となります。
（すぬけ君が歩かないので、りんごさんがA[1]回石を入れる操作を繰り返す）
ただし、A[1]の前にはA[0]があり
A[1]が領域0になるということは
A[0]も「領域0」であることを示すので
A[0]の値を足しておきます。
dp[0,0]=A[1]+dp[0,0]/*(=A[0])*/;
次に領域1は「0偶奇偶0」の一番初めの「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[1]==0?2:A[1]％2」になります。
（A[1]が0なら2回、偶数なら0回、奇数なら1回）
ただし、A[1]の前にはA[0]があり、ここで2パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
①②どちらを取るかは、りんごさんの操作を最小にしたいので
値の小さいほうを取ります。
仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,A[0]が領域1のパターン);
として、値が小さいほうを「A[1]==0?2:A[1]％2」に足します。
var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,dp[0,1]/*(=A[0]が領域1のパターン)*/); dp[1,1]=A[1]==0?2:A[1]％2+value;
次に領域2について見ていきます。
ここは、「0偶奇偶0」の「奇」の部分です。
ここはすぬけ君が「奇数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[1]==0?1:(A[1]+1)%2」になります。
（A[1]が0なら1回、偶数なら1回、奇数なら0回）
ただし、A[1]の前にはA[0]があり、ここで3パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
③A[0]が領域2のパターン
①②③どれを取るかは、りんごさんの操作を最小にしたいので
値の小さいものを取ります。
仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,
Math.Min(A[0]が領域1のパターン,A[0]が領域2のパターン));
として、値が小さいものを「A[0]==0?1:(A[0]+1)%2」に足します。
var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,
Math.Min(dp[0,1]/*(=A[0]が領域1のパターン)*/,dp[0,2]/*(=A[0]が領域2のパターン)*/));
dp[1,2]=A[1]==0?1:(A[1]+1)%2;
次に領域3は「0偶奇偶0」の二番目に出てくるの「偶」の部分です。
ここはすぬけ君が「偶数回」歩いてくれるので
りんごさんが石を入れる数、或いは石を抜く数は
「A[1]==0?2:A[1]％2」になります。
（A[1]が0なら2回、偶数なら0回、奇数なら1回）
ただし、A[1]の前にはA[0]があり、ここで4パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
③A[0]が領域2のパターン
④A[0]が領域3のパターン
①②③④どれを取るかは、りんごさんの操作を最小にしたいので
値の小さいものを取ります。
仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,
Math.Min(A[0]が領域1のパターン,
Math.Min(A[0]が領域2のパターン,A[0]が領域3のパターン)));
として、値が小さいものを「A[1]==0?2:A[1]％2」に足します。
var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,
Math.Min(dp[0,1]/*(=A[0]が領域1のパターン)*/,
Math.Min(dp[0,2]/*(=A[0]が領域2のパターン)*/,dp[0,3]/*(=A[0]が領域3のパターン)*/)));
dp[1,1]=A[1]==0?2:A[1]％2+value;
領域4は「0偶奇偶0」の二番目に出てくるの「0」の部分なので
すぬけ君はこの部分を歩きません。
なので、りんごさんの操作回数は
石を入れる数そのままの「A[1]」となります。
（すぬけ君が歩かないので、りんごさんがA[1]回石を入れる操作を繰り返す）
ただし、A[1]の前にはA[0]があり、ここで5パターン考えが出てきます。
①A[0]が領域0のパターン
②A[0]が領域1のパターン
③A[0]が領域2のパターン
④A[0]が領域3のパターン
⑤A[0]が領域4のパターン
①②③④⑤どれを取るかは、りんごさんの操作を最小にしたいので
値の小さいものを取ります。
仮にこれをvalueとすると
value=Math.Min(A[0]が領域0のパターン,
Math.Min(A[0]が領域1のパターン,
Math.Min(A[0]が領域2のパターン,
Math.Min(A[0]が領域3のパターン,A[0]が領域4のパターン))));
として、値が小さいものを「A[1]」に足します。
var value=Math.Min(dp[0,0]/*(=A[0]が領域0のパターン)*/,
Math.Min(dp[0,1]/*(=A[0]が領域1のパターン)*/,
Math.Min(dp[0,2]/*(=A[0]が領域2のパターン)*/,
Math.Min(dp[0,3]/*(=A[0]が領域3のパターン)*/,dp[0,4]/*(=A[0]が領域4のパターン)*/))));
dp[1,4]=A[1]+value;
あとのA[2]以降はこの操作を繰り返し、
dp[L-1,4]までいけば動的計画法はおしまいです。
✩最も小さい値を出す
最後に
dp[L-1,0]（1番初めの0で終わるパターン）,
dp[L-1,1]（1番初めの偶で終わるパターン）,
dp[L-1,2]（奇で終わるパターン）,
dp[L-1,3]（二番目に出てくる偶で終わるパターン）,
dp[L-1,4]（二番目に出てくる0で終わるパターン）の中で
最も最小の値を出せばそれが答えになります。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var L = Int64.Parse(Console.ReadLine());
var A = new List<long>();
for (int i = 0; i < L; ++i)
{
A.Add(Int64.Parse(Console.ReadLine()));
}
//動的計画法
var dp = new long[L, 5];
for (int i = 0; i < L; ++i)
{
var num = A[i] % 2;
//偶数領域のコスト
var even = A[i] == 0 ? 2 : num == 0 ? 0 : 1;
//奇数領域のコスト
var odd = A[i] == 0 ? 1 : num == 0 ? 1 : 0;
//領域0（0）
//自分の前の値すべてが領域0に属していたときのコスト
var value = GetValue(dp, i, 0);
//自分もさらに領域0に属すときのコスト
dp[i, 0] = A[i] + value;
//領域1（偶）
//自分の前までの値が、領域0と領域1どちらかに属したときの最小コスト
value = GetValue(dp, i, 1, value);
//自分が領域1に属すときのコスト
dp[i, 1] = even + value;
//領域2（奇）
//自分の前までの値が、領域0、領域1、領域2のどれかに属したときの最小コスト
value = GetValue(dp, i, 2, value);
//自分が領域2に属すときのコスト
dp[i, 2] = odd + value;
//領域3（偶）
//自分の前までの値が、領域0、領域1、領域2どれかに属したときの最小コスト
value = GetValue(dp, i, 3, value);
//自分が領域3に属すときのコスト
dp[i, 3] = even + value;
//領域4（0）
//自分の前までの値が、領域0、領域1、領域2、領域3どれかに属したときの最小コスト
value = GetValue(dp, i, 4, value);
//自分が領域4に属すときのコスト
dp[i, 4] = A[i] + value;
}
//一番小さいパターンを出す
var ans = Math.Min(dp[L - 1, 0],
Math.Min(dp[L - 1, 1],
Math.Min(dp[L - 1, 2],
Math.Min(dp[L - 1, 3], dp[L - 1, 4]))));
Console.WriteLine(ans);
}
//value（自分の手前までの値の最小コスト）を返す
static long GetValue(long[,] dp, long num, int section, long value = long.MaxValue)
{
//A[0]は自分の前に値がないので、前の値は考えない
if (num == 0) return 0;
else
{
switch (section)
{
//領域0なので、自分の前の値全てが領域0に属していたときのコスト
case 0: return dp[num - 1, section];
//自分の前の値の、領域ぶんの可能性の中の、最小コストを返す
default: return Math.Min(value, dp[num - 1, section]);
}
}
}
}
