解説のおまけ問題にもあるが，100 x N程度の計算量で解くようなコードを生成できた…と思う。

$\displaystyle{S}$ が仮に $\displaystyle{ 1067381902499 }$ というような数列だった場合，暗証番号の一桁目を全探索していくときに，2回目の $\displaystyle{ 1 }$ については見る必要がない。なぜなら，一回目の $\displaystyle{1}$ を一桁目とすると，暗証番号の二，三桁目の候補となるのは $\displaystyle{ 067381902499 }$ だが，二回目の $\displaystyle{1}$ を一桁目とすると，候補は $\displaystyle{ 902499 }$ となり，明らかに一回目の全探索は二回目の全探索を含むからである。すなわち，一桁目の全探索時に $\displaystyle{0}$ から $\displaystyle{9}$ までのbool型配列を作っておき，探索したことがある数字についてはフラグを立てて次は読み飛ばせば良い。この方針に従ってコードを書くと次のようになる：

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<bool> firstdigit(10, false);
    vector<bool> seconddigit(10, false);
    vector<bool> thirddigit(10, false);
    vector<int> int_s(n);
    int counter = 0;
    rep(i, n) {
        int_s.at(i) = (int)s.at(i) - (int)'0';
    }

    rep(i, n - 2) {
        if (firstdigit.at(int_s.at(i)) == false) {
            firstdigit.at(int_s.at(i)) = true;
            rep(j, 10) {
                seconddigit.at(j) = false;
            }
            for(int j = i+1; j < n - 1; j++) {
                if (seconddigit.at(int_s.at(j)) == false) {
                    seconddigit.at(int_s.at(j)) = true;
                    rep(k, 10) {
                        thirddigit.at(k) = false;
                    }
                    for(int k = j+1; k < n; k++) {
                        if (thirddigit.at(int_s.at(k)) == false) {
                            thirddigit.at(int_s.at(k)) = true;
                            counter++;
                        }
                    }
                }
            }
        }
    }

    cout << counter << endl;
}

3 x Nについてはわからんかった。

2021-04-27

桁数を数えるときに気をつけること

例えば $\displaystyle{ 1 \leq i \leq 1000 }$ の桁数をループを回しながら数えていくとき(かぞえた桁数は配列digitsにしまうものとする)。

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;

int main() {
    vector<int> digits(1000);
    ostringstream oss;
    string s;
    for (int i = 1; i <= 1000; i++) {
        oss.str(""); //初期化する！
        oss << i;
        s = oss.str();
        digits.at(i - 1) = s.size();
    }

    cout << digits.at(9);
}

ソースコード中にも書いたが，使ったostringstreamはループのたびに初期化する必要があることに注意。もちろん，桁数を数える関数を作っても良い。というか，こっちのほうが2, 3倍早かったっぽい：

int digit(int x) {
    int counter = 0;
    while (x != 0) {
        counter++;
        x /= 10;
    }
    return counter;
}

問題文によって2つは見極めて使っていこうと思う。

2021-04-25

AtCoder Beginner Contest 199

昨日受けたので復習。

問題A, B

A - Square Inequality

B - Intersection

についてはすぐ実装が終わった。AOJのITP1をすべてこなしたおかげで力がついたかもしれない。せっかくなのでB問題に使ったmax_elementとmin_elementの使い方を復習しておく。

vector<int> x(100) = {/* hoge */};
cout << *max_element(x.begin(), x.end());  // 返り値がiteratorなので*を忘れずに！
cout << *min_element(x.begin(), x.end());  // 同様

問題C

C - IPFL

について。問題通り素直に実装したがTLE。入力関係の遅さを疑い，cinをscanfにするが，手間取った上にMLEまでつく。cinに戻す。例えばすべてのクエリが $\displaystyle{ T = 2 }$ で， $\displaystyle{ N = 2 \times 10^ 5, Q = 3 \times 10^ 5 }$ のとき，このようなコードだと間に合わないらしい:

case 2:
    string tmp1 = s.substr(0, n);
    string tmp2 = s.substr(n, n);
    s = tmp2 + tmp1;
    break;

substr関数が $\displaystyle{O(n)}$ なのだそう。結局flagを作って(そのときはint型にしたが多分bool型にしておいたほうが良かったな…)T=2のときflagを反転させ，T=1のときにflagによって処理を変える方針がいいっぽい。最終的に提出したコード:

Submission #22026711 - AtCoder Beginner Contest 199（Sponsored by Panasonic）

最後に何を思ったかswapを使わないほうが早いのかな？とか考えてswapを使わなかったが，絶対使ったほうがいいに決まってる。

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;


int main() {
    string A = "cat";
    string B = "dog";
    clock_t start = clock();
    rep(i, 1000000) {
        swap(A, B);
    }
    clock_t end = clock();

    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;

    string tmp;
    start = clock();
    rep(i, 1000000) {
        tmp = A;
        A = B;
        B = tmp;
    }
    end = clock();

    cout << (double)(end - start) / CLOCKS_PER_SEC << endl;
}

結果:

1.013s //swap
1.432s //自作swap

今度からはSTLを疑わず使います…あと前半と後半の文字列を分割して保存しておくやり方は頭いいなあと思った。

問題D

D - RGB Coloring 2

わかんなかった。この問題青diffらしいので，別の基礎的な問題をやってからまたこっちに戻ってこようと思う。

2021-04-25

accumulateの第三引数に注意(及び数値の型指定)

vector<long long>型やvector<double>型の配列 x の総和を求めるときに，

std::accumulate(x.begin(), x.end(), 0);

とすると誤差がおおきくなったり，オーバーフローしたりする。std::accumulateの仕様として第三引数の型で値が帰ってくるらしい。なので正しくはそれぞれ

std::accumulate(x.begin(), x.end(), 0LL);
std::accumulate(x.begin(), x.end(), 0.0);

とする。一応数値の型指定のまとめしておく:

0          //int
0LL        //int64_t
0.0        //double
0.0f       //float

(2020/04/24 19:55 誤りがあったので修正しました。)

(メモ) std::cout よりも printf のほうが便利で早いこともあるっぽい，桁数固定など

2018-03-25

はてなブログで、プラットフォームやブラウザごとにMathjaxの表示方法を変える

備忘録

タイトルの通り。

僕のAndroid端末のChromeの環境だけなのかもしれないが、MathjaxのRendererがHTML-CSSでは表示がずれてしまい、数式と文章と覆い被さってしまう。だから、端末やブラウザごとにMathjaxのRendererを変更することにした。

まず、はてなブログの設定画面にいく。
「詳細設定」＞「headに要素を追加」に、以下のコードを入力する。

<script type="text/javascript">
     var ua = navigator.userAgent;  
     if( ua.indexOf("Android") > 0 )   
         var androidversion =      parseFloat(ua.slice(ua.indexOf("Android")+8));
</script>

<script type="text/x-mathjax-config">
MathJax.Hub.Register.StartupHook("End Jax",function () {
  var BROWSER = MathJax.Hub.Browser;
  var jax = "CommonHTML";
  if (BROWSER.isMSIE && BROWSER.hasMathPlayer) jax = "NativeMML";
  if (BROWSER.isMSIE && !BROWSER.versionAtLeast("9.0")) jax = "HTML-CSS";
  if (BROWSER.isSafari && !BROWSER.versionAtLeast("6.0")) jax = "HTML-CSS";
  if (androidversion < 3.0) jax = "HTML-CSS";
  if (androidversion >= 3.0) jax = "SVG";
  return MathJax.Hub.setRenderer(jax);
});
</script>

参考にさせていただいたサイトは以下の三つ。

(1)MathJax Output Formats — MathJax 2.7 documentation
(2)www.kaasan.info
(3)d.hatena.ne.jp

簡単に言えば、

最新のIEではnativeMML
古いIEやSafariではHTML-CSS
古いAndroidではHTML-CSS
普通のAndroidではSVG
それ以外ではCommonHTML

をそれぞれRendererとした。

また、よっぽど昔のブラウザーを使っているか、DSやPSPを使っている人のことは流石に考えていない。
しかし、ウェブフォントを無効にしている人は案外多いそう。（2012年の記事では有るが）
tech.nitoyon.com
これに関して、なんとかウェブフォント無効を検出できないかなあと検索してみたが、良いサイトは見当たらなかった。（もし検出の仕方をご存知の方がいらっしゃったら教えて下さい）

というわけで、若干妥協せざるを得なかったが、当面はこれで行こうと思う。
（もし数式の表示がおかしい場合は環境と共にその旨をご一報いただけるとありがたいです）

テスト数式： $\displaystyle e^{i \pi}+1=0$