2020年3月24日
まえがき
特に言うことはない
今日解いた問題
ABC097 C- K-th Substring
[部分文字列,substr,連想配列,文字列,辞書順]
辞書順でK番目であるということについての考察。
"abcdef"と言う文字列sがあったとき、その末尾(プレフィックス)を取ったもの"abcde"文字列tは、sよりも辞書順で前か後か。どっちでしょうか。
答えは、t < s です。プレフィックスを取った文字列は、取る前の文字列よりも辞書順で前です。
これは今回の文字列だけの話ではない。
s = "nekochan", t = "nekocha"を考えてみても、プレフィックスを取った文字列(すなわちt)は、sよりも前になります。
何が言いたいかと言うと、部分文字列のK番目を求めるとき、K+1文字の文字列はどんな文字列であれ辞書順でK番目以内に入ることはありません
よって、K文字以内のsubstringを考えれば良い。
(ま、解説からの知識なんだけどね)
文字列を作ってソートをするのがめんどくさかったので、連想配列に入れていきました。
int main() { string s; cin >> s; int k; cin >> k; map<string,int> my_m; int n = s.size(); string t; rep(i,n){ // for(int i = 0; i < n; i++) For(j,1,k+1){ // for(int j = 1; j < k + 1; j++) // i 文字目から j 文字を取る if (i + j > s.size()) continue; t = s.substr(i,j); my_m[t] += 1; } } int count = 1; for(auto x:my_m){ if (count == k){ cout << x.first << endl; return 0; } count ++ ; } }
substrの挙動
cppreference substr
日本語のsubstr説明
substrって文字列のサイズを超えたところから取ろうとしたらどうなるんだろう。っていうのを手元でだけ確認してたら、フォロワーさんに仕様書を読みなさ〜いって怒られちゃいました。(怒られてはないけど)
文字列sに対してpos番目の要素からcount文字を取ったsubstringを作ろうとしたとき、pos >= s.size() の場合は
std::out_of_rangeというエラーメッセージが吐かれるようです。
また、pos + count >= s.size()のときはエラーは吐かれずに、[pos,s.size())が返されるようです。
ABC045 C- たくさんの数式
[bit全探索]
みんな大好きbit全探索の問題です。
|S|個の数字がある時|S| - 1箇所のどこに + を入れるかで2|S|-1通りを全部やってあげようという問題です。この問題を解けたことで僕はbit全探索に少し自信がつきました。
少し思い出を語ると、10月ぐらいにこの問題挑戦しようとして死んだんですよね。
ll ans = 0; for int(tmp = 0; tmp <(1 << s.size() - 1); tmp++) { bitset<10> bit(tmp); // bitset<k> の k に変数は使えない ll ret = 0; // bit が立っているところまでの文字列を作る string t = ""; rep(i,s.size()) { t += s[i]; if(bit.test(i)||i == s.size() - 1) { if(t != "")ret += stoll(t); t = ""; } } ans += ret; }
動かしてないからもしかしたらバグッてるかも。
おまけ stoiについて
stoiについてもリファレンスしらべてみました。 stoiの日本語reference どうやらstoi("fads")とかすると std::invalid_argumentっていうエラーが吐かれるようです。 また、int型に収まらない数値に変換しようとした場合は std::out_of_rangeが図れるんだって。
ABC129 D-Lamp
[最大化,数え上げ的な]
まずはこちらの画像をご覧ください。
ブログ用 pic.twitter.com/yin8MbGQ5z
— 瑞々しぃにぼし@バナナのナナチはバナナナチ (@niboshi_wakai) 2020年3月24日
一次元でみたとき障害物と障害物の間ならどこに置いても行や列の照らす個数は変わりません。このことを利用して、そのマスにおいたときに照らす個数を調べるのを楽にすることが出来ます。
具体的には、左や上のマスを見れば、行、列で何個照らすかをO(1)で(多分)参照することができる。
diverta 2019 Programming Contest D- DivRem Number
[整数,約数,商と余り]
何か解けちゃいました。
13で割ると商と余りが等しくなる100以上の整数
このyahooエッチ袋を参照したら解けました.
この問題では13がMに対応しています。つまり、8× 14 , 9 × 14 , ... , 12 × 14 は13をお気に入りの数に持っている。
そんな感じでコネコネしてやると、Nの約数とお気に入りの数が密接な関係を持っていることに気が付きました。 計算量にそこまで影響しないので約数-1がお気に入りの数かどうかを調べてそうなのであれば答えに+するって感じでAC出来ました。バンザイ
あとがき
読書…しゅき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - あいさつ - 久々にブログを更新したときの記事