nashidos’s diary

アルゴリズムとか機械学習とか色々

.gitignoreファイルの簡単な作り方

本記事では、.gitignoreファイルを簡単に作る方法について紹介していきます。

どうやって.gitignoreファイルを作ればいいかわからない、.gitignoreファイルをもっと簡単に作成したいという方向けの記事です。

.gitignoreのテンプレ

なかなか.gitignoreを1から自分で書くのはめんどくさいですし、初心者の方にとっては、どのファイルをignoreすればいいのかわからない時もあるかもしれません。

そんな人のために.gitignoreのテンプレを用意してくれるサイトがあります。
www.toptal.com

使っている言語やフレームワーク等で検索すると.gitignoreのテンプレを見ることができます。
以下は検索結果の例です。
f:id:nashidos:20210112115048p:plain

ちなみに、複数の項目を同時に検索することも可能です。
f:id:nashidos:20210112114115p:plain

コマンドラインから利用

Webから検索してそのまま利用することもできますが、curlwget等で利用することもできます。

例えば以下のように直接.gitignoreファイルに書き出せば簡単に.gitignoreを作成することができます。

curl -L http://www.gitignore.io/api/python,django,windows > .gitignore

おわりに

あくまでテンプレートなので、その後の取捨選択は必要ですが、新しいプロジェクトを作成したときに手っ取り早く作れるのは便利ですね。

おわり

Pythonで半分全列挙を実装してみる-ABC184

本記事では、半分全列挙をPythonで実装していきます。

実際に一緒に問題を解きながら半分全列挙を理解しましょう。

半分全列挙とは

半分全列挙は、その名の通りN個の要素を半分に分けてそれぞれを全列挙し、半分に分けたグループから組み合わせを考えることで高速に解を求める方法です。

具体的には以下のような流れになることが多いです。

  1. 半分のグループLを全列挙
  2. もう半分のグループRを全列挙
  3. Lから要素を1つ選び固定し、二分探索を用いて最適な組み合わせを探す(全ての要素に対して繰り返す)

それでは、実際に例題を解きながら理解していきましょう。


例題

今回は以下の問題を扱います。
atcoder.jp

問題文

高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は T 分間で、 N 問の問題が出題されます。高橋くんは超能力者なので、 i 番目の問題が A_i 分で解けることが分かっています。高橋くんは N 問の中から 0 問以上を、解くのにかかる時間の総和が T 分以下になるように選び、それらの問題を解きます。
選んだ問題を解くのにかかる時間の総和の最大値を求めてください。

制約

  • 入力は全て整数
  • 1≤N≤40
  • 1≤T≤10^9
  • 1≤A_i≤10^9

実装

選んだ問題を「解く」「解かない」の2パターンで考えることができるので全探索で答えを求めることはできます。

しかし、この例題における全探索の計算量はO(N^2)です。また、1≤N≤40なので、到底全探索では間に合いません

そこで、半分だけ全列挙した場合の計算量を考えてみましょう。半分であれば最大でもN=20なので2^{20}≒10^6程度で計算することが可能です。

半分全列挙した前半のグループをL、後半のグループをRと呼ぶことにします。

半分に全列挙することができれば、あとは皆さんご存知の二分探索で解を求めることができます。

例えば、Lの要素であるL_iを固定した場合、「T-L_i>=R_iという条件を満たす最大のR_iを探す」という話になります。

Pの要素を固定して全探索するにはO(N^{N/2})かかり、二分探索にはO(log(2^{N/2}))かかるので、全体でO(N2^{N/2})でこの問題を解くことができます。

以下が実装例のコードです。

from bisect import bisect_right
 
N, T = map(int, input().split())
A = list(map(int, input().split()))
L = [0]
R = [0]
for x in A[:20]:
    for i in range(len(L)):
        L.append(x + L[i])
for x in A[20:]:
    for i in range(len(R)):
        R.append(x + R[i])
R.sort()

ans = 0
for x in L:
    if x > T:
        continue
    y = R[bisect_right(R, T - x) - 1]
    if ans < x + y:
        ans = x + y

print(ans)

参考元:https://atcoder.jp/contests/abc184/submissions/18300926

まとめ

半分全列挙はさほど難しいアルゴリズムではないですね。

正しく列挙し、二分探索を行うことができれば解ける問題でした。

Nの数が少ない場合などに半分全列挙の可能性を考えてみてもいいかもしれません。

おわり