2020-05-24

n個からk個取る組み合わせを全探索したいときメモ

bit全探索に慣れたい。

蟻本より、n個からk個取る組み合わせのJava版

public class Main {
    public static void main(String[] args){
        int n = 4;
        int k = 2;
        
        int comb = (1<<k) -1;
        while(comb < 1 << n){
            System.out.println(Integer.toString(comb,2));
            int x = comb & -comb;
            int y = comb + x;
            comb = ( (comb & ~y) / x >> 1 ) | y;
        }
    }
}
/*
11
101
110
1001
1010
1100
*/

式の意味がわからなかったから行間を埋める。

0でない整数xに対して、x & -xは最下位の1のビットのみを取り出す
- -xは補数の定義より~x + 1
- ~xはxの最下位に続く0たちがすべて1になっている数だから、そこに1を足すと求めたいビットだけxと~x+1に対して1が揃うイメージ。
- 補数の定義は足すと繰り上がりになる数のうち最小の数
x = comb & -combとすると、y = comb + xはcombの末尾にある...001111000を...010000000にしてくれる
上の例で言うとyはビットを3つ失っている。どこかで3つ分補充したい。comb & ~yを考えると元々並んでいた末尾の1のグループ(4つ並んだ1)だけ得ることができる。xは末尾の1のグループの最下位であるため、xで割ってあげれば4つの1を得ることができる。さらに1ビット右にシフトすれば、(4-1=)3個の1を手に入れることができる。((comb & ~y) / x >> 1)
上で手に入れたものが補充したいビットである。( (comb & ~y) / x >> 1 ) | y

隣り合う要素を同時に含まないような集合についてはまた今度考えよう。

2020-05-19

C - N進数

競技プログラミング Java

CODE FESTIVAL 2014 決勝 - AtCoder

20200519のあさかつで出た問題

概要

10以上の整数 $N$ に対して、 $N$ 進数で表したとき $N$ と表せる数を $f(N)$ とする。

与えられた整数 $A$ に対して、 $f(k)$ と表すことができる $k$ が存在すれば $k$ を出力。

なければ $-1$ を出力せよ。

制約

$1 \leqq A \leqq 10^ {16}$

方針

$f(N)$ の性質より、調べなければならない $k$ の範囲はそんなに大きくないです。全探索します。

整数 $N$ を $k$ 進数で表したときの10進数表記を $N_{(k)}$ とします。

$10 \leqq k \leqq 10000$ のすべてのkに対して、 $k = N_{(k)}$ を満たすかどうか判定します。

$N$ 進数

Long#toStringはJavaで進数変換するときによく使います。*1

数字と基数を与えれば、文字列型で進数変換した結果を返してくれます。*2

long N = 100;
System.out.println(Long.toString(N, 2));
System.out.println(Long.toString(N, 16));
System.out.println(Long.toString(N, 17));

/*
1100100
64
5f
*/

ただしこれには制約があり、2～36進数の間でしか変換してくれません。*3

それ以外の基数を与えると10進数の結果で返ってきます。*4

long N = 100;
System.out.println(Long.toString(N, 1));
System.out.println(Long.toString(N, 2));
System.out.println(Long.toString(N, 36));
System.out.println(Long.toString(N, 37));

/*
100
1100100
2s
100
*/

自前で基数変換を行いました。

大枠としては基数で割ったあまりを文字列に追加していくことを繰り返していきます。

ミュータブルであるStringBuilderを利用すると気楽に実装できます。reverseメソッドが便利です。

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int ans = -1;
        long A = sc.nextLong();
        for(int i=10; i<10001; i++){
            StringBuilder tmp = new StringBuilder();
            long a = A;
            while(a>0){
                long t = a%i;
                if(t > 9)break; //表記が数字でなくなった時点で無視
                tmp.append(t);
                a -= t;
                a /= i;
            }
            tmp = tmp.reverse();
            if(String.valueOf(i).equals(tmp.toString()))ans = i;
        }
        System.out.println(ans);
        sc.close();
    }
}

*1:実際は、Integer#toStringの方がよく使います。今回は問題の制約条件的にLongを紹介

*2:2進数はtoBinaryString、8進数はtoOctalString、16進数はtoHexStringと専用のメソッドがありますが、競技プログラミングをする上では全部toStringで実装しちゃいます。

*3:アルファベットが26文字しかないからでしょうか

*4:これを知らなかったのでだいぶ時間をとられました。

2020-04-06

C - Numbering Blocks

競技プログラミング Java

問題文：C - Numbering Blocks

解説を見ると全探索か深さ優先探索で解いている人が多く、DPで解いている人があまりいなさそうだったのでメモを残します。

考察

以下のイメージです。
dp[i][j][k]を次で定義する
- $(a_1, a_2, a_3) = (i,j,k)$ のときの条件を満たす数字の書き込み方の数
DP遷移
- dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k] + dp[i][j][k-1]
初期値

dp[1][0][0] = 1;
dp[1][1][0] = 1;
dp[1][1][1] = 1;

$i \geqq j \geqq k$ の条件に注意

コード*1

int a1 = scan.nextInt();
int a2 = scan.nextInt();
int a3 = scan.nextInt();

int[][][] dp = new int[4][4][4];
dp[1][0][0] = 1;
dp[1][1][0] = 1;
dp[1][1][1] = 1;
for(int i=2; i<4; i++){
    for(int j=0; j<4; j++){
        for(int k=0; k<4; k++){
            if(!(i>=j && j>=k))continue;
            dp[i][j][k] = 
                    (i-1>=j ? dp[i-1][j][k] : 0)
                    + (j-1>=k ? dp[i][j-1][k] : 0)
                    + (k-1>=0 ? dp[i][j][k-1] : 0);
        }
    }
}

System.out.println(dp[a1][a2][a3]);

フック長公式というキーワードが気になる。調べる。

*1:入出力用のライブラリを使用している

2020-04-05

優先度付きキューメモ

競技プログラミング Java メモ

Javaで優先度付きキューを取り扱うときに毎回調べている気がする。メモする。 - PriorityQueue (Java Platform SE 8 )

Queue<Integer> que = new PriorityQueue<>();
que.add(3);
que.add(1);
que.add(4);
que.add(1);
que.add(5);

while(!que.isEmpty()){
    int i = que.poll();
    System.out.print(i+" ");
}

// 実行結果
// 1 1 4 3 5

自然順序でソートされる。数値だったら小さい順。

大きい順とか、自然順序以外のソートをしたい場合はComparatorを引数に渡す。

Queue<Integer> que = new PriorityQueue<>((a,b)->Integer.compare(b,a));

que.add(3);
que.add(1);
que.add(4);
que.add(1);
que.add(5);


while(!que.isEmpty()){
    int i = que.poll();
    System.out.print(i+" ");
}

// 実行結果
// 5 4 3 1 1

java.util.Collections#reverseOrder()を使用する方法もあるけど、ラムダ式で書くほうが拡張性高くて好き（二次元配列でソートするときとか）

2020-03-26

統計学入門メモ(1章統計学の基礎)

基礎統計学I 統計学入門を読み進めています。自分の認識や、調べたこと、行間や補足のメモを残していきます。知識の整理が目的ですので、本に記述されていない内容を含んでいたりします。

1章統計学の基礎

1.1 統計学とは

記述統計学と統計的推測

記述統計学

対象全てのデータが存在し、そのデータの規則性や法則をわかりやすく説明する学問
データが存在することが前提。さらに、すべての情報があることが必要(全数調査)
例
- 平均
- ヒストグラムなどのグラフ化
ここで言う全てのデータが母集団

統計的推測

集めたデータ≒標本から母集団の特徴を推測する学問
大きく推定と仮説検定に分かれる
例
- 選挙の当選確実
- 視聴率

平均への回帰

データに偏りがあっても、最終的には平均に近づいていくこと
遺伝学者ゴルトンのスイート・ピーの趣旨の直径の測定
- 親をx軸、子をy軸とすると、直線の傾きは1/3になった。
- 直径の小さい親から生まれた子供の直径は、親の直径より大きく、逆に直径の大きい親から生まれた子供の直径は、親の直径より小さかった。
- 遺伝の影響が限りなく強い(いわゆる、相関係数が1)場合は、親と子の直線の傾きは1になるはず、それが1/3になったということは、遺伝の影響よりも偶発的なぶれ（分散）が大きかった。
このように、分散が大きいような集合の平均を繰り返しとっていった場合、最終的には全体の平均に近づいていく。これを平均への回帰という。
平均への回帰を意識していないと、「改善効果があった」と勘違いすることがある(回帰の誤謬)

標本分布

標本の統計量の分布
母集団から標本を抽出することは理論上何回でも可能であり、それらの統計量はばらつきがあるため分布として記述できる。

1.2 統計データと統計手法

量的データ
- 定量的なデータ
- 例：長さや重さ、金額、時間など
質的データ
- 量的データ以外。カテゴリー等
- 対応する数字(ダミー変数)を与えることで量的データとして扱うこともある
- 例：男女、天気、地域など
時系列データ
- 同一の対象に対する、異なった時点での観測値
クロスセクションデータ
- 同一の時点に対する、異なった対象での観測値
パネルデータ
- 時系列データ×クロスセクションデータ

1.3 統計データの分析プロセス

仮説（何を対象にどのようなことを分析するか）を決める
データが存在しない場合は収集する
- 原データ
  - 実験や調査から得られる生のデータ
- 統計資料
  - 行政機関や研究機関などが作成した、原データに統計処理を行った後の資料
  - 以下の定義に注意しないと、誤った結論につながる
    - 誰が行ったものか
    - 全数調査 or 標本調査
    - 調査対象
    - 時期
    - 地域
    - 分類
    - etc
統計分析
- 様々な統計手法を用いる理由を理解していくことが重要
結果の解釈
- 今後勉強していく部分

練習問題

1.1 総務省統計局「日本の統計 2019」

壁とかパズルとか

パズルと将棋とボルダリングとダイビングが趣味です。

n個からk個取る組み合わせを全探索したいときメモ

C - N進数

概要

制約

方針

$N$ 進数

C - Numbering Blocks

考察

コード*1

優先度付きキューメモ

統計学入門メモ(1章統計学の基礎)

1章統計学の基礎

1.1 統計学とは

記述統計学と統計的推測

記述統計学

統計的推測

平均への回帰

標本分布

1.2 統計データと統計手法

1.3 統計データの分析プロセス

練習問題

参考資料

概要

制約

方針

進数

考察

コード*1

1章 統計学の基礎

1.1 統計学とは

記述統計学と統計的推測

記述統計学

統計的推測

平均への回帰

標本分布

1.2 統計データと統計手法

1.3 統計データの分析プロセス

練習問題

参考資料

$N$ 進数

1章統計学の基礎