おはようございます。しほみんです。
ABC160に参加したのでその復習をします。まあ、E問題をちゃんと解きたかったですね....あと一歩って感じでしょうか。
コードは帰宅後にあげます。ちょっと設定間違えた…今日も仕事はあるので
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800度になりました。緑と茶をうろちょろしています。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。パフォーマンスを安定的に1000以上とる。
今回は60分でABCDの4完でした。D問題を解くのにちょっと時間を費やしてしまい、パフォを落とした形です。でも、パフォーマンスも966でそこそこ調子よかったです。レーディングも789→808となってようやく緑コーダになれました。
本当はE問題まで解いてもっとレートをあげたかったなと感じます。 D問題も もっと早く気が付けばよかったなあという感じです。悔しいですが一つずつ振り返ります。
ここから問題です。
A問題
coffeeみたいな文字列かどうか判定してください。
具体的には3文字目と4文字目、5文字目と6文字目が一致するものを見つけてください。
上のまんま実装します。
（実装例）
if(s[2] == s[3] && s[4] == s[5])
Console.WriteLine("Yes");
else
Conosole.WriteLine("No");
B問題
X円持っています。500円玉1枚ごとに1000の幸福度、5円玉1枚ごとに5の幸福度が得られます。
X円のときの一番大きい幸福度を求めなさい。
500円玉は1円当たり2幸福、5円玉は1円当たり1幸福です。
よって、できるだけ500円を持った後、5円玉を持てばいいことになります。
500円玉を一番大きく持てる状態を考えます。そのあと、あまりで5円玉が何枚持てるか求めます。この時が最大です。
（構成例）
int a = x/500;
int b = (x - a * 500) /5;
Console.WriteLine(a * 1000 + b * 5);
（コードでは一行で答え出力してますが、こっちのほうが確実な気がします）
C問題
円状の湖があります。そこにNこの家が、あります。すべての家を訪問するとき一番小さい距離はいくつですか。
まあ、素直に1番目からN番目、2番目から1番目、3番目から2番目、....みたいに家の訪れかたを考えればよいです。また、この距離の求め方は一周がKと決まっている以上、i+1番目とi番目の家の差をKから引けば求められます。
最初の1番目からN番目までだけは実装上、別途でやると簡単だと思います。
(構成例）
あらかじめ、a[i]にi番目の家の原点からの距離が入っている。
for(int i = 1;i < n;i++)
temp = K - (a[i] - a[i -1]) ;
ans = Min(temp, ans);
temp2 = a[n-1] - a[0];
ans = Min(temp2, ans);
Console.WriteLine(ans);
D問題
無向グラフで1からNまで順繰りにつながっています。
途中、xからyまでは1の距離でつないでいます。
このとき、それぞれ2つの場所の距離を1からN-1まで求めなさい
わかりづらいので図で書くとこんな感じです。（Atcoder160例題引用）
一応、N = 2000とかなので二重ループは使えます。つまり、全部の組み合わせがそれぞれ度の距離であるかは計算しても間に合います。
ということでまずはそれぞれiとjの距離を求める方法を考えていきます。
ここから一般化して考えます。
とはいえ高々ショートカットがあるかどうかなので、そこで違いを比べます。
座標iと座標jの差を単純に考えます。
このiとjの間にショートカットあるとき、
このときは2ついき方があります。
1. ショートカットを使うとき
2. ショートカットを使わないとき
1のとき、ショートカットがxとyで結ばれているとすると
Abs(x - i) + Abs(y - j) +1です。（図を参照してください。いき方Aの方です）
2のときは単純にj - iです。
ということはこのどっちか小さい方が距離になります。
ショートカットがなければ単純にj - iです。
（図）
ここまで来たらもうそのように実装するだけです。
この問題も1つ条件が追加されたとき、何が影響するかを考えて解きます。今回はショートカットができるため、移動距離が小さくなる恐れがある状態を考えてすべて求めればよかったことになります。
E問題
A個赤リンゴがあります。おいしさがそれぞれ設定されています。
B個緑リンゴがあります。おいしさがそれぞれ設定されています。
C個無色リンゴがあります。おいしさがそれぞれ設定されています。
無色リンゴは赤か緑に着色して食べれます。
赤リンゴx個、緑リンゴy個食べるとき、最大のおいしさを求めてください。
まあ、気が付くかどうかな気がします。
まず、赤リンゴのうち最大でもx個しか食べません。一方、緑リンゴも最大でもy個しか食べません。
なので、まずはおいしい順に赤リンゴ、緑リンゴをx,y個食べるが候補です。
しかし、無色リンゴの中で、赤リンゴ、緑リンゴの候補の中よりおいしいものがあったらそれを食べる必要があります。
ということは、無色リンゴは既存の候補リンゴと入れ替えればいいことが分かります。
あとはこの方法ですが、普通に候補であるリンゴたちのうち、頭からx+y個取り出せばよいってわかります。
つまり、候補となる、x+y+c個のリンゴをソートして頭からx+y個とって食べればよいのです。
これは入れる無色リンゴ個数と取り除く色リンゴ個数が一致しているので、のぞかれたらその対応した色を塗ればいいだけとわかります。
詳しくはコードを見てください。
最後に....
E問題みたいに問題を深く読んですることを理解するのも大切です。アルゴリズムの力がなくても解けるこういう問題からまずはとれるようにしたいですね....
ではでは。
