あらこまノート

あらこま日記

よろしく

ABC141D - Powerful Discount Tickets

AtCoder Python priority queue heapq

問題

atcoder.jp

【概要】
N個の品物があり、それぞれA_{1}...A_{N}円である。
M枚の割引券があり、一回使うと任意の品物の値段を1/2にできる(小数以下切捨、同じ品物にも重ねて使える)。
全ての品物を買えるような最小の金額を求める。
【制約】
1\leq N,M \leq 10^{5}

考える

  • 一番値段の高い品物に割引券使う。これをM回やればよさそう。

  • 割引するごとにソートして一番高い値段を得る。⇒TLE...

  • 時間切れまでいろいろやるも終了。

解説見る

  • (pythonの)max()は O(N)なので、愚直に繰り返すと O(NM)でTLEする。

  • 優先度付きキュー（priority queue, heap queue）を使うと、配列について以下の操作を比較的高速に行える。

    • 値の追加 O(\log_{}{N})
    • 値の削除 O(\log_{}{N})
    • 最小値(最大値)の取得 O(1)

  • 最小値(最大値)のみを得たい、のみに処理したい、を何回も繰り返す場合は優先度付きキューを使うと速い！！！

  • pythonだとimportして使える。
import heapq

heapq.heapify(L) #list(L)をheapに変換
heapq.heappop(L) #最小値を取り出して返す
heapq.heappush(L, a) #heapに値(a)を追加

注意！pythonのheapqは最小値が根にくるので、最大値が欲しいなら全部の要素に-1をかけてからheapに変換する。

  • これらを使うと、「一番高い品物を選んで半額にする」という操作を O(\log N) でできる。よって、全体で O(M \log N) で間に合う。

ACコード(python)

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))

#全要素に-1かける
for i in range(len(A)):
    A[i] *= -1

heapq.heapify(A)
for _ in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, (-x//2)*(-1)) #切り下げのためマイナスを2回かける

print(-sum(A))#全要素を負にしたので戻すためにマイナス付ける

おわりに

くぇうぇ笑

参考(ありがとうございます…！)

ABC125C - GCD on Blackboard(300)

AtCoder Python gcd 累積

解いた問題で面白かったものについて書いていくことにしました。
今の自分は300点（ABCがABCDまでの時）が解けるか解けないかってかんじなので、当分はそのへんの問題が多くなりそうです。

問題

atcoder.jp 【概要】
N個の整数 A_1,A_2,...,A_N がある。
この中から1つ選んで好きな整数（1以上10**9以下）に書き換えてもよい。
書き換えた後のN個の整数の最大公約数の最大値を答える。

【制約】

  • 入力は全て整数。
  • 2\leq N\leq 10^{5}
  • 1\leq A_i\leq 10^{9}

考える

  • 何を1個だけ書き換えても、残りのN-1個でのgcdより大きくならなそう。
  • N-1個でのgcdに書き換えるとすると、整数1個を取る（消す）のと同じ。
  • （愚直に1個ずつ消してgcdとっていくのはTLEでしょ…？）

結局自力ACできず…

解説見る

  • 複数個の整数でgcdをとるとき、どのペアから始めても結果は同じになる。
  • なので、整数Aiの「左側( A_{0\sim i-1} )でのgcd」と「右側( A_{i+1\sim} )でのgcd」とでgcdをとれば、Aiを消した時の結果が得られる。すべてのAiについて求めた中の最大が答え。と考える。
  • ⇒累積和みたいにgcdを左端からと右端からとの2通りとっていき、それぞれlistに保持することでこれを実装できる。
    f:id:Arakoma:20190906195606j:plain

ACコード（python）

Submission #7352699 - AtCoder Beginner Contest 125

N = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(1, N+1):
    L[i] = gcd(L[i-1], A[i-1])
for i in range(N)[::-1]:
    R[i] = gcd(R[i+1], A[i])

M = [gcd(L[i], R[i+1]) for i in range(N)]

print(max(M))

おわりに

初めてTeX書いたけどめっちゃ時間かかった…。
次も書くかは謎(?)。

VSCodeでC++の環境構築（win10,MinGW）

C++ 環境構築 VSCode MinGW

最近、蟻本を読み始めました（Pythonしか読めない顔）

ということで、
VSCodeでC++を書く環境構築について、自分用まとめです。

注：ここではMinGWを使いました。WSL(windows subsystem for linux)で環境構築する方法もあるらしい（よくわかってない）ので、そっちも調べてみてください。

想定環境

  • Windows10
  • VSCodeインストールして日本語化拡張済み

目標

VSCodeで、

をできるようにする。

やること

  • MinGWインストール
  • Pathを通す
  • VSCodeにC/C++拡張をインストール
  • VSCodeのターミナルからコンパイル、結果表示

    順番にやっていきましょーう

    MinGWインストール

    コンパイラをインストールします。
    MinGWを使います。
    このサイト見ながらやりました。（ありがとうございました…！） webkaru.net
    自分がやったときは(2019/05/23)、MinGWのサイト内のダウンロードボタンの位置とかが微妙に違ったので注意。

    Pathを通す

    無事インストール出来たら、Pathを通します。

  • Windowsの設定を開き、「環境変数を編集」で検索。
    f:id:Arakoma:20190522170641p:plain
  • それを開いて、「Path」をクリック。
    f:id:Arakoma:20190522171207j:plain
  • 「編集」をクリック。
  • すると、「環境変数の編集」のウィンドウが開く。
  • 「新規」をクリックして、C:\MinGW\bin と入れる。
    f:id:Arakoma:20190522172737j:plain

    OKを押すとPathが通ります。

    VSCodeにC/C++拡張をインストール

    C/C++拡張をインストールすると、コードを書くときに色々サポートしてくれます。
    VSCodeの拡張機能でC++と検索したら上の方に出ると思います。

    VSCodeのターミナルからコンパイル、結果表示

    ここまでで準備は終わりです。
    最後にコードのコンパイル、結果表示までの手順をやっていきます。

  • 実行するファイル作る
    Ctrl+N で新規ファイル作成です。
    Ctrl+S で名前を付けて保存。
    今回はhello.cpp という名前でファイル作って以下のコードをコピペします。
#include <iostream>
using namespace std;

int main(){
    cout << "Hello world" << endl;
}


  • ターミナル開く
    Ctrl+@ でターミナル（powershell）が開く。

  • 「g++ ファイル名」でEnter
    f:id:Arakoma:20190523000829j:plain すると、新しいファイルが出現します。
    （写真だとa.exe）
    これはコンパイルされた結果が入ってます。

  • 「.\ ファイル名」でEnter f:id:Arakoma:20190523001400j:plain

結果が表示されればOKです。 お疲れさまでした！
ちなみに、
.cppを.c、g++をgcc、にするとCでの実行になります。

とりあえずターミナルから実行できるようになったと思います。
自分はまだ全然C++書いてないので、
また何か便利な拡張とかあったら追記するかもしれないです。