n度あることはn+1度ある

憶測が多いブログなので鵜呑みにしないこと

ABC104 C - All Green

久しぶりに問題を解いていたら、C問の中でも個人的に骨が折れた問題があったのでメモ
ボーナス点という要素がなければ欲張り法で解ける問題ですが、これの所為で他の解説者の方の言う通り、2nの全解探索が必要です。
最高で1024通りを試しますが、対象の問題のビットが立っている時、問題数*問題点+ボーナス点を加算し、目標点数Gに届いていなければ、欲張り法で残りの必要点数を加算していきます。
最下位ビットが立っているときは、2で割る時余りが1になるので、ビットはループ回数の2の剰余で求めます。
ビットのたった問題は全て解いたと仮定するので、vectorでチェックしていて、問題が全て解かれているものを除き、点数の高い問題から残りの必要点数を加算していきます。
この時、1つの問題に就き問題数全てを加算すると、上記の前提が外れるので最高でも問題点*(問題数-1)しか加算しません。
単なる2nの探索のみならず、様々な要素が組み合わさっているので個人的には難しかったです。

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
    int d,g;
    cin >> d >> g;
    vector<int> p(d),c(d);
    for(int i = 0; i < d; i++)
        cin >> p[i] >> c[i];
        
    int loop = pow(2,d);
    int min = 10000;
    for(int i = 0; i <= loop-1; i++){
        int t = i,tg = g;
        vector<int> check(d,0);
        int j=0,count=0;
        while(t != 0){
            if(t%2 == 1){
                tg -= p[j]*(j+1)*100+c[j];
                count += p[j];
                check[j] = 1;
            }
            t /= 2;
            j++;
        }
        for(j = d-1; j >= 0; j--){
            if(tg <= 0)
                break;
            if(check[j] == 0){
                for(int k = 0; k < p[j]-1 && tg > 0; k++){
                    tg -= (j+1)*100;
                    count++;
                }
            }
        }
        if(count < min && tg <= 0)
            min = count;
    }
    cout << min;
}

参考:

AtCoder Beginner Contest 104 C - All Green (300 点) - けんちょんの競プロ精進記録

ABC104 参加記録 - ARMERIA

OpenCVでステガノグラフィの実験をしてみる

今までだ・である調を使ってブログを書いてきたが、普通に書きにくいので以下よりです・ます調でブログを書いていく。
以上蛇足

OpenCVを使って、画像に画像を埋め込むステガノグラフィ的なことをしてみました。

埋め込み対象画像

hidden.bmp f:id:benntann:20180714014405j:plain

埋め込む画像

hide.bmp f:id:benntann:20180714014441j:plain

ステグした画像

output.bmp f:id:benntann:20180714014707j:plain

ぱっと見はそこまで変わりませんが、ステグした画像の背景をよく見ると、「ステ」の文字が薄っすらと見えます。記載している復号用のプログラムを使用すれば、hide.bmpが取り出せます。
アルゴリズムとしては、埋め込む画像の1つの画素のRGB情報を、2bitずつにして埋め込み先の画像の下位2bitに設定して実現しています。つまり1つの画素情報を4つの画素に分けて保存しています。こんな単純なアルゴリズムでも、殆ど変わりがないレベルなので、実際に使用されているアルゴリズムで作られた画像は、バイナリエディタなどで数値的に観ない限りわからないレベルなのでしょうか。
猫の画像はフリー画像です。

以下ソースコード
※埋め込みは400*100 -> 400*400、取り出しは400*100 <- 400*400のみ対応

steg.cc

#include "opencv2/highgui.hpp"
int main(){
  cv::Mat hidden,hide;
  cv::Vec3b *hidesrc,*hiddensrc;
  int i,j,k;
  int shift;
  int offset;
    hidden = cv::imread("hidden.bmp", 1);
    hide = cv::imread("hide.bmp", 1);
    
    if( hide.data == NULL || hidden.data == NULL) return -1;

    for(i = 0; i < 400; i++){
      hidesrc = hide.ptr<cv::Vec3b>(i);
      hiddensrc = hidden.ptr<cv::Vec3b>(i);

      for(j = 0; j < 100; j++){
    int shift = 0b11;
    for(k =0; k < 4; k++){
      //shiftdown for steg space
      offset = j*4+k;
      hiddensrc[offset][0] >>= 2;
      hiddensrc[offset][1] >>= 2;
      hiddensrc[offset][2] >>= 2;

      //assert info of hide img
      hiddensrc[offset][0] = (hiddensrc[offset][0] << 2) | ((hidesrc[j][0] & shift) >> (2*k));
      hiddensrc[offset][1] = (hiddensrc[offset][1] << 2) | ((hidesrc[j][1] & shift) >> (2*k));
      hiddensrc[offset][2] = (hiddensrc[offset][2] << 2) | ((hidesrc[j][2] & shift) >> (2*k));
      shift = shift << 2;
    }
      }
    }
    cv::imwrite("output.bmp", hidden);
    return 0;
}

dec.cc

#include "opencv2/highgui.hpp"
int main(){
  cv::Mat steged = cv::imread("output.bmp", 1);
  cv::Mat dec  = cv::Mat::zeros(400,100,CV_8UC3);
  cv::Vec3b *ssrc,*dsrc;
  int i,j,k;

  if( steged.data == NULL || dec.data == NULL) return -1;
  for(i = 0; i < 400; i++){
    ssrc = steged.ptr<cv::Vec3b>(i);
    dsrc = dec.ptr<cv::Vec3b>(i);
    for(j =0; j < 100; j++){
      for(k = 0; k < 4; k++){
    dsrc[j][0] += ((ssrc[j*4+k][0] & 3) << (2*k));
    dsrc[j][1] += ((ssrc[j*4+k][1] & 3) << (2*k));
    dsrc[j][2] += ((ssrc[j*4+k][2] & 3) << (2*k));
      }
    }
  }
  cv::imwrite("dec.bmp",dec);
  return 0;
}

珍しい(?)ギター・ベースの練習環境

楽器 →(シールド)→ AudioBox 22VSL →(モノラル→AUX)→ HD-DAC1 → ヘッドフォン
みたいな感じで今現在練習している。
AudioBoxのつまみは小っさいのと、ヘッドフォンが今1つしかないのでジャックの抜き差ししたくないからこのような形になった。 ジャックの抜き差し以外だと、ボリューム調整が1つだけでいいのが個人的に利点。
こんな変な構成でやってる人は自分だけだと思う。

HD-DAC1の入力をUSBから光デジタルにした

入力が無いときにリレーが切り替わるとノイズが聞こえるレベルで発生し、電源を切ってもなっていたので光デジタルにした。 光デジタルにしたところ、今の所可聴レベルのノイズは発生していない。またSPDIF端子は音がなっていなくても、出力しっぱなしなようでリレー音の切り替えがなくなり選曲時のストレスもなくなった。
音質の違いはよく分からないが、HD-DAC1の主なストレスは消えたので良かった。

マザボの光出力だとHD-DAC1から音が出ないときの解決策

症状

マザボのSPDIF出力からHD-DAC1に出力してもUNSUPPORTと表示される

原因

realtekの5.1chに非対応(ヘッドフォン用のDACだから当たり前?)

解決策

コンパネのサウンドから出力形式を2chにする f:id:benntann:20180326174459p:plain

折り畳み傘のススメ

折り畳み傘を購入して半年くらい経ったが、とても素晴らしいので是非様々な人に使ってほしいという記事

折り畳み傘の良い点

傘の盗難・忘れを防止できる

ビニール傘を盗まれたり、帰り際晴れていて傘を置き忘れたという経験は無いだろうか。
折り畳み傘は基本的に傘置き場に置くという行動を必要としないため、傘の盗難・置き忘れを防止できる。

邪魔にならない

傘を持って歩くという行為は、手が塞がり場合によっては非常に邪魔な場合がある。しかし、折り畳み傘は鞄の中に突っ込んでおけばいいだけなので邪魔だということは基本的にない。

突発的な雨に対応できる

鞄の中に常に入れておけば、急に天気が変わったときでも対応ができる。

折り畳み傘の悪い点

鞄を専有する

当たり前だが、鞄の中に入れっぱなしにしておけばその鞄の容量を常に圧迫する状態となる。大きめの鞄や、折り畳み傘を入れるスペースなどがあれば問題ないが小さめの鞄を持ち歩く人にとっては大いに邪魔になる。

収納がめんどくさい

鞄から折り畳み傘を出し、ケースから傘本体を出すという行程が追加されるため傘をさす、しまうという動作が通常の傘と比べて、めんどくさくなる。

折り畳み傘への予想される懸念

壊れやすい

百均のものではなく少し高めの傘を買えば、すぐに壊れるということは無いと思われる。
Crayon Palmeの傘を使用しているが、現在まで特に問題はない。

髪の毛を巻き込む

これも一定水準以上の折り畳み傘ならば問題ないと思われる。

収納時、鞄などに水滴がつく

一緒についてくる折り畳み傘を入れるケースだと防水性がなく、傘に付着した水滴がそこら中に散乱するため、以下のようなケースを一緒に購入するとこのような事態を防げる。

傘が小さい

自分が使用してる傘なら展開時、コンビニで販売してるビニール傘くらいのサイズはある。展開時のサイズは通常商品ページに記載されているので、購入時に確認すれば良い。120cmくらいあれば十分かと。

基本的に収納がめんどくさいこと以外は、普通の傘より便利だと思っているので購入を検討してはどうだろうか。

Ubuntuでユーザー切り替えがうまくいかないときに

症状

新規に作成したユーザーでUbuntuにログインしようとすると、ログインGUIから移り変わらない

原因

ユーザーのホームディレクトリが作成されていない

解決策

adduserコマンドで作り直すなどホームディレクトリを作る

参考

qiita.com