Arc's blog

プログラミングとかの研究室

PandocとMarkdownで快適執筆環境を作る

文書を書く際、MS Wordで体裁を整えて提出 or .docxを直接提出する事が多いと思います。しかし実際に書いてみると、

  • Wordが重い
  • 直接書くと体裁が崩れがち
  • 白背景嫌い

などの問題が発生しました。そこで、Markdownで執筆して.docx形式にエクスポートする環境を整えました。それに関してのメモです。

この手の話は既出ネタなので、他の方の記事も読んでみてください。

Markdownって何?

本来はHTML文書を簡単に作るために開発された言語です。Markdown単体で読んでもそこそこ読みやすく、また書きやすいです。この機会に覚えてみるのもいいと思います。

詳しくはMarkdown - Wikipediaなどを参照。

使用するソフトウェア

Pandoc

Pandoc - About pandoc

Markdown→.docxに限らず、(色々な入力形式)→(色々な出力形式)への変換を実現するソフトウェア(雑)。

Bear(などのMarkdownエディタ)

軽くて目の疲れない物を選びましょう。

ソフト自体の説明は別記事におまかせします。Pandocについては多様なフォーマットに対応!ドキュメント変換ツールPandocを知ろう - Qiitaを読めば分かります(記事とても良かったです。ありがとうございました)。

MS Word

レイアウト確認用。

環境構築

ソフトをインストールする

環境と好みに合わせてどうぞ。MarkdownエディタにはBearやVSCodeなどがあります。

Pandocの出力スタイルを作る

PandocがMarkdownを.docxに変換するときに使うスタイルを設定します。

ドキュメント変換ツールPandoc:ユーザーズガイドを熟読して分かったマニアックな使い方 - Qiitaの「ODT/docxの参照用スタイルファイル」項を参照。

ここで指定したファイルのスタイルが変換時に使用されます。

Wordの「スタイル」について

フォント、フォントサイズ、文字色などの設定をまとめたものが「スタイル」です。文書中で同じスタイルを使った文字は全て同じ書式設定になります(それはそう)。

Markdownファイルが

# 見出しA
## 見出しA-a
本文a
# 見出しB
## 見出しB-b
本文b

のようになっていた場合、「見出しA&見出しB」「見出しA-a&見出しB-b」「本文a&本文b」にそれぞれ同じスタイルが適用されます。文の書式を直接いじるのではなく、スタイルをいじることで、書式の揃った見やすい文書を作ることができます。

一番最初に書いた「体裁が崩れがち」な原因の多くは「スタイルを使いこなせていない」のが原因なのかな、と勝手に想像しています(ぼくもあまりわかってない)。一度設定してPandocに任せれば、スタイル設定を自動でやってくれます。

Markdownで書く

軽量エディタはいいぞ。黒背景はいいぞ。

.docxに変換する

Terminal/コマンドプロンプトを開き、Markdownファイルのあるディレクトリ上で

pandoc -f markdown -t docx -o (出力ファイル名) (入力ファイル名)

を実行します。詳しいコマンドはPandoc ユーザーズガイド 日本語版 - Japanese Pandoc User’s Associationを参照。

このコマンドは”From markdown To docx”みたいな意味になります。

出来上がったもの

完成直前のこの記事をPandocで変換してPDF化したものがこちらになります。

まとめ

Word直書きに戻れる気がしません。

他にも色々な活用方法があります。Pandocを使いこなしていきましょう。おわり。

Google Code Jam 2019 Qualification Round に参加したよ

GCJ予選に参加してきました。AB満点で41点でした。予選通過です。

GCJ予選のルール

  • 全4問。
  • それぞれの問題はいくつかの小課題に分かれている。
  • それぞれの小課題には「点数」「Visible か Hidden か」が決まっている。
    • Visible: 採点結果がコンテスト中に通知される
    • Hidden: 採点結果はコンテスト中に通知されない
  • 100点中30点をとれば予選通過。
  • コンテストは27時間開催される。

問題

ネタバレ防止のため、最初に全ての問題文を載せてからAとBの解法を載せます。

A - Foregone Solution

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

1つ以上の桁に4を含む自然数Nが与えられる(例: N=4, 434, 4444)。どの桁にも4を含まない自然数の組(A, B)の中で、N==A+Bを満たす物の1つを答えよ。

サンプル

  • N=4のとき、(A, B)=(1, 3)
  • N=434のとき、(A, B)=(232, 202)

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 10 sec
  • メモリ制限: 1 GB

Test set 1 (Visible, 6 pts)

  • 1<N<10^5

Test set 2 (Visible, 10 pts)

  • 1<N<10^9

Test set 3 (Hidden, 1 pt)

  • 1<N<10^100

B - You Can Go Your Own Way

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

南北方向Nマス、東西方向Nマスで構成された平面がある。

はじめに、Lydiaが南への移動と東への移動を繰り返して、北西の角のマスから南東の角のマスまで動いた。あなたは、Lydiaの移動方法と1度も重ならないようにして、同じように南への移動と東への移動を繰り返し、北西の角のマスから南東の角のマスまで動きたい。具体的には、

Lydiaの移動ルートに「マスAから隣接するマスBへの移動」が含まれるとき、あなたは「マスAから隣接するマスBへの移動」をすることはできない。しかし、あなたは「マスAから隣接するマスCへの移動」をすることはできる。

平面のサイズN、Lydiaの移動ルートを表す文字列P(南への移動はS、東への移動はEで表される)が与えられるので、あなたの移動ルートを表す文字列yを1つ答えよ。

サンプル

GCJ公式の図を参照(Lydiaは青、あなたのルートはオレンジです)。

このとき、N=5, L=“EESSSESE”, y=“SEEESSES”である。

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 15 sec
  • メモリ制限: 1 GB
  • Lydiaが北西の角のマスから南東の角のマスまで動くことは保証される。すなわち、Pには文字SN-1個、文字EN-1個含まれる。

Test set 1 (Visible, 5 pts)

  • 2<=N<=10

Test set 2 (Visible, 9 pts)

  • 2<=N<=1000

Test set 3 (Hidden, 10 pts)

  • 最大10個のテストケースで 2<=N<=50000
  • それ以外のテストケースで2<=N<=10000

C - Cryptopangrams

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

pangramと呼ばれる、26種のアルファベット全てを少なくとも1回用いて作られた特殊な文字列がある(例: “the quick brown fox jumps over the lazy dog”)。あるpangramを、以下の手順で数列として暗号化した。

  1. Nを決める。
  2. N以下の素数を26個決める。
  3. 26個の素数を昇順にソートする。
  4. 最小の素数A、次の素数B、...最大の素数Zを割り当てる。
  5. pangramを用意し、文字を全て大文字にして、空白を削除する。これを平文とする。
  6. 手順4で構成した文字と素数の対応に従って、平文を数列に変換する。便宜上、この数列をp[]とする。
  7. 暗号数列c[]を、c[i]=p[i]*p[i+1]を満たすようにして構築する。
  8. c[]が暗号化されたpangramの数列である。要素の個数はLである。

N, Lと、L個の暗号数列の要素が与えられるので、暗号数列を復号し、もとのpangramを出力せよ。

サンプル

例としてGCJを暗号化する(注: この文字列はpangramではない)。

'C'→5, 'G'→17, 'J'→29 と対応している場合、

p[0]==17, p[1]==5, p[2]==29

であり、

c[0]==17*5==85, c[1]==5*29==145

である。

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 20 sec
  • メモリ制限: 1 GB
  • 25<=L<=100
  • 復号するとpangramになることが保証されている

Test set 1 (Visible, 10 pts)

  • 101<=N<=10000

Test set 2 (Hidden, 15 pts)

  • 101<=N<=10^100

D - Dat Bae

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

これはインタラクティブ問題である。

ID 0,ID 1,...ID N-1 を与えられたコンピュータがN台ある。これらのコンピュータにN桁のビット列を与えると、戻り値として、与えたビット列と同じN桁のビット列が返ってくる。

しかし、B台のコンピュータが壊れてしまったため、戻り値がN-B桁しか返ってこない。この戻り値は、与えられたビット列から、壊れたコンピュータのIDに対応する桁を削除したものである。具体的には、

N=5, B=2, ID 0とID 3 のコンピュータが壊れているとき、

  • 01101を与えると111が返ってくる
  • 00110を与えると010が返ってくる
  • 01010を与えると100が返ってくる
  • 11010を与えると100が返ってくる

あなたは、コンピュータに対してN桁のビット列を最大F回送信することにより、どのコンピュータが壊れているかを調べたい。

はじめに、整数N, B, Fが与えられる。その後、あなたは、コンピュータに対して、次のクエリを最大F回送ることができる。

  • N桁のビット列を送信する。不正な入力である場合は-1が与えられる。そうでなければ、N-B桁のビット列で構成された戻り値が与えられる。

また、どのコンピュータが壊れているかわかった場合、次のクエリを1回だけ送ることができる。

  • 壊れているコンピュータのIDを、空白区切りでB個送信する。間違っている場合は-1が与えられる。正解している場合は1が与えられ、次のテストケースのジャッジが始まる(もしくはACになる)。

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 20 sec
  • メモリ制限: 1 GB
  • 2<=N<=1024
  • 1<=B<=min(15, N-1)

Test set 1 (Visible, 14 pts)

  • F==10

Test set 2 (Hidden, 20 pts)

  • F==5

解法

A - Foregone Solution

Test set 1

方針

O(N)が間に合うので、A=i, B=N-iとして全探索すればよい。

数nを1桁ごとにstd::vectorの要素として追加するライブラリがあれば、4が使われているかの判定はすぐにできる。なかったら作る。

AtCoder基準の体感難易度

ライブラリがあれば200点

Test set 2

例としてN=434を考える。 各桁に4または0以外の数が出現しない自然数Sと、各桁に4が出現しない自然数Tのうち、N==S+Tを満たすような組を求める(この場合、S=404, T=30。この組はNを一桁ずつ確認することで求められる)。 そして、A=S/2+T, B=S/2にすれば良い。なぜならば、

  1. 明らかにA+B==Nである
  2. Bの各桁は2か0のいずれかである
  3. S/2の各桁は2か0のいずれかであり、Tを足したときに桁の繰り上がりは発生しない

からである。

これによりO(Nの桁数)で求められる。

AtCoder基準の体感難易度

300点上位〜400点下位

Test set 3

Test set 2 の操作は、N,A,Bを文字列として考えたときに、

  • N中のそれぞれの文字cに対して
    • c=='4'ならA+='2' , B+='2'
    • c!='4'ならA+=c , B+='0'
  • Bの最初の方で連続している無駄な0を削除する

という操作をすることと等しい。

文字列化することでオーバーフローの心配がなくなった。

AtCoder基準の体感難易度

300点上位〜400点下位 実装はset 2 よりも楽

B - You Can Go Your Own Way

Test set 1, 2

略。3を解きに行ったほうがわかりやすいので

Test set 3

方針

Lydiaが南に動いたら自分は東に、Lydiaが東に動いたら自分は南に動けば良い。

こうすることで二人の移動ルートが「北西の角と南東の角を結んだ対角線に対して対称」になる。ルートが直交することはあっても重なることはないのでAC。O(N)

AtCoder基準の体感難易度

300点。体感ではAより楽

C - Cryptopangrams

解けてないです ごめんなさい

Test set 1 は素数列挙してゴリ押し因数分解するだけなはずなんだけどなぁ…

D - Dat Bae

あまり考えてないです ごめんなさい

二分探索をうまく使えば解けそうな気がしました

その他雑記

  • 問題閲覧画面ですが、ブラウザ内エディタが強制的に問題文の横に出現する仕様でした。正直いらないです。
  • スマホコーディングはつらいです。
  • GCJ Round 1もがんばります。

AtCoder Beginner Contest (ABC) 106 を解いてみた

AtCoder Beginner Contest (ABC) 106 の解法ログです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - Garden

解法

算数の問題にこういうのありましたね。道の重なりに注意。

ソースコード

int main(void) {
    int a, b;
    cin >> a >> b;
    cout << a * b - a - b + 1 << endl;

    return 0;
}

B - 105

解法

Nが小さいので、N以下の数で割ったあまりを全て見ていけばOK。

余り0になる場合が8つあるなら、その数は約数を8個持つ。

ソースコード

int main(void) {
    int n;
    cin >> n;
    int result = 0;
    for (int i = 1; i <= n; i += 2) {
        int count = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0)
                count++;
        }
        if (count == 8)
            result++;
    }

    cout << result << endl;

    return 0;
}

C - To Infinity

解法

1<=n<=K文字目に1以外の文字が存在する場合、5000兆日経つと、たとえK=10^18でも1以外の文字がKの場所に到達する(指数関数は一瞬で膨れ上がるので)。

そうでない場合は5000兆日経ってもK文字目は1のまま。

K文字目まで1が続くのなら1を、そうでないなら最初に出現した1以外の文字を出力する。

ソースコード

int main(void) {
    std::string s;
    int64_t k;
    cin >> s;
    cin >> k;
    for (int i = 0; i < k; i++) {
        if (s[i] != '1') {
            cout << s[i] << endl;
            return 0;
        }
    }
    cout << '1' << endl;

    return 0;
}

D - AtCoder Express 2

解法

愚直に解く場合、『クエリ(p,q)に対して、「全列車に対しp<=L,R<=qであるかを調べる」』という解法を思いつける。計算量はO(Q*M)なので間に合わない。

都市の数が少ないことに着目すると、train[L][R]=LからRに向かう電車の数という配列を作ることができそう。この配列を利用して「p<=L,R<=qを満たす場所を足していく」という解法を思いつける。計算量はO(QN^2)。……計算量増えてるじゃーん!!

しかし、「p<=L,R<=qを満たす場所を足していく」処理は累積和を利用することでO(N)に落とせる。ということで、先程の配列から累積和を作ってクエリに答えればAC。

ソースコード

(printf/scanfで書いてます)

int main(void) {

    int n, m, q;
    cin >> n >> m >> q;
    int train[501][501] = {};
    int cum[501][501]   = {};

    int m1, m2;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &m1, &m2);
        train[m1][m2]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cum[i][j] = cum[i][j - 1] + train[i][j];
        }
    }

    int a, b;
    int answer;
    for (int i = 0; i < q; i++) {
        answer = 0;
        scanf("%d%d", &a, &b);
        for (int j = a; j <= b; j++) {
            answer += cum[j][b];
        }
        printf("%d\n", answer);
    }

    return 0;
}

その他

37分全完やったぜ。

AtCoder Beginner Contest (ABC) 105を解いてみた

AtCoder Beginner Contest (ABC) 105の解法をまとめてみます。今回はD問題が詳しめです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - AtCoder Crackers

解法

なるべく公平に配るなら、

  • N%K==0のとき 差は0
  • N%K!=0のとき 差は1

になる。

ソースコード

int main(void) {
    int n,k;
    cin>>n>>k;
    if(n%k==0){
        cout<<"0"<<endl;
    }else{
        cout<<"1"<<endl;
    }
 
    return 0;
}

B - Cakes and Donuts

解法

7ドルのドーナツを買う→残額が4で割り切れるならtrue、割り切れないならドーナツをもう一つ→……というふうにやっていく。

一応4ドルのケーキを買った後で判定する処理も書いたけど無駄だった。

ところでArcとかいう人はこの問題で2WAも出しているそうですよ。酷いですね。

ソースコード

int main(void) {
    int n;
    cin >> n;
    bool can_buy = false;
    if (n % 7 == 0 || n % 4 == 0) {
        can_buy = true;
    } else {
        for (int i = 0; i <= n; i += 7) {
            if ((n - i) % 4 == 0) {
                can_buy = true;
                break;
            }
        }
        for (int i = 0; i <= n; i += 4) {
            if ((n - i) % 7 == 0) {
                can_buy = true;
                break;
            }
        }
    }
 
    if (can_buy)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
 
    return 0;
}

C - Base -2 Number

解法

10進数nを普通の2進数に変換する際の処理を考えてみると、

nが0になるまで{

(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
2進数a桁目にフラグを立てる
n-=2^(a-1)

}を繰り返す

と言う風になる。これを応用して、

nが0になるまで{

n<(a-1ビットで表現できる最小の数)か(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
-2進数a桁目にフラグを立てる
n-=(-2)^(a-1)

}を繰り返す

という処理を作ってみる。

ソースコード

const long long MAX_N = 1000000000;
const long long MIN_N = -1000000000;
 
int main(void) {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    bool is_on[101] = {};
    std::vector<long long> max;
    std::vector<long long> min;
 
    // max,minを計算
    //max[a]=(aBitで表現できる最大値)
    max.push_back(0);
    min.push_back(0);
    long long add = 1;
    int count     = 0;
    while (1) {
        count++;
        if (count % 2 == 1) {
            max.push_back(max[count - 1] + add);
            min.push_back(min[count - 1]);
        } else {
            max.push_back(max[count - 1]);
            min.push_back(min[count - 1] + add);
        }
        if (max[count] >= MAX_N && min[count] <= MIN_N)
            break;
        add *= -2;
    }
 
    int top_digit = 0;
    while (n != 0) {
        if (n > 0) {
            int digit = 1;
            while (max[digit] < n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        } else {
            int digit = 1;
            while (min[digit] > n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        }
    }
 
 
    for (int i = top_digit; i >= 1; i--) {
        if (is_on[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << endl;
 
    return 0;
}

D - Candy Distribution

解法

累積和を計算した後、累積和のそれぞれの項に対してMで割った余りを計算。 Mで割った余りがiであるような項がn個あるなら、それらの項から2つを選択すると条件を満たす和が得られる。個数はn C 2。これをそれぞれのiに対して計算することで答えが得られる。

実装

実装がきつかったので詳しめに書いてみる。

「余りがiであるような項の個数」をどう保持するか?

余りのパターンはM通り存在するから、配列を用意するとメモリが足りない。

公式PDFにもある通り、std::map系のコンテナを利用することになる。今回の実装はstd::multimapを利用している。キーを余り、値を累積和の項にして、count(i)で個数を取得する作戦。なおmap系を利用するのは今回が初めてな模様。

イテレータを最初から最後まで回して、前に見たキーと別のキーが出現したら計算用関数を呼び出す事にした(キーが順番通りに出現する必要があるのでunordered_multimapは使えない)。

unorderedの実装ってどうやるんでしょうね……。

組み合わせの数n C 2をどう計算するか?

ソースコードコメントアウトした関数のように、階乗を利用して計算するとlong longでもオーバーフローしてREを吐く。階乗をなめたらいけない。

結局「n!を少しずつ計算→途中で(n-2)!か2!の因数で約分できそうだったら約分」というクッッッッソ醜いやり方で押し通した。

……と、ここまで書いたが実は全て罠n C 2なら普通に(n-1)+(n-2)+...+2+1を計算するだけで済む。

これに気づいたのはACした後の話でしたとさ。

コンパイラによって異なる言語実装

GCC5.4.1、ローカル環境のClang(clang-902.0.39.2)だと、ローカル変数宣言時に自動で0初期化が行われる。

Clang 3.8.0だと初期化が行われないらしく、結果「ClangでコンパイルするとWAになる」という現象が発生していた。

とりあえず明示的にint hoge=0としておいた方が精神衛生上よろしいかも。

ソースコード

/*
long long factorial(long long n) {
    long long result = 1;
    for (long long i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
 
long long combination(long long n, long long r) {
    long long result = factorial(n) / factorial(n - r) / factorial(r);
    return result;
}
*/
 
long long combination_improved(long long n, long long r) {
    long long d      = n - r;
    long long result = 1;
    while (n > 1 || d > 1 || r > 1) {
        if (n > 1) {
            result *= n;
            n--;
        }
        if (d > 1 && result % d == 0) {
            result /= d;
            d--;
        }
        if (r > 1 && result % r == 0) {
            result /= r;
            r--;
        }
    }
    return result;
}
 
int main(void) {
    long long n, m;
    long long count;//Clangだと初期化の必要あり
    long long cum[100001];
    std::multimap<long long, long long> mod_map; //(mod M,number)
    cin >> n >> m;
    long long m1;
    for (int i = 0; i < n; i++) {
        cin >> m1;
        if (i == 0)
            cum[i] = m1;
        else
            cum[i] = cum[i - 1] + m1;
    }
    for (int i = 0; i < n; i++) {
        mod_map.insert(std::make_pair(cum[i] % m, cum[i]));
    }
 
    int prev = m;
    for (auto itr : mod_map) {
        if (prev != itr.first) {
            if (itr.first == 0) {
                if (mod_map.count(0) >= 1)
                    count += combination_improved(mod_map.count(0) + 1, 2);
            } else {
                if (mod_map.count(itr.first) >= 2) {
                    count += combination_improved(mod_map.count(itr.first), 2);
                }
            }
        }
        prev = itr.first;
    }
 
    cout << count << endl;
 
    return 0;
}

おまけ

散っていったコードに敬意を。(?????)

Mujin Programming Challenge 2018 を解いてみた

無人コン(参加者800人以上)の解法メモです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの文字と解法中の文字は無関係です

A - コンテスト名

文字列MUJINSを比較するだけ。

ソースコード

int main(void) {
    std::string s;
    std::string ans;
    cin >> s;
    ans = "MUJIN";
    for (int i = 0; i < 5; i++) {
        if (ans[i] != s[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

B - セキュリティ

一文字ずつ読んでシミュレート、0になったらYesを返して即return 0

一番最初に0人だった(A==0)場合もYesになることに注意。

ソースコード

int main(void) {
    cout << std::fixed << std::setprecision(10);
    int a;
    cin >> a;
    std::string s;
    cin >> s;

    if (a == 0) {
        cout << "Yes" << endl;
        return 0;
    }

    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '+') {
            a++;
        } else {
            a--;
        }
        if (a == 0) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

C - 右折

解けてないです><

あるマスで右折するルートの総数は、

左、上、右、下に(そのマスを除いて).がa,b,c,d個並んでいた場合a*d+b*a+c*b+d*c=(a+c)*(b+d)で求められる

このことを利用していけばO(NM)で解けるはずです(通らないよぅ……)。

D - うほょじご

解法

準備

数の組に対して、

enum status { ns = 0, wj, wa, ac };
//ns(No Submission)は未確認
//wj(Waiting for Judging)は確認中
//wa(Wrong Answer)は無限回操作ができないと確定
//ac(Accepted)は無限回操作ができると確定

を定義する。

status grid[x][y]=(x,y)のstatusとしておく。

初期状態では(0,n)(n,0)(nは任意の整数)のみwa、その他はns

探索

あるnsの数の組(x,y)に対して、とりあえず一回操作をしてみる。

操作後の数の組(a,b)の状態によって、以下のことを行う。

grid[a][b]==nsの場合

grid[a][b]=wjとして、さらにstd::vector<std::pair<int, int>> vecに数の組をpush_back()しておく(後で役に立つ)。 vecは「探索中に通過したwjの状態の記録」として考えてください。

その後、(a,b)をもう一度操作。

grid[a][b]==waの場合

waになっている組になったら、その数の組が向かう先は(0,n)(n,0)しかない。

探索中に通った数の組についても同じことが言える。

vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=waにする。(vecに保存しないでgrid[][]を全探索すると時間が掛かるが、vecに保存すると計算量を落とせる)

grid[a][b]==ac、grid[a][b]==wjの場合

探索中にwjにたどり着いた場合、以降は無限回操作ができる。

また、無限回操作ができると確定した状態にたどり着いた場合、無限回操作ができる(それはそう)。

探索中に通った数の組は無限回操作が可能、と言えるので、vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=acにする。

仕上げ

あとはgrid[x][y]==acになっている場所を数えて終了。

ソースコード

void dp_search()となっていますが、DPと言えるかは人それぞれだと思います。

enum status { ns = 0, wj, wa, ac };

int n, m;
status grid[1000][1000];

int rev(int x) {
    int a, b, c;
    int reverse;
    if (x >= 100) {
        a = x / 100;
        x -= a * 100;
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 100 + b * 10 + a;
    } else if (x <= 9) {
        reverse = x;
    } else {
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 10 + b;
    }
    return reverse;
}

void dp_search(int x, int y, std::vector<std::pair<int, int>> vec) {
    if (grid[x][y] == wa) {
        //終了措置
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = wa;
        }

    } else if (grid[x][y] == ac || grid[x][y] == wj) {
        //成功措置
        grid[x][y] = ac;
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = ac;
        }
        return;
    } else {
        grid[x][y] = wj;
        if (x < y)
            x = rev(x);
        else
            y = rev(y);
        if (x < y)
            y -= x;
        else
            x -= y;
        vec.push_back(std::make_pair(x, y));
        dp_search(x, y, vec);
        return;
    }
}

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin >> n >> m;

    for (int i = 0; i <= 999; i++) {
        for (int j = 0; j <= 999; j++) {
            grid[i][j] = ns;
        }
    }
    for (int i = 0; i <= 999; i++) {
        grid[0][i] = wa;
        grid[i][0] = wa;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ns) {
                std::vector<std::pair<int, int>> vec;
                vec.push_back(std::make_pair(i, j));
                dp_search(i, j, vec);
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ac) {
                answer++;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

これ以降

やってません

まとめ

時間内では2完でした。

腕、落ちてないか?? 青になれるのか???

ABC072/ARC082を解いたので記録を残す

だいぶ昔のやつですが、ABC072/ARC082のA~D問題を解いたので記録を残します。

問題文はAtCoder公式からどうぞ。

A - Sandglass2

ans=x-tをして、ans>=0だったらそのまま出力。それ以外だったら0を出力。

int main(void)
{
    int x, t;
    cin >> x >> t;
    int answer = x - t > 0 ? x - t : 0;
    cout << answer << endl;
 
    return 0;
}

B - OddString

一文字飛ばしで文字を足していく。実装ゲー。

int main(void)
{
    std::string s;
    std::string answer;
    cin >> s;
    for (int i = 1; i <= (int)s.size(); i++)
    {
        if (i % 2 == 1)
        {
            answer += s[i - 1];
        }
    }
    cout << answer << endl;
 
    return 0;
}

C - Together

{\displaystyle a_i}{\displaystyle a_i-1}{\displaystyle a_i}{\displaystyle a_i+1}になれる。

{\displaystyle x}に対して、count[x-1]++; count[x]++; count[x+1]++;をしていった後、どのcount[]が最大の値かを調べればOK。

イメージとしては「長さnの直線上に積み木を3つずつ積んでいく」感じ。一番高く積み上がった場所が答え。

int main(void)
{
    int n;
    int count[100000] = {};
 
    cin >> n;
    int m1;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        count[m1]++;
        if (m1 - 1 >= 0)
            count[m1 - 1]++;
        if (m1 + 1 < 100000)
            count[m1 + 1]++;
    }
 
    int max = 0;
    for (int i = 0; i < 100000; i++)
    {
        if (count[i] > max)
            max = count[i];
    }
 
    cout << max << endl;
 
    return 0;
}

D - Derangement

{\displaystyle p_i\neq i}である所をt,そうでない所をfとする。

ffとなっている所をスワップするとttにできる。

また、ftとなっている所をスワップしてもttにできる(数は1つずつしかないため、スワップ後にtがfになってしまうことはない)。

貪欲的に「fが見つかったら右隣とスワップして、さらに右隣の場所から検索を再開する」という操作をしていけばいい(自分のソースコードだと無駄な処理をしています)。

int main(void)
{
    int n;
    int answer = 0;
    int m1;
    std::vector<int> number;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        number.push_back(m1);
    }
 
    for (int i = 0; i <= n; i++)
    {
        if (number[i] == i + 1)
        {
            if (i + 1 < n && number[i + 1] == i + 2)
            {
                answer++;
                i++;
            }
            else
            {
                answer++;
            }
        }
    }
 
    cout << answer << endl;
 
    return 0;
}

C++&Siv3Dでリアルタイム動画加工ソフト作ったった

Arcです。突然ですが、謎ソフト作ってみました。

機能追加しやすい設計にはしましたが、機能が足りてないです。動作も重いです。クオリティには期待するな。

名付けてRealtimeMovieHacker厨ニっぽい

製作経緯

  • CombNaf3のネタを何か持ってみたかった
  • Siv3Dを使ってみたかった
  • 高校生のうちにプログラミングで何か「形あるモノ」を作ってみたかった

こんな感じですね。

ソフト概要

キーボード操作によって、Webカメラで取得した映像をリアルタイム加工して出力します。

このように動作します。

動作環境はWindows 7 SP1,8,8.1,10です。CPUはできるだけ高性能なものが望ましい。

macOSLinuxには対応していません……が、いつの日か対応するかもしれません(後述)。

ダウンロード

ソフトウェア本体はGithubのReleasesからどうぞ。(無保証です) 一番上が最新版です。"Assets"の下の"RtMovieHacker_vX.Y.Z.zip"をダウンロード、展開してください。

ソースコードGithubで公開しています。

使い方

  1. RtMovieHacker.exeを起動する
  2. Webカメラを起動する
  3. キー操作などで映像にエフェクトを掛ける(詳細は付属のREADME.txt)

実装

ここからは技術的な話。

使ってる言語とかライブラリとか

全てC++14を利用しています。

また、外部ライブラリとしてSiv3Dを利用しています。

Siv3DはWindowsのみ対応。macOS/Linuxに対応するOpenSiv3Dが開発されていますが、現状だと機能が足りなかったので使いませんでした。機能が増えてきたらOpenSiv3Dを利用して移植するかも。

開発はVisual Studio 2015で行いました。

ルーチン

最初に、使用可能なWebカメラを全て起動します。

また、全てのエフェクタクラスをインスタンス化します。

後は以下の処理をずっと回すだけ。

カメラ切り替えキーが押されたらカメラを切り替える(ここの動作は不安定です)
カメラで新しいフレームを取得する
エフェクタ起動条件を満たしていたらエフェクタを起動する
エフェクタ停止条件を満たしていたらエフェクタを停止する
フレームにエフェクトを掛ける
フレームを出力する

エフェクタ管理の実装

std::list<std::reference_wrapper<Effecter>> effecter_disabled(停止しているエフェクタへの参照のリスト)、std::list<std::reference_wrapper<<Effecter>> effecter_enabled(起動しているエフェクタへの参照のリスト)という2つのリンクリストが核になっています。任意位置での削除操作を高速化したいのでstd::listを使用しました。

また、全てのエフェクタは、抽象クラスclass Effecterをpublic継承して実装しています。こうすることで、全てのエフェクタに必須な関数を一元管理できます。

再実装する必要のある関数は以下の通り。

  • virtual bool needs_enable()(起動条件を満たしていたらtrue)
  • virtual bool needs_disable()(停止条件を満たしていたらtrue)
  • virtual void effect()(エフェクトを実行する)

また、全てのエフェクタにはcore_dataという構造体への参照が呼ばれます。core_data.imageを書き換えることで出力フレームが加工されます。

初期化処理として、全てのエフェクタクラスをインスタンス化します。次に、全てのエフェクタクラスへの参照をeffecter_disabledに入れます。

次に、effecter_disabled内の全てのインスタンスに対して、needs_enable()を呼び出します。trueならそのインスタンスeffecter_enabledpush_back()して、effecter_disabled側のインスタンスerase()します。ここの削除操作の時短のためにstd::listを使用しました。ここの処理でつまづきました……。

次に、effecter_enabled内のすべてのインスタンスに対して、needs_disable()を呼び出します。以下、察してください。

で、effecter_enabled内のすべてのインスタンスに対して、effect()を呼び出します。これによってエフェクトが掛かります。

なんか操作が重いのでチューンアップする必要がありそうです(思い当たる節があったので、そのうち更新します)。v0.1.0で修正できました

なんでこんなことをしたのか

こう実装することによって、effecter_enabledの中身が「昔に起動したエフェクタ」を先頭にして並びます。effect()もこの順番に呼び出されるので、あるエフェクトに別のエフェクトを重ねる事ができます。決まった順番で「起動しているか判定→エフェクト掛ける」という方法だと、命令の並び順によってエフェクトを掛ける順番が決まってしまうので……。

エフェクタの作り方

"Effecter.h"にこんな感じで追記。

class <ClassName> :public Effecter{

public:
    <ClassName>(CoreData&);
    bool needs_enable();
    bool needs_disable();
    void effect();
    //その他エフェクタ内で使う関数
}

適当なcppファイルに関数を実装する。

#include<Siv3D.hpp>
#include"CoreData.h"
#include"Effecter.h"

<ClassName>::<ClassName>(CoreData& input_data) :Effecter(input_data){};

bool <ClassName>::needs_enable(){
    //起動条件を満たしたらtrueをreturnするように実装
}

//その他もろもろの関数を実装

"Main.cpp"void Main()内にこんな感じで追記。

<ClassName> <InstanceName>(core_data);
effect_ctrl.push_to_disabled(<InstanceName>);

割と面倒くさい

感想

初めてプログラミングに触れた(プチコンっていう、DSiで動くBASIC環境でした)小学生の頃は、ちょっとした入力や条件分岐はできても「このサンプルゲームどうやって動いてるの……」っていう感じでした。

で、それから5年ぐらい。なんかそれっぽい(これは罠で、実用性皆無)ものができました。素直に嬉しい。

どんなに複雑なプログラムでも「入力」「処理」「出力」しか無いんですよね。ここらへんの「できるだけシンプルに捉える」考え方を持てたのは競プロ効果かもしれないです。

また、実装を通してc++の機能をたくさん学習しました。c++機能多すぎ

エフェクタは割と簡単に追加できるように実装してみました(そのつもり)。ちょっとずつ機能追加していけたら良いなあ。

最後に、このソフトの開発を実現してくれたSiv3D開発チームの方々に感謝申し上げます。

では。

更新履歴

20180325 動作映像をv0.1.1仕様に変更