yukicoder No.225 文字列変更(medium)
yukicoderに参戦。No.225は解けなかったけれど、自分にとって良いレベルの問題だったためメモ。
コンテスト中に書いたコードは以下の通り。
#include <iostream> #include <algorithm> using namespace std; int solve(string s, string t, int n, int m, int itr = 0){ if(itr == m) return 0; if(itr == n) return m - n; if(s[itr] == t[itr]) return solve(s, t, n, m, itr + 1); int mincost; mincost = solve(s, t, n, m, itr + 1) + 1; mincost = min(mincost, solve(s.substr(1, n - 1), t, n - 1, m, itr) + 1); mincost = min(mincost, solve("a" + s, t, n + 1, m, itr + 1) + 1); return mincost; } int main(){ int n, m; cin >> n >> m; string s, t; cin >> s >> t; cout << solve(s, t, n, m) << endl; }
基本的に考え方はこれで良かったはず。TLEになってしまいましたが、自分の中ではここまでコードを書けるようになってすこし満足。でも、上を見ましょう。後はこれをDynamic Programmingで効率的に解きましょう。
#include <iostream> #include <algorithm> using namespace std; #define MAX 1100 #define INF 1<<29 void chmin(int& a, int b){ if(a > b) a = b; } int n, m; string S, T; int dp[MAX][MAX]; int main(){ cin >> n >> m; cin >> S >> T; S += "-"; T += "-"; for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) dp[i][j] = INF; dp[0][0] = 0; for(int i = 0; i <= n; ++i){ for(int j = 0; j <= m; ++j){ if(S[i] == T[j]) chmin(dp[i+1][j+1], dp[i][j]); else chmin(dp[i+1][j+1], dp[i][j] + 1); chmin(dp[i+1][j], dp[i][j] + 1); chmin(dp[i][j+1], dp[i][j] + 1); } } cout << dp[n][m] << endl; }
模範解答をほぼ丸パクリですね...でも良い勉強になりました。
全探索が出来るようになってきたのでDPを極めるぞ！！！
101 Hack May'15
いやー全然ダメでした。205/556位、完答は1問のみと厳しい結果でした。悔しかったのでModerateまでは大会後にEditorialを見ずに解いた感じでは3問完答までは少なくともいけた・・・。まぁ、前回初参戦でbronze medalをとったので完全に浮かれてた自分が悪いんですけどねw
Counting Good Partitions of a String (Easy)
えーと。この問題は大会終了後まで問題文の意味が理解出来ませんでした。kの値を最大化するものだと思っていて、なぜ1000を法にして解かないといけないんだろうとか思っていました。Discussionsを見ると同じ勘違いをしてる人がいますね。（私も納得いかなくて書き込んでるのはここだけの秘密w）
大会終了後に解いたコードを紹介
int n = str.size(), count = 0, ch[26]; for(int i = 0; i < 26; i++){ ch[i] = 0; } for(int i = 0; i < n; i++){ ch[str[i] - 'a']++; } ch[str[0] - 'a'] = 1; int result = 1; for(int i = 0; i < 26; i++){ if(ch[i] > 0){ result = result * ch[i] % 1000; count++; } } cout << result << endl;
まず、全ての文字が何回登場しているかをchに記録。例えば、aが3個あるならそのうち１つをpartitionの先頭にするためresultを3倍。ただし、inputの最初にくる文字は必ずpartitionの最初になるため1通り。これを1000を法にして計算すると解けました。
Devu, Amit, and Good Integers (Easy)
今大会で唯一解けた問題。
cin >> n >> l >> r;
for(int i = 0; i < n; i++){
cin >> tmp;
if(tmp > r){
a[i] = tmp - r;
} else if (tmp < l){
a[i] = l - tmp;
} else {
a[i] = 0;
}
}
sort(a, a + n);
for(int i = 1; i < n; i++){
a[i] = a[i] + a[i - 1];
}
for(int i = 0; i < n; i++){
if(i)
cout << " ";
cout << a[n - i - 1];
}
cout << endl;
まずは、入力された数字に何回操作を行う必要があるかをaに格納します。そしてこれをソート。次にa[i]=a[i]+a[i-1]の漸化式でその前にある時間を足し合わせることでa[i]はi+1個の数字をgood integerにするための操作数になります。そして、k個の数字を選ぶと少なくとも1個はgood integerであるということはn-k+1個のgood integerがあればいいためaを逆順に出力して終了。
Devu and a Wonderful Game (Moderate)
今大会はEasyで時間を使いすぎて、この問題を解き始めたときには時間がほとんど残っておらず、しかも急いで書き上げたコードはwhileの処理をミスってSample Inputは通ったもののそれ以外では無限ループに陥ってTLE。
まずは、何も操作を行うことなく風船は割れていくので残る風船の個数を出力する関数をつくりました。
int convert(string str){ string tmp; int n; while(true){ n = str.size(); if(n == 0 || n == 1) break; tmp = ""; if(str[0] != str[1]) tmp += str[0]; for(int i = 1; i < n - 1; i++){ if(str[i] != str[i - 1] && str[i] != str[i + 1]) tmp += str[i]; } if(str[n - 2] != str[n - 1]) tmp += str[n - 1]; if(n == tmp.size()){ break; } str = tmp; } return n; }
正直もっとスマートなコードに直せる気がするのですが現時点ではこんな感じです。他の人のコードをみて勉強してみるかな。そして、結果を出力する部分。
cin >> str; int len = convert(str); if(len <= 2){ cout << 0 << " " << 0 << endl; } else { cout << 1 << " " << ceil((double) (len - 2)/4) << endl; }
3つ以上の風船が残ったときに注目。真ん中の風船2つを交換すれば残りの風船は1つ以下になります。また、端にある風船とその隣の風船を交換すれば4つの風船が割れ、これが一回の操作で割る風船の最小値となります（風船が4つ以上残っていると仮定した場合ですが）。これを考慮して最大の操作数はceil((double) (len - 2)/4)と天井関数を使ってみました。でも天井関数を使わなくても出来ますねw
とりあえず、解いたのはここまで。まだまだへなちょこだと実感した大会でした。
Codeforces Round #303 (Div. 2)
初めてCodeforcesに参戦しました。結果は5問中4問正解で2826人出場した中で254位でした。そしてレイティングは1500 → 1704でCandidate Masterに！！ん？これってDiv.1じゃないか。#304(Div.2)にも参加する気でワクワクしていたのでちょっと複雑wまぁレイティングが変化しないけど問題を解くことはできるし、時間と体力があれば参戦しようかと思ってます。以下今回の問題の簡単なサマリー。
A - Toy Cars
問題文を3周くらい読んでようやく理解したのはここだけの秘密w Inputは総当たりの対戦表になってるんですね。つまり、各行をみて1(自分のみ負け)または3(両方負け)が１つでもあれば負けです。そうでない行の数を数えれば終了!
B - Equidistant String
最初にSusie loves symmetryと見て回文にしないといけないと勘違い。少々難しいと感じて飛ばしましたw C, Dを解き終えた後にもう一度問題を読んでも勘違いに気づかず、Sample Outputをみてようやく気づきました。正解者の多い問題だったので解けなかったらどうしようかと正直ちょっと焦りましたw
C - Woodcutters
この問題はGreedyで解けますね。自分はまず、両端はそれぞれ外側に倒す。それ以外は左側の木から考えていき、左に倒せるならそれを優先、右にも倒せないならばその木は倒すことができないと考えました。
if(n == 1){ cout << 1 << endl; } else if (n == 2){ cout << 2 << endl; } else { int result = 2; for(int i = 1; i < n - 1; i++){ if(x[i - 1] < x[i] - h[i]){ result++; } else if(x[i] + h[i] < x[i + 1]){ result++; x[i] = x[i] + h[i]; } } cout << result << endl; }
D - Queue
これはソートをして、時間の小さい方からGreedyに考えればいけますね。
E - Paths and Trees
これが解けませんでした。ダイクストラ法など勉強はしてきたつもりだったんですけどまだまだですね。今の自分はグラフが一番弱いです。そろそろ対策をせねば。
The Magic Lines
今回はHackerRankにて、The Magic Linesという大会に参加しました。結果は1/1292位!!とはいえ、同率一位が239人いて、自分は忙しかったので期限ギリギリにsubmitしたため時間を考慮すると230位でした。初めてコードの一部を補完する形式のコンテストに参加しましたが、コード全体の意味が分かっていなくても変数の名前がbinomになってるから二項係数を計算すればいいんだろうなとかちょっといい加減な解き方をしても正解になるような問題でした。
UnKoder #04
GW最高。ってな訳でプロコン連日参加中。今回はUnKoder#04に参加して、19/36位でした。
Islands in Circle
とってもシンプルなコードになりました。
int main() { int N, K, result; cin >> N >> K; if(N % 2 == 1){ result = min(K + 1, N); }else{ result = min(K + 1, N / 2); } cout << result << endl; return 0; }
ただ、ここまでたどり着くのに一苦労。探索をして解きました。するとSegmentation Errorに。どうすればいいんだーと頭を抱えながら図を書いて規則性を探していると実は凄く分かりやすい規則性があることを発見してこうなりました。
Book Stacks
これはすぐに解けました。冊数の一番少ない山をまずは崩し、そこに読み終わった本を山積みしていくと操作回数が最小になります。
int main() { int N; cin >> N; int A[N], minA=100, total = 0; for(int i = 0; i < N; i++){ cin >> A[i]; minA = min(minA, A[i]); total += 2 * A[i] - 1; } total += minA - 1; cout << total << endl; return 0; }
この2問しか解けませんでした。後の2問にも挑戦してみたのですが、無理でした。
XOR(排他的論理和)の計算
Grundy数を計算する際にXORの計算をしました。Exclusive orとか日本語では排他的論理和と言われているものですね。基本的なことですが、どうやって計算するのかを紹介します。
まずは基本から
まずは表で計算結果を見てみましょう。
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
このようになります。なお、0をfalseあるいは偽、1をtrueあるいは真に置き換えても大丈夫です。プログラミングでboolを使ったことある方ならよく見る表現ですよね。同じものを入力すれば0、違うものを入力すれば1になるのがXORです。では、入力の個数を増やして見ましょう。
| A | B | C | A XOR B XOR C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
こんな感じです。個人的に、今回の規則性はこの並びだと分かりにくいと思うので並べ直してみます。
| A | B | C | A XOR B XOR C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 |
これで規則性が見えてきたのではないでしょうか。1が偶数個(0個も含む)あれば出力は0、1が奇数個あれば出力は1になります。入力がさらに多くてもこの規則通りになります。なお、計算の順番が違っても計算結果は同じになるため
(A XOR B) XOR C
A XOR (B XOR C)
のどちらで解いても良いですし、
(A XOR C) XOR B
と順番を入れ替えても構いません。では、今のところ真理値(0と1あるいはfalseとtrue)でしか計算していませんが、これを拡張して実数でも計算出来るようにします。
Grundy数 その3
前回までにGrundy数についての説明をしました。augusuto04.hatenablog.com
augusuto04.hatenablog.com
長くなったGrundy数の記事も今回でラスト。実際に使ってみます。
実践例
AtCoder Regular Contest 038のC - 茶碗と豆に挑戦します。
#include <iostream> using namespace std; static const int NMAX = 100000; //Cがラベルの番号、Aが豆の数、gはGrundy数 int N, C[NMAX], A[NMAX], g[NMAX]; int main(){ cin >> N; C[0] = A[0] = g[0] = 0; int result = 0; for(int i = 1; i <= N - 1; i++){ cin >> C[i] >> A[i]; g[i] = 0; //茶碗iにおけるGrundy数を求める while(true){ bool d = true; for(int j = 1; j <= C[i]; j++){ if(g[i] == g[i - j]){ g[i]++; d = false; break; } } if(d == true) break; } //全体のGrundy数を更新する for(int j = 0; j < A[i]; j++){ result = result ^ g[i]; } } if(result > 0) cout << "First" << endl; else cout << "Second" << endl; }
ただし、これではNとAの値が小さい問題しか解けず、他はタイムアウトになってしまうため部分点の80点しかとれません（まぁ初心者の私にとっては80点でも取れれば大きいんですけどねw）。次の部分点を取るにはAの値が大きいときに対応する必要があります。なので、Grundy数の更新の計算量を少なくしました。
//全体のGrundy数を更新する for(int j = 0; j < A[i]; j++){ result = result ^ g[i]; }
上のような計算をしていました。しかし、同じ数を繰り返しxorの計算をすることに実はあまり意味がありません。
a xor a = 0
a xor 0 = a
となるため、同じ数を2回計算するときは無視します。すると次のようになります。
//全体のGrundy数を更新する if(A[i] % 2 == 1){ result = result ^ g[i]; }
つまり、偶数回(0回も含む)更新するときは値が変わらないため行わない。奇数回更新するときは1回更新することと同じである。この変更を行うことで100点取れました！ただ、満点は104点です。どうやらg[i]の求め方を工夫する必要があるみたいですね。私はまだ出来ていません。そのやり方やコードの改善等あったら教えていただけると有り難いです。
