sumoch1メモ

記録に残したいことを書いていきます。文章力はないです。

Visual Studio Code で C++ でAtcoderを始める時のメモ

Visual Studio CodeC++ のコーディング/ビルド/デバッグを実行できるようにするまでの初期設定手順
若干手間取ったので自分用のメモ
1.VSCodeをインストールする 日本語化もしておく

2.MinGW-w64 を導入する
下のサイトを見てインストール
MinGW-w64 を導入する — しっぽのさきっちょ | text.Baldanders.info
PATHにMinGW-w64をインストールしたフォルダを追加する
例:C:\Program Files\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin

3.この記事を見てVScodeの設定をする

Visual Studio Code での C++ の初期設定 (Windows x gcc(MinGW) 編) - Qiita
"compilerPath"や"miDebuggerPath"はMinGW-w64をインストールした場所に書き換えます
task.jsonとlaunch.json

C++で競プロをやるためのVSCodeの環境づくり - Qiita
この記事を参考にしてコンパイルオプションを書き換えます。

4.その他のカスタマイズ

Visual Studio Codeで競プロ環境構築(実践編) - Qiita

「1000円分の切手を買ってきて」とお願いされた時の買い方のパターンの総数を計算するプログラム(Python)

このツイートを見てプログラムを作って計算してみました。

初心者なので計算が合っているか保証できません。
間違ってたら誰か教えてください。

再帰を使ったアルゴリズムで計算します。
x円で買うことが出来るパターンの総数をf(x)とします。f(0)=1とします。

残金がx円の時、x円以下の切手(値段p)を選びf(x-p)を足します。これを繰り返します。
 この時(1,2)と(2,1)などの重複をカウントしないために高い切手から順に買います。前の試行で買った切手y円より高い切手を買わないようにします。
このためf(x,y)を「y円以下の切手でx円分買う時の組み合わせの総数」として再帰的に計算を行います。

再帰的に計算することで計算量が莫大になるためメモ化再帰を使います。
https://qiita.com/alchemist/items/c75174c41b0bcd31ecc6

from functools import lru_cache
price_list = [1, 2, 3, 5, 10, 20, 30, 50, 62, 82,
              92, 100, 120, 140, 205, 280, 310, 500, 1000]
price_list = price_list[::-1] #降順にする

@lru_cache(maxsize=10000)
def count(x, y):
    if x < 2:
        return 1
    else:
        sum_price = 0
        for p in price_list:
            if x-p >= 0 and p <= y:
                sum_price += count(x-p, p)
        return sum_price

print(count(1000,1000)


計算結果は
1141266126310
1兆通り以上あるらしいです。
間違っていたらこちらまでご連絡ください↓
もち (@sumoch1) | Twitter