おはようございます。しほみんです。
ABC167の見直しです。といってもE問題解けてたのに最後変数を代入ミスでACできなかったのでつらかったです。とれたはずの水色パフォーマンスを失ったきつい回でした....
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。PAST58点の初級レベル。
・基本的に時間がないのでぶっつけ本番でやっている。現在48回参加、もうすぐ一年。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABCD、55分でした。パフォーマンスは過去最高1152で、緑後半でした。レートも無事818で、緑復活です。
ミスをしなくなったのがよかったです。ただ、先ほど言ったように解けてたのに実装できなかったことをしてしまったので大反省です。
こういうのいまだになれない...まだまだ実装力が足りないですね....
もういろいろなものは作れるようになったりライブラリが整ってきたので、あとは問題に対して適切なアルゴリズムを使えるかどうか練習ですね。
ということでE問題まで振り返りますが、長いのでA-CとD,Eで分けます。
今回はA-C問題まで書きます。
ここから問題です。
A問題
webサービスにID登録しようとします。
sをID登録したかったのですが既に登録済みでした。
なのでsに1文字加えたID登録しようと思います。
それがtなのですが、tがそれを満たしているか判定してください。
まあt = s+(ほかの1文字）なので、
sの文字列とtの最後の一文字以外が同じか判定すればよいです。
1文字比較かtを1文字消して考えればよいでしょう。
実際は前者で書きましたが、後者で書いてみます。
（構成例）
string s = Console.ReadLine();
string t = Console.ReadLine();
t1 = t.Substring(0, s.Length)
if(s == t1)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
B問題
1, 0, -1の書かれたカードはA, B, C枚あります。
K枚取り出すとき、最大値はいくつでしょうか。
できるだけ1をとって、-1を取らないようにするのが最大です。
1, 0, -1の順にそれぞれA, B, C枚ずつ取っていきます。
K < Aであれば、全部1のカードなので、最大値はKです。
A<= K <= A +Bならば、1をA枚とって、残りを0にします。この時は最大値Aです。
A + B < K ならば、1をA枚、0をB枚、-1をK-A-B枚とります。この時はA-(K-A-B)です。
この条件分岐を書けばよいです。このとき、前の条件で分岐してしまったものは除かれるので、右辺だけ書けば十分です。すっきりしたコードになります。
（構成例）
if(K < A)
Console.WriteLine(K);
else if(K < A+ B)
Console.WriteLIne(A);
else
Console.WriteLine(2*A-K+ B);
C問題
競技プログラミングを学びたいです。M個のアルゴリズムを覚えたいです。
それぞれの知識量は0です。
N個の本があり、その本のコストはCで、
本を読むとそれぞれの知識をMi得られます。
すべての知識が、X以上になることが目的です。
この時、与えられた本を使って一番小さいコストで目的を達成したいです。
最小コストを求めなさい。
制約条件を見ます。Nは最大でも12です。
よって、本の選び方は2の12乗で、高々4000通りです。
なので、全部調べてみて条件を満たす最小のコストを出します。
こういう時はこの本を選んだどうかだけなのでビット探索法が便利です。
それぞれのビットの位置が本の個数、ビットが1なら選択、0なら選ばないです。
例えば、10だと、00001010となり、8冊の本の場合、2,4冊目の本を選ぶことになります。(下一桁から1冊目とする）。
ということで実際実装例を挙げます。
全数は1 << n、i番目の本が選ばれたかは(i >> j) & 1が1かどうかで分かります。
for(int i = 0;i < (1 <<n);i++)
for(int j = 0; j < n;j++)
if( ((i >> j) & 1 )== 1)
count += cost[j];(costはj番目の本をコストを記録）
for(int k = 0;k < n;k++)
sum[k] = aj[k];
（sumは今までの知識量の和、aj[k]はj番目の本のkの知識量を記録）
for(int j = 0;j < n;j++)（ここで条件満たすか判定）
if(sum[j] <x)
flag = 1;
break;
if(flag == 0)
ans = Math.Min(ans, count);
少し複雑ですが、基本はビット全探索です。
今回はここまでにします。ではでは。
