ベスパリブ

プログラミングを主とした日記・備忘録です

Educational DP Contest I - Coins 解いた

解説

// dp[i][j] := i枚目を投げたとき表がj枚の確率
// p[i] := i枚目が表が出る確率

ということっぽいのはわかるのだが、ここからどうすればいいのかわからなかったので、一つずつdpの状態を書いていった。

// 1枚投げて表が0枚の確率
dp[1][0] = 1-p[1]; 
// 1枚投げて表が1枚の確率
dp[1][1] = p[1];    
// 2枚投げて表が0枚の確率 = (1枚投げて表が0枚の状態で、2枚目が裏)
dp[2][0] = dp[1][0]*(1-p[2]);  
// 2枚投げて表が1枚の確率 = (1枚投げて表が0枚の状態で、2枚目が表) + (1枚投げて表が1枚の状態で、2枚目が裏)
dp[2][1] = dp[1][0]*p[2] + dp[1][1]*(1-p[2]);  
// 2枚投げて表が2枚の確率 = (1枚投げて表が1枚の状態で、2枚目が表)
dp[2][2] = dp[1][1]*p[2];  
// 3枚投げて表が0枚の確率
dp[3][0] = dp[2][0]*(1-p[3]);  
// 3枚投げて表が1枚の確率
dp[3][1] = dp[2][0]*p[3] + dp[2][1]*(1-p[3]);  
// 3枚投げて表が2枚の確率
dp[3][2] = dp[2][1]*p[3] + dp[2][2]*(1-p[3]);  
// 3枚投げて表が3枚の確率
dp[3][3] = dp[2][2]*p[3];  

なんだが法則性が見えてきた。

求める答えは「表の個数が裏の個数を上回る確率」なので、dp[N][(N/2)+1]~dp[N][N]の総和を求めれば良い。

というわけで、最終的なコードは以下のようになった。

#include <bits/stdc++.h>
#define _USE_MATH_DEFINES  // M_PI等のフラグ
#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INF = 1001001001;
void chmax(int& x, int y) { x = max(x,y); }
void chmin(int& x, int y) { x = min(x,y); }


void solve(){
    int N; cin >> N;
    vector<double> p(N+1, 0.0);
    for (int i=1; i<N+1; i++) {
        cin >> p[i];
    }

    // dp[i][j] := i枚目まで投げたときの表がj枚になる確率
    vector<vector<double>> dp(N+1, vector<double>(N+1, 1.0));
    dp[1][0] = 1.0-p[1];  // 1枚投げて表が0枚の確率
    dp[1][1] = p[1];    // 1枚投げて表が1枚の確率

    // dpを埋める
    for (int i=2; i<N+1; i++) {
        for (int j=0; j<i+1; j++) {
            if (j==0) {
                dp[i][j] = dp[i-1][0] * (1.0-p[i]);
            }
            else if (j==i) {
                dp[i][j] = dp[i-1][j-1]*p[i];
            }
            else {
                dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1.0-p[i]);
            }
        }
    }

    // 求める答えはdp[N][(N/2)+1]~dp[N][N]の総和
    double ans = 0.0;
    for (int j=(N/2)+1; j<N+1; j++) {
        ans += dp[N][j];
    }

    printf("%.10f", ans);
}


int main(int argc, char const *argv[]){
    solve();
    return 0;
}

以下のけんちょんさんの解説を見たらもっとすっきり書けるようです。

Educational DP Contest の F ~ J 問題の解説と類題集 - Qiita

ABC 181: E問題の解説 (C++)

問題:AtCoder Beginner Contest 181: E - Transformable Teacher

解説

 H Wは事前にソートしておきます。

先生と組む生徒以外の人のペアの身長差は、ソートしたときに隣り合う人でペアを作り続ければよさそう。

図にすれば以下。

黒丸が先生と組む生徒 i、白丸はそれ以外の生徒。

f:id:takeg:20201114161152j:plain
ペアの作りかた

図を眺めると、「先生と組む生徒」以外のペアの身長差の合計 totalは、最初の1回目( i=0のとき)に totalを計算するときだけ O(N)かかりますが、2回目以降( i=1以降)は、しゃくとり法を使えば totalの計算は O(1)で計算できそうです。

あとは「先生と組む生徒」と「先生」の身長差を高速で求めたいですが、これも先生が変身できる身長配列 Wに対して、生徒の身長がどこに入るかを二分探索すればO(logN)で求まります。

これを各生徒iのどの生徒のときに最小になるのかN回探索するので、全体としてはO(N logN)で計算できます。

実装

C++での解法です。

#include <bits/stdc++.h>
#define _USE_MATH_DEFINES  // M_PI等のフラグ
#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;


void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    vector<int> W(M);
    for (int i=0; i<N; i++) cin >> H[i];
    for (int i=0; i<M; i++) cin >> W[i];
    sort(H.begin(), H.end());
    sort(W.begin(), W.end());

    /*
    i=0から順に、先生と組む場合の身長差を計算をする
    i=1のときは、しゃくとり法を使えば先生と組む以外の人たちの身長差は一瞬で計算できるO(1)
    先生がどの身長になればよいかは、二分探索で求めればO(logN)
    よって、この計算量はO(NlogN)でいけそう
    */
    vector<int> diffT(N,0);  // 生徒iと、先生との最小の身長差
    for (int i=0; i<N; i++) {
        auto it = lower_bound(W.begin(), W.end(), H[i]);
        if (it == W.begin()) {
            diffT[i] = W[0]-H[i];
        }
        else if (it == W.end()) {
            diffT[i] = H[i]-W.back();
        }
        else {
            diffT[i] = min(abs(H[i]-*it), abs(H[i]-*(it-1)));
        }
    }

    // i=0の生徒が先生とペアになるとき
    int total = 0;
    for (int i=1; 2*i<N; i++) {
        total += H[2*i]-H[2*i-1];
    }
    int ans = total + diffT[0];

    // i=1~N-1の生徒が先生とペアになるときを、しゃくとり法で求める
    for (int i=1; i<N; i++) {
        if (i%2==1) {
            total -= H[i+1] - H[i];
            total += H[i+1] - H[i-1];
            ans = min(ans, total+diffT[i]);
        }
        else {
            total -= H[i] - H[i-2];
            total += H[i-1] - H[i-2];
            ans = min(ans, total+diffT[i]);
        }
    }

    // 出力
    cout << ans << endl;
}


int main(int argc, char const *argv[]){
    solve();
    return 0;
}

計算量は、ソートした処理も含めると O(N logN + M log M)です 。

PowerShellのエラー「System.ArgumentOutOfRangeException: 値には 0 以上で、コンソールの次元のバッファー サイズ しなければなりません。」

解決方法

PowerShellの画面をリサイズすれば直る

現象

VSCodePowerShellを使っていて、キーの「.」を打つと以下のようなエラーが出た。

PS C:\Users\takey\Desktop\myspace\workspace\Algorithm>
問題が発生しました。このバグを以下の詳細と共に報告してください。
GitHub で報告: https://github.com/lzybkr/PSReadLine/issues/new
-----------------------------------------------------------------------
直前 96 個のキー:
 P r i m Tab s e g m e n t Tab LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow Leftrrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LetArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow LeftArrow eftArrow LeftArrow g + + Space Enter
 . . . . Enter
 . . Backspace Backspace Enter
 . Backspace Backspace g + + Space P r i m e Tab s e g m e n t Tab Enter
 . / a Enter
 Enter
 . Backspace .

例外:
System.ArgumentOutOfRangeException: 値には 0 以上で、コンソールの次元のバッファー サイズ
しなければなりません。
パラメーター名:left
実際の値は -2 です。
   場所 System.Console.SetCursorPosition(Int32 left, Int32 top)
   場所 Microsoft.PowerShell.Internal.VirtualTerminal.set_CursorLeft(Int32 value)
   場所 Microsoft.PowerShell.PSConsoleReadLine.ReallyRender(RenderData renderData, Striolor)
   場所 Microsoft.PowerShell.PSConsoleReadLine.ForceRender()
   場所 Microsoft.PowerShell.PSConsoleReadLine.Insert(Char c)
   場所 Microsoft.PowerShell.PSConsoleReadLine.SelfInsert(Nullable`1 key, Object arg)
   場所 Microsoft.PowerShell.PSConsoleReadLine.ProcessOneKey(ConsoleKeyInfo key, DictioatchTable, Boolean ignoreIfNoAction, Object arg)
   場所 Microsoft.PowerShell.PSConsoleReadLine.InputLoop()
   場所 Microsoft.PowerShell.PSConsoleReadLine.ReadLine(Runspace runspace, EngineIntrinIntrinsics)
-----------------------------------------------------------------------

エラーの発動条件が意味不明だったのですが、なんかここのissueを見ると、

This issue happens only when you resize the window after UpArrow and before Escape.

とありましたので、試しに画面サイズを変更すると現象が起こらなくなりました。なんか入力カーソルが画面右ぎりぎりの状態で「.」や「,」を打つとエラーが起きるらしい。

f:id:takeg:20201108205724p:plain
このくらいの状態で「.」や「,」と打つとエラーが出る

f:id:takeg:20201108203318p:plain
こんなエラーが出る

f:id:takeg:20201108203358p:plain
画面サイズを大きくするとエラーは起こらなくなった

追記

Powershellのバージョンをアップデートすれば直るらしい

Chromeストアの画像アセット(アイコン)の作り方(とりあえず登録できればいい人向け)

Chromeストア用のショップアイコンと、スクリーンショットやプロモーション タイルの作り方について書いていきます。

ショップアイコンの作り方

Chrome拡張を作成してChromeストアに登録する際、ショップアイコンを必ず登録しないといけません(2020/10/31現在)。

ショップアイコン用の画像は、128x128px(実際は96x96で、上下左右の16pxは透過)が必要です。

この仕様に満たない画像をアップロードしようとした場合(透過になっていない場合)、アップロード中の処理は無限に終わりません

透過アイコンの作り方なんて知らないし適当でいいんだよな私みたいな人向けに、ショップアイコンの作り方を以下に記載します。Windows10標準搭載の3Dペイントを使うのでWindows10向けです。

まずは96x96の画像(画像A)を作成する。

画像は適当にパワポで作って、ペイントでサイズ変更して作りました。

f:id:takeg:20201031172648p:plain
96x96

画像AをWindows10標準アプリ「ペイント3D」で開く

画像を右クリックして「画像を3Dペイントで開く」で開きます。

f:id:takeg:20201031172947p:plain
3Dペイントで開く

上の「キャンバス」タブをクリックする

f:id:takeg:20201031173046p:plain
キャンバスをクリック

すると画面右側にキャンバスの設定が表示されます。

次の手順でキャンバスの設定をする

  1. 「透明なキャンバス」をオンにする
  2. 「キャンバスでの画像のサイズ変更」をチェックなしにする
    • 「縦横比を固定する」はどっちでもいいです。
    • これをする前に次の幅と高さを変更すると画像のサイズも変更してしまうので注意。
  3. 幅と高さを128x128にする

これで実画像のサイズは96x96のままで、背景画像が128x128になります。

f:id:takeg:20201031173724p:plain
最終的なキャンバスの設定はこんなかんじ

f:id:takeg:20201031174537p:plain
画像の回りに白い枠が出てきたら成功

左上の「メニュー」から「名前を付けて保存」で「画像」でpng保存する

これで128x128px(実際は96x96で、上下左右の16pxは透過)のショップアイコンが作成できました。

スクリーンショットやプロモーション タイルの作り方

Chromeストアのスクリーンショットやプロモーションタイルの作り方を記載していきます。

スクリーンショットやプロモーション タイルは適当にJPEGで作ればそのままでOKなんですが、JPEGは保存のたびに劣化するのでPNGで保存したいです。PNGのときだけ少し注意が必要です。

例えば「プロモーション タイル(小)」の仕様は次のようになっています。(2020/10/31現在) * 440×280 キャンバス * JPEG または 24 ビット PNG(アルファなし)

JPEGのときは何もしなくていいっぽいんですが、問題はPNGのときで、24ビットPNG(アルファなし)という制限がついています。

おそらく適当にPNG保存したら深度32ビットの画像になっていると思います。画像の深度を調べるには、画像ファイルを右クリックして「プロパティ」>「詳細」タブで確認できます。

f:id:takeg:20201031183732p:plain
深さ32ビットのPNG画像

Chromeストアに登録しようとして以下のような「エラー:不明なエラーが発生しました。」とか出たら、この深度の違いによって登録できない可能性があります。

f:id:takeg:20201031183838p:plain
登録しようとしたらエラーが出る。具体的なエラーメッセージは出してくれない

なので24ビットPNGに無理やり修正します。

画像をペイントで開いて、「名前を付けて保存」でファイルの種類を「24ビットマップ(.bmp;dib)」で保存します。その後、保存したファイルの拡張子をPNGに変更したらOKです。

以上です。

ルート証明書の探し方

ルート証明書を探す作業をたまにお仕事でするのですが、私なりの探し方をまとめました。

ブラウザの場合

ブラウザの鍵マークをクリック>証明書>証明書のパス>一番上の証明書をクリック>証明書の表示

f:id:takeg:20200926130706p:plain
ブラウザの鍵マークをクリック

f:id:takeg:20200926130730p:plain
一番上のルート証明書をクリックして、「証明書の表示」をクリック

ルート証明書が見れます。

ルート証明書のダウンロード(エクスポート)も「詳細」タブの「ファイルにコピー」でできます。

f:id:takeg:20200926130923p:plain
「ファイルにコピー」でダウンロードできる

エクスポートするときのファイル形式は、

  • DER形式(DER encoded binary X.509)
  • PEM形式(Base 64 encoded X.509)
  • P7B形式(Cryptographic Message Syntax Standard)

の3種類から選べます。

ブラウザ以外の場合

ルート証明書の名前がわかっている場合

「[ルート証明書名 or 企業名] root certificate」等でググって、ダウンロードできるサイトを探します。

「GlobalSign Root CA - R2 root certificate」とかで検索して探します。

ルート証明書/中間CA証明書(SSLサーバ証明書) | サポート・お申し込みガイド | GMOグローバルサイン【公式】

ルート証明書を発行しているCA認証局は大体サイトからダウンロードできるようにしてくれているので頑張って探します。

ルート証明書の名前がわかっていない場合

OpenSSLを使います。

まず、opensslコマンドを使ってサーバとTLSなりSTARTTLSなりで通信をします。その際に-showcertsオプションを指定すると証明書チェーンが表示されるので、それを見ればルート証明書がわかります。

以下ではGmailSMTPサーバ(smtp.gmail.com)のルート証明書を探します。

> openssl s_client -connect smtp.gmail.com:587 -starttls smtp -showcerts
CONNECTED(000001C0)
depth=1 C = US, O = Google Trust Services, CN = GTS CA 1O1
verify error:num=20:unable to get local issuer certificate
verify return:1
depth=0 C = US, ST = California, L = Mountain View, O = Google LLC, CN = smtp.gmail.com
verify return:1
---
Certificate chain
 0 s:C = US, ST = California, L = Mountain View, O = Google LLC, CN = smtp.gmail.com
   i:C = US, O = Google Trust Services, CN = GTS CA 1O1
-----BEGIN CERTIFICATE-----
MIIEyDCCA7CgAwIBAgIQSzhrqklQvncCAAAAAHpLZDANBgkqhkiG9w0BAQsFADBC
MQswCQYDVQQGEwJVUzEeMBwGA1UEChMVR29vZ2xlIFRydXN0IFNlcnZpY2VzMRMw
EQYDVQQDEwpHVFMgQ0EgMU8xMB4XDTIwMDkwMzA2NDA0NloXDTIwMTEyNjA2NDA0
NlowaDELMAkGA1UEBhMCVVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcT
DU1vdW50YWluIFZpZXcxEzARBgNVBAoTCkdvb2dsZSBMTEMxFzAVBgNVBAMTDnNt
dHAuZ21haWwuY29tMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEDhITcefeUMYB
+nyn2h4okLuNeiWVUHA8WiGU7RQO0hcmhB5wujB7Pl8jYgIXHoOzRRmywIDIFp+V
wCQ5cFR5SaOCAl0wggJZMA4GA1UdDwEB/wQEAwIHgDATBgNVHSUEDDAKBggrBgEF
BQcDATAMBgNVHRMBAf8EAjAAMB0GA1UdDgQWBBSHRBeWPUXeRH3cDglYzWu9AJcW
cTAfBgNVHSMEGDAWgBSY0fhuEOvPm+xgnxiQG6DrfQn9KzBoBggrBgEFBQcBAQRc
MFowKwYIKwYBBQUHMAGGH2h0dHA6Ly9vY3NwLnBraS5nb29nL2d0czFvMWNvcmUw
KwYIKwYBBQUHMAKGH2h0dHA6Ly9wa2kuZ29vZy9nc3IyL0dUUzFPMS5jcnQwGQYD
VR0RBBIwEIIOc210cC5nbWFpbC5jb20wIQYDVR0gBBowGDAIBgZngQwBAgIwDAYK
KwYBBAHWeQIFAzAzBgNVHR8ELDAqMCigJqAkhiJodHRwOi8vY3JsLnBraS5nb29n
L0dUUzFPMWNvcmUuY3JsMIIBBQYKKwYBBAHWeQIEAgSB9gSB8wDxAHcAB7dcG+V9
aP/xsMYdIxXHuuZXfFeUt2ruvGE6GmnTohwAAAF0UuksiAAABAMASDBGAiEAiN7n
z854FQrffyjPiAHQWjkKnBIPaxA08/CifmKCaHUCIQCLc14iC3ac5WgDubjkXITa
SmlaVemO1Ix3eAa3g6N7kwB2AOcS8rA3fhpi+47JDGGE8ep7N8tWHREmW/Pg80vy
QVRuAAABdFLpLF8AAAQDAEcwRQIga/yh3rUb4L/1fkTTgmEMQqS/0QAmQvJfNsJr
GSwgc+oCIQD+TVQ1RU7r6ylJsPJ68N4nAZphIBMgK1fLNHfSZ3F2aTANBgkqhkiG
9w0BAQsFAAOCAQEApjaqg8SqdbyYQyck3mGS9BNytzqrbUqYqmto6KcIJvuXx83I
HDJgbSJ+u1ukUZNxs2r5D2zi5sckwu7XUJKjakz+M2gafXy6i8l3LYQQ7dawuIJa
CkkdurNlYnXqfjt1ZXLhSlmj9AF/PqKEyE0p3aBcLRbDyBkPIbPRR9QnOt6cE3rV
q8wtfzwq6qSa8e2TVe6b7pSLMMe1aVcyBY6mrXyKxcz13KwiheUg8CicptkAPBoy
w757azBTSjyPEfEpT5IomANb9AUJx4ijhyvV9MXchbNwLkhktiR9QW29VkSlXSBb
tIUdHACgD69wvelpVJlyFG/aYmWeeweg5aWFNQ==
-----END CERTIFICATE-----
 1 s:C = US, O = Google Trust Services, CN = GTS CA 1O1
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign
-----BEGIN CERTIFICATE-----
MIIESjCCAzKgAwIBAgINAeO0mqGNiqmBJWlQuDANBgkqhkiG9w0BAQsFADBMMSAw
HgYDVQQLExdHbG9iYWxTaWduIFJvb3QgQ0EgLSBSMjETMBEGA1UEChMKR2xvYmFs
U2lnbjETMBEGA1UEAxMKR2xvYmFsU2lnbjAeFw0xNzA2MTUwMDAwNDJaFw0yMTEy
MTUwMDAwNDJaMEIxCzAJBgNVBAYTAlVTMR4wHAYDVQQKExVHb29nbGUgVHJ1c3Qg
U2VydmljZXMxEzARBgNVBAMTCkdUUyBDQSAxTzEwggEiMA0GCSqGSIb3DQEBAQUA
A4IBDwAwggEKAoIBAQDQGM9F1IvN05zkQO9+tN1pIRvJzzyOTHW5DzEZhD2ePCnv
UA0Qk28FgICfKqC9EksC4T2fWBYk/jCfC3R3VZMdS/dN4ZKCEPZRrAzDsiKUDzRr
mBBJ5wudgzndIMYcLe/RGGFl5yODIKgjEv/SJH/UL+dEaltN11BmsK+eQmMF++Ac
xGNhr59qM/9il71I2dN8FGfcddwuaej4bXhp0LcQBbjxMcI7JP0aM3T4I+DsaxmK
FsbjzaTNC9uzpFlgOIg7rR25xoynUxv8vNmkq7zdPGHXkxWY7oG9j+JkRyBABk7X
rJfoucBZEqFJJSPk7XA0LKW0Y3z5oz2D0c1tJKwHAgMBAAGjggEzMIIBLzAOBgNV
HQ8BAf8EBAMCAYYwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMBIGA1Ud
EwEB/wQIMAYBAf8CAQAwHQYDVR0OBBYEFJjR+G4Q68+b7GCfGJAboOt9Cf0rMB8G
A1UdIwQYMBaAFJviB1dnHB7AagbeWbSaLd/cGYYuMDUGCCsGAQUFBwEBBCkwJzAl
BggrBgEFBQcwAYYZaHR0cDovL29jc3AucGtpLmdvb2cvZ3NyMjAyBgNVHR8EKzAp
MCegJaAjhiFodHRwOi8vY3JsLnBraS5nb29nL2dzcjIvZ3NyMi5jcmwwPwYDVR0g
BDgwNjA0BgZngQwBAgIwKjAoBggrBgEFBQcCARYcaHR0cHM6Ly9wa2kuZ29vZy9y
ZXBvc2l0b3J5LzANBgkqhkiG9w0BAQsFAAOCAQEAGoA+Nnn78y6pRjd9XlQWNa7H
TgiZ/r3RNGkmUmYHPQq6Scti9PEajvwRT2iWTHQr02fesqOqBY2ETUwgZQ+lltoN
FvhsO9tvBCOIazpswWC9aJ9xju4tWDQH8NVU6YZZ/XteDSGU9YzJqPjY8q3MDxrz
mqepBCf5o8mw/wJ4a2G6xzUr6Fb6T8McDO22PLRL6u3M4Tzs3A2M1j6bykJYi8wW
IRdAvKLWZu/axBVbzYmqmwkm5zLSDW5nIAJbELCQCZwMH56t2Dvqofxs6BBcCFIZ
USpxu6x6td0V7SvJCCosirSmIatj/9dSSVDQibet8q/7UK4v4ZUN80atnZz1yg==
-----END CERTIFICATE-----
...

このCertificate chain以下に注目します。「0」と「1」の2つの証明書情報がぶら下がっているのが見つかります(中間証明書がある場合は2とかにもなる)。

 0 s:C = US, ST = California, L = Mountain View, O = Google LLC, CN = smtp.gmail.com
   i:C = US, O = Google Trust Services, CN = GTS CA 1O1
 1 s:C = US, O = Google Trust Services, CN = GTS CA 1O1
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign

数字が大きいほうがルート証明書に近くなります。今回は「1」がルート証明書です。sはsubject(証明対象)でiはissuer(発行者)を意味します。ルート証明書の発行者がCA認証局なので、「GlobalSign」がCA認証局です。

ルート証明書「GlobalSign Root CA - R2」は、-----BEGIN CERTIFICATE----------END CERTIFICATE-----で囲まれたものが証明書になります。

 1 s:C = US, O = Google Trust Services, CN = GTS CA 1O1
   i:OU = GlobalSign Root CA - R2, O = GlobalSign, CN = GlobalSign
-----BEGIN CERTIFICATE-----
MIIESjCCAzKgAwIBAgINAeO0mqGNiqmBJWlQuDANBgkqhkiG9w0BAQsFADBMMSAw
HgYDVQQLExdHbG9iYWxTaWduIFJvb3QgQ0EgLSBSMjETMBEGA1UEChMKR2xvYmFs
U2lnbjETMBEGA1UEAxMKR2xvYmFsU2lnbjAeFw0xNzA2MTUwMDAwNDJaFw0yMTEy
MTUwMDAwNDJaMEIxCzAJBgNVBAYTAlVTMR4wHAYDVQQKExVHb29nbGUgVHJ1c3Qg
U2VydmljZXMxEzARBgNVBAMTCkdUUyBDQSAxTzEwggEiMA0GCSqGSIb3DQEBAQUA
A4IBDwAwggEKAoIBAQDQGM9F1IvN05zkQO9+tN1pIRvJzzyOTHW5DzEZhD2ePCnv
UA0Qk28FgICfKqC9EksC4T2fWBYk/jCfC3R3VZMdS/dN4ZKCEPZRrAzDsiKUDzRr
mBBJ5wudgzndIMYcLe/RGGFl5yODIKgjEv/SJH/UL+dEaltN11BmsK+eQmMF++Ac
xGNhr59qM/9il71I2dN8FGfcddwuaej4bXhp0LcQBbjxMcI7JP0aM3T4I+DsaxmK
FsbjzaTNC9uzpFlgOIg7rR25xoynUxv8vNmkq7zdPGHXkxWY7oG9j+JkRyBABk7X
rJfoucBZEqFJJSPk7XA0LKW0Y3z5oz2D0c1tJKwHAgMBAAGjggEzMIIBLzAOBgNV
HQ8BAf8EBAMCAYYwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsGAQUFBwMCMBIGA1Ud
EwEB/wQIMAYBAf8CAQAwHQYDVR0OBBYEFJjR+G4Q68+b7GCfGJAboOt9Cf0rMB8G
A1UdIwQYMBaAFJviB1dnHB7AagbeWbSaLd/cGYYuMDUGCCsGAQUFBwEBBCkwJzAl
BggrBgEFBQcwAYYZaHR0cDovL29jc3AucGtpLmdvb2cvZ3NyMjAyBgNVHR8EKzAp
MCegJaAjhiFodHRwOi8vY3JsLnBraS5nb29nL2dzcjIvZ3NyMi5jcmwwPwYDVR0g
BDgwNjA0BgZngQwBAgIwKjAoBggrBgEFBQcCARYcaHR0cHM6Ly9wa2kuZ29vZy9y
ZXBvc2l0b3J5LzANBgkqhkiG9w0BAQsFAAOCAQEAGoA+Nnn78y6pRjd9XlQWNa7H
TgiZ/r3RNGkmUmYHPQq6Scti9PEajvwRT2iWTHQr02fesqOqBY2ETUwgZQ+lltoN
FvhsO9tvBCOIazpswWC9aJ9xju4tWDQH8NVU6YZZ/XteDSGU9YzJqPjY8q3MDxrz
mqepBCf5o8mw/wJ4a2G6xzUr6Fb6T8McDO22PLRL6u3M4Tzs3A2M1j6bykJYi8wW
IRdAvKLWZu/axBVbzYmqmwkm5zLSDW5nIAJbELCQCZwMH56t2Dvqofxs6BBcCFIZ
USpxu6x6td0V7SvJCCosirSmIatj/9dSSVDQibet8q/7UK4v4ZUN80atnZz1yg==
-----END CERTIFICATE-----

ちなみにこの-----BEGIN CERTIFICATE----------END CERTIFICATE-----で囲まれた形式をPEM形式と呼びます(Base64エンコードされてる形式)。

証明書のエンコード形式の変換

おまけとして、PEM形式の証明書とDER形式の証明書の変換方法を記載します。

PEMからDERへ変換

PEM形式server.pem.crtを、DER形式server.der.crtに変換する。

> openssl x509 -inform PEM -in server.pem.crt -outform DER -out server.der.crt

DERからPEMへ変換

DER形式server.der.crtを、PEM形式server.pem.crtに変換する。

> openssl x509 -inform DER -in server.der.crt -outform PEM -out server.pem.crt

参考サイト

証明書フォーマットを変換する

OpenSSLの"Unrecognized flag modules" エラー

以下のようなエラーが出て小一時間溶かしました。

OpenSSL> rsa -noout -modules -in private.key
rsa: Unrecognized flag modules
rsa: Use -help for summary.
error in rsa
OpenSSL> req -noout -modules -in server.csr
req: Unrecognized flag modules
req: Use -help for summary.
OpenSSL> x509 -noout -modules -in server.crt
x509: Unrecognized flag modules
x509: Use -help for summary.
error in x509

もしかして:modulus

OpenSSL> rsa -noout -modulus -in private.key
Modulus=D33DDA42F3XXXX...XXXXD431587DC9
OpenSSL> req -noout -modulus -in server.csr
Modulus=D33DDA42F3XXXX...XXXXD431587DC9
OpenSSL> x509 -noout -modulus -in server.crt
Modulus=D33DDA42F3XXXX...XXXXD431587DC9

modulus(モジュラス)とは

RSAモジュラス - Wikipedia

OpenSSLの"problem creating object tsa_policy1=1.2.3.4.1" エラー

環境

現象

証明書署名要求(CSR)の確認をするコマンドを行うと、2回目以降で以下のようなエラーが発生しました。

# 初回実行はうまく動作する
OpenSSL> req -text -noout -in localhost.csr
Certificate Request:
    Data:
        Version: 1 (0x0)
        Subject: C = JP, ST = Kyoto, L = Sakyoku, O = hogehoge, CN = hogehoge.co.jp
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key: (256 bit)
                pub:
                    04:eb:95:8d:d6:fc:53:fe:e7:3e:d7:ed:64:14:11:
                    28:de:d2:3b:2f:4a:a5:6b:fc:61:b0:8e:d3:bf:38:
                    59:15:a6:f6:d3:2a:48:7f:35:4d:12:aa:95:6e:ed:
                    dc:3e:bb:1a:e5:de:13:59:77:75:09:10:89:c9:3f:
                    ac:08:18:7a:ec
                ASN1 OID: prime256v1
                NIST CURVE: P-256
        Attributes:
            a0:00
    Signature Algorithm: ecdsa-with-SHA256
         30:45:02:20:04:da:d9:e5:67:be:c3:51:42:2e:2d:6f:c1:0c:
         78:cd:79:90:33:e8:6d:79:6d:ba:f8:c8:d2:6f:47:50:65:29:
         02:21:00:bf:fa:4d:7b:51:83:67:ba:99:c1:ae:eb:6a:c1:9a:
         78:3a:6f:a8:6f:27:db:25:91:90:93:41:7b:f6:a2:85:8d
# 2回目以降は、全く同じコマンドを打ってもエラーが発生する。
OpenSSL> req -text -noout -in localhost.csr
problem creating object tsa_policy1=1.2.3.4.1
27948:error:08064066:object identifier routines:OBJ_create:oid exists:crypto\objects\obj_dat.c:698:
error in req

追記(2020/07/07)

以下のコマンドでも同現象が発生しました。

OpenSSL> req -noout -modulus -in server.csr
Modulus=D33DDA42...31587DC9
OpenSSL> req -noout -modulus -in server.csr
problem creating object tsa_policy1=1.2.3.4.1
10040:error:08064066:object identifier routines:OBJ_create:oid exists:crypto\objects\obj_dat.c:698:
error in req

やはりreqコマンド系で発生するようです。

直し方

本質的な直し方は不明です 笑。

いかがでしたか?(は?)

Ctrl-Cで一旦OpenSSLプロンプトから抜けると、とりあえず直ります。面倒くさいですが、こうする以外に私は方法を見つけれませんでした。

以下の参考URLのissueを追うと、「コマンド実行する際にライブラリコンテクストを作成し、コマンド終了時にそれをクリーンアップするのだけれど、そのクリーンアップがうまく行ってないとかなんとか」みたいに書いてありました。

よくわからないのでバグ修正待ちです。

参考

OpenSSLv1.1.0e CSR verification error, problem creating object tsa_policy1=1.2.3.4.1 · Issue #2795 · openssl/openssl