【AtCoderBeginnerContest045 C】この体にも慣れてきたな
スポンサードリンク
こんにちは。
コンテストではC# だけではなくC++も使うことを心に決めてから、早いもので5週間ばかりが経とうとしています。
今日はC++でC問題に挑戦しましたので、現状報告とともに問題点を洗い出します。
ABC061 C
https://atcoder.jp/contests/abc045/tasks/arc061_a
問題概要
1,2,3,4,5,6,7,8,9からなる数字の羅列Sが与えられる。
+記号を間にいくつか挟むことを考える。(0でもよい)
+記号の入れ方はたくさんあるけど、全パターンの入れ方を試す。
できる数列全部計算して出てきた数字の和を求めよ。
Sの長さは最大10だそうです。
考えたこと
一瞬、どの桁まで見て計算した、というDPを書こうとしたけど思いとどまった。
最悪数字が10個ってことは、数字の間は9個。
2^9=512パターンなので、多分割と余裕で全探索ができる。
n番目の数字とn+1番目の数字の間に+記号を入れるかどうかをplus[n]が1か0かで決めて、全部試して全部足しました。
plusの次の状態を求める関数、plusとSから数式をstringで出力する関数、+入りの数式を計算してくれる関数を定義して、じゅんぐりにまわしました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <iostream> #include <string> #include <algorithm> #include <list> #include <vector> #include <map> using namespace std; string addplus(string, string); long long calc(string); string next(string); int main() { //S=1なら1個、S=2なら2個、S=nなら、各数字の間に入れる入れないがあるので2^(n-1)個。 string S; cin >> S; int veclen = S.length()-1; string plus = ""; string last = ""; for (int i = 0; i < veclen; i++) { plus += "0"; last += "1"; } long long output; output = 0; while (plus != last) { string next_siki = addplus(S, plus); output += calc(next_siki); plus = next(plus); } output += calc(addplus(S, plus)); cout << output << endl; return 0; } string next(string s) { string output = s; int keta = '1'; int zero = '0'; int one = '1'; int two = '2'; for (int i = s.length() - 1; i != -1; i--) { if (s[i] + keta == zero + zero) { output[i] = '0'; keta = '0'; } if (s[i] + keta == zero + one) { output[i] = '1'; keta = '0'; } if (s[i] + keta == one + one) { output[i] = '0'; keta = '1'; } } return output; } long long calc(string s) { long long output = 0; long long lookingnumber = 0; for (int i = 0; i < s.length(); i++) { if (s[i] != '+') { lookingnumber *= 10; long long keta = s[i]-'1'+1; lookingnumber += keta; } else { output += lookingnumber; lookingnumber = 0; } } output += lookingnumber; return output; } string addplus(string s, string plus) { string output = s; for (int i = plus.length() - 1; i != -1; i--) { if (plus[i] == '1') { output = output.substr(0, i+1) + "+" + output.substr(i + 1, output.length()-1); } } return output; } |
C#userから見た問題点が一つ大きく目立ちます。
それは、
「型変換が雑」
使うプリミティブ型データ（言葉の使い方あってる？）としては、long,string,int,char,doubleぐらいでしょうか。
longとintとdouble間の変換はとりあえずおいておくにしても、stringとcharとint間の変換は見過ごせません。
C#なら、
string→charは、s[0]がcharになるし、
char→stringはchar c;に対して string s = “"+c;とすれば変換できる。
int→char、char→intはそんなに使わないから置いといて、
string→intはint.Parse(string)すればよくて、
int→stringはcharと同じくstring s = “" +i;とでもすればよい。
これがC++となるとまったくわからず、
string→charは同じくs[0]でいいんだけど、
charをstringにできない。哀れ。
string→intもわからないからcharにして’1’引いて1足すという悪魔みたいなコード生成してるし、
int→stringは今回使っていないけどこれもわからない。
競技プログラミングに限ったことではないが、これぐらいの型変換はできるようになっておかないといけないのでは。
競プロで一番困るのは、string[n]で表記して取り出したcharをstringに戻せないこと。どうしたもんかなぁ。
…まだ、「C#と同じぐらいデキル」という境地には至れてません。
この辺の未解決変換についてご存知の方いましたら教えてください。
スポンサードリンク