メンズワキガ対策専門ブランドD AGICA【ディーアジカ】

 

■Arduino CPUファン (PWM)を回してみた

体調があまり良くなくて、競技プログラミングのある問題のアルゴリズムを考えつつ、ぼんやりする日が続いてます。しかし、暑い。でもエアコンが寒い。そんな感じ。で、ファンを回してみようと思った。なんだかな〜 (^_^;)

 

使っていない CPU 冷却ファンがあったので、これを回してみましょう。

 

ファンから出ている線は 4 芯です。ググってみると、4 芯のものは PWM で回転数制御ができるんだとか。電源に 12V を与えておき、control に 25KHz の PWM 信号を入れてやるとそのデューティー比によって回転数が変化する。また、sense には 1 回転あたり 2 パルス (デューティー比 50%) の信号がオープンコレクタで出てくる。らしい。

このファン自体の仕様はわからなかったのですが、汎用品のようですのでたぶん同じでしょう。

 

ということで、回路図。Arduino Nano 互換品を使いました。


画像キャプション

 

ジャンクのサーミスタがあったので、これで温度を検出し回転数を制御することにします。

このサーミスタはレーザープリンタの定着部の部品で 200℃ 程度の計測がベストなんですけど、まぁテキトーに使いましょ。この定数での入力値は、約 26℃ で 830 、約 32℃ で 780 ぐらいになりました。 

 

Arduino の Vin に 12V を入れていますが、USB をつないだまま 12V を落としたときに 5V が逆流するのを防ぐためにダイオードを入れています。実験中は電源を切ることがよくありますのでね。

 

control は 3.3V 推奨なので、ツェナーダイオードで降圧しています。

control の電流の実測値は吐き出しで約 0.6mA でした。Arduino の 3 番ピンが HIGH (5V) のとき、ツェナーダイオードには R2 を介して約 11mA 流れ、control 側の HIGH レベルは 3.3V になります。3 番ピンが LOW (0V) のとき R2 の電圧降下は 0.09V ですので、control 側は問題なく LOW レベルに落ちます。

 

sense はオープンコレクタなのでプルアップしています。内部プルアップでも構わないのですが、プルアップを明示的にするために抵抗を入れることにしています。まぁ好みです。

 

さて、問題の PWM ですが、Arduino の PWM は 490Hz か 980Hz ですのでこのままでは使えません。そこで Arduino で 25KHz PWM を作る方法をググってみると、けっこうたくさんヒットします。なるほどっポンと膝を叩いた、参考にさせていただいたサイトはこちらです。ありがとうございます。

 

趣味関係のメモ帳

Arduinoで遊ぶページ

 

そしてできあがったスケッチは以下。

 

/*  FAN Controller   2019.08.15 meyon
 *   
 *  Timer2 Mode5 PhaseCorrect PWM
 *  Clock 16MHz / 8 = 2MHz
 *  PWM countuency 25KHz
 *  OCR2A = 2MHz / 25KHz / 2 = 40
 *  OCR2B = dutyRatio ratio 0 ~ 40
 *  PWM output PD3
 */

 

volatile long riseTime = millis();
volatile long prevTime = millis();

 

void setup() 
{
  pinMode(3, OUTPUT);
  TCCR2A = _BV(COM2B1) | _BV(WGM20);
  TCCR2B = _BV(WGM22)  | _BV(CS21);
  OCR2A = 40;
  OCR2B = 0;

 

  pinMode(2, INPUT);
  attachInterrupt(digitalPinToInterrupt(2), sense, RISING);

 

  Serial.begin(115200);
}

 

void loop() 
{
  static const int thermMax = 780;
  static const int thermMin = 830;
  static const float gradients = 40.0/(thermMax-thermMin);

 

  int thermValue = analogRead(A0);
  float dutyRatio = (thermValue-thermMin)*gradients;

  if (0>dutyRatio) {
    dutyRatio=0;
  } else if (40<dutyRatio) {
    dutyRatio=40;
  }

 

  OCR2B = (int)dutyRatio;


  long cycle=riseTime-prevTime;
  long rpm=30000/cycle;
  if (100<millis()-riseTime) {
    rpm=0;
  }

 

// data monitor
  Serial.print(thermValue);
  Serial.print("¥t");
  Serial.print(dutyRatio);
  Serial.print("¥t");
  Serial.print(rpm);
  Serial.print("¥n");

}

 

void sense()
{
  prevTime=riseTime;
  riseTime=millis();
}

 

setup() のなかで PWM の動作を規定しています。

WGM20 、WGM22 をセットすることで Mode 5「PWM Phase Correct」になります。COM2B1 はデジタルピン 3 番の PWM 出力を規定します。CS21 は分周比を 8 としています。OCR2A で TOP を 40 にすることで、出力周波数が 16000 / ( 8 * 40 * 2 ) = 25KHz になります。

 

OCR2B は 3 番ピンの比較レジスタで、これを 0 〜 40 にすることでデューティー比 0 〜 100% の PWM を発生させることができます。

サーミスタ入力を 830 〜 780 とし、その範囲でデューティー比を 0 〜 40 (0 〜 100%) として OCR2B を設定します。

 

2 番ピンは sense を入力し、パルスの立ち上がりで関数 sense() を呼び出しています。これによりパルスの周期を計測して回転数を算出しますが、100msを超えて割り込みが無いときは回転数を 0 としています。

 

ちなみに、ビットアクセスマクロ _BV() は、指定したビットをセットし、他をクリアします。| でつなぐことで複数ビットをセットしています。

指定したビットのみセットするには、たとえば DDRD |= _BV(PD3) のようにします。これは DDRD = DDRD | _BV(PD3) ということですね。PD3 のビットのみセットし、他は変更しません。 指定したビットのみクリアするには DDRD &= ~_BV(PD3) とします。DDRD = DDRD & ~_BV(PD3) ということです。

 


■競技プログラミング AtCoder Beginner Contest 133 D 問題 合格の巻

AtCoder Beginner Contest 133 D 問題  Rain Flows into Dams を解いてみましたが、TLE (実行時間制限超過) となって不合格でした。

 

余談ですが、いろいろ数値を入力して確認しているときに、答えが負数になる場合がでてきました。確認のために AC の方のプログラムを実行してみたところ、やっぱり負数になります。うーん、マイナスの雨が降るなんてありえない話じゃ ……

考えること小一時間 (^_^;) 問題文の制約に次の一文を見つけました。

 

入力が表す状況は、各山に非負の偶数リットルの雨が降った際に発生しうる。

 

わかりにくい文ですが、つまり「答えが負数になるような入力は与えませんよ」ってことなんでしょう。ということで、それは気にする必要はないのだと判断しました。

 

閑話休題

 

結果が TLE になったということは計算量が多すぎるってこと。解決策を求めて解説をみてみることにします。ん〜と… そうか、漸化式をそのまま順番に計算していけば O(n) にできるんだ。なるほど (^_^;)

 

では解説を参考にして、もう一度考えなおしてみましょう。

 

前回と同じく山は 5 個とします。降雨量の総量を S とすると、

 

S = A1 + A2 + A3 + A4 + A5 = X1 + X2 + X3 + X4 + X5

X1 = S - ( X2 + X3 + X4 + X5 )

 

X2 + X3 = 2 × A2 、X4 + X5 = 2 × A4 ですから、

 

X1 = S - 2 × ( A2 + A4 )

 

これでまず X1 が求まりました。あとは、

 

X2 = 2 × A1 - X1

X3 = 2 × A2 - X2

X4 = 2 × A3 - X3

X5 = 2 × A4 - X4

 

と順番に計算していけばよいです。このような前の式によって定まる式を「漸化式」というそうです。漸化式をそのまま順番に計算していくことで全体の計算量を減らせるなんて、考えが及びませんでした。

 

ということで、計算部分を改善してみました。太字が変更した部分です。

 

/*  AtCoder Beginner Contest 133 D - Rain Flows into Dams
    2019.07.28 by meyon */

 

#include <stdio.h>
#include <stdlib.h>

 

void err()
{
  printf("Error!¥n");
  exit(1);
}

 

int main()
{
  // input N
  int N;
  scanf("%d", &N);
  if(3>N || 99999<N || 0==N%2) {
    err();
  }

 

  // input A
  int A[N];
  for(int i=0; i<N; i++) {
    scanf("%d", &A[i]);
    if(0>A[i] || 1000000000<A[i]) {
      err();
    }
  }

 

  // rainfall X
  int X[N];
  for(int i=0; i<N; i++) {
    X[i]=0;
  }

 

  int S=0;
  for(int i=0; i<N; i++) {
    S += A[i];
  }
  int P=0;
  for(int i=1; i<N; i+=2) {
    P += A[i];
  }
  X[0]=S-2*P;   // X1=S-2(A2+A4+...+A[n-1])

 

  for(int i=0; i<N-1; i++) {
    X[i+1]=2*A[i]-X[i];   // X[i+1]=2Ai-Xi

  }

 

  // display answer
  for(int i=0; i<N; i++) {
    printf("%d ", X[i]);
  }
  printf("¥n");

  return 0;
}

 

入力して、範囲外の場合はエラー終了。ここは毎度同じです。

改善した rainfall X の部分。

 

  1. 配列変数 X[N] を宣言して初期化
  2. 総降雨量 S = A1 + A2 + ... + A5 を計算
  3. X1 の算出のために P = (A2 + A4) を計算
  4. X1 = S - 2 × P で X1 を求める
  5. X2 = 2 × A1 - X1 を求め、繰返し X3、X4、X5 を算出

 

といった感じです。

はい、これで AC (合格) となりました \(^o^)/ 実行時間は 23ms 、メモリ 2048KB でした。

 


■競技プログラミング AtCoder Beginner Contest 133 D 問題 不合格の巻

面白がって過去問題を解いているうちに、なんと D 問題まできてしまいました。

AtCoder Beginner Contest 133 D 問題 は Rain Flows into Dams です。

 

問題文

円形に  N 個の山が連なっており、時計回りに山  1 , 山  2 …… , 山  N  と呼ばれます。 N 奇数です。

これらの山の間に  N  個のダムがあり、ダム  1 , ダム  2 …… , ダム  N  と呼ばれます。ダム  i  ( 1≤i≤N ) は山  i  と山  i+1  の間にあります (山  N+1  は山  1  のことを指します)。

山  i  ( 1≤i≤N ) に  2x  リットルの雨が降ると、ダム  i−1  とダム  i にそれぞれ  x リットルずつ水が溜まります (ダム  0 はダム  N のことを指します)。

ある日、各山に非負の偶数リットルの雨が降りました。

その結果、ダム  i ( 1≤i≤N ) には合計で  Ai リットルの水が溜まりました。

各山に降った雨の量を求めてください。この問題の制約下では解が一意に定まることが証明できます。

 

さて頭が痛くなりそうですが (^_^;) まずは問題を理解しなければなりません。紙に山とダム (谷) を描いて考えてみましょう。

山が 3 個あるとします。ダム 1 の左が山 1 、右が山 2 です。ダム 1 に溜まった水 A1 は、山 1 と山 2 に降った雨 X1、X2 の半分です。

 

A1 = ( X1 + X2 ) ÷ 2

 

したがって山 1 に降った雨 X1 は、

 

X1 = 2 × A1 - X2

 

となります。同様にそれぞれの山に降った雨は、

 

X2 = 2 × A2 - X3

X3 = 2 × A3 - X1

 

です。ということで、それぞれの式を代入して X を求めると、

 

X1 = A1 - A2 + A3

X2 = A2 - A3 + A1

X3 = A3 - A1 + A2

 

となりました。

山が 5 個の場合はどうでしょう。同様に考えていくと

 

X1 = A1 - A2 + A3 - A4 + A5

X2 = A2 - A3 + A4 - A5 + A1

X3 = A3 - A4 + A5 - A1 + A2

X4 = A4 - A5 + A1 - A2 + A3

X5 = A5 - A1 + A2 - A3 + A4

 

となります。

さてプログラムですが、この式をどうしましょうか。

 

for ( i = 0 ; i < N ; i++ ) {

  for ( j = i ; j < N+i ; j++ ) { 

    A[ j%N ];

 

って感じでループすれば、

 

A[0] A[1] A[2] A[3] A[4]

A[1] A[2] A[3] A[4] A[0]

A[2] A[3] A[4] A[0] A[1]

A[3] A[4] A[0] A[1] A[2]

A[4] A[0] A[1] A[2] A[3]

 

という数列が作れます。あとは符号を反転しては加算していく、と。うん、できそうですね。

 

ということで、

 

  1. 山の数 N を入力
  2. ダムの水量 A を入力
  3. 降雨量 X を計算
  4. すべての山に対して繰返し
  5. 結果を表示

 

という流れでプログラムを書いてみました。

 

/*  AtCoder Beginner Contest 133 D - Rain Flows into Dams
    2019.07.26 by meyon */

 

#include <stdio.h>
#include <stdlib.h>

 

void err()
{
  printf("Error!¥n");
  exit(1);
}

 

int main()
{
  // input N
  int N;
  scanf("%d", &N);
  if(3>N || 99999<N || 0==N%2) {
    err();
  }

 

  // input A
  int A[N];
  for(int i=0; i<N; i++) {
    scanf("%d", &A[i]);
    if(0>A[i] || 1000000000<A[i]) {
      err();
    }
  }

 

  // rainfall X
  int X[N];
  for(int i=0; i<N; i++) {
    X[i]=0;
  }
  for(int i=0; i<N; i++) {
    int s=-1;
    for(int j=i; j<N+i; j++) {
      int amou=A[j%N];
      s=-s;
      X[i] += s*amou;
    }
  }

 

  // display answer
  for(int i=0; i<N; i++) {
    printf("%d ", X[i]);
  }
  printf("¥n");

 

  return 0;
}

 

さぁ提出してみましょう。…… あれ? … あー、TLE (実行時間制限超過) になってしまいました (*_*;)

 


■競技プログラミング AtCoder Beginner Contest 133 C 問題

さらに続けてみましょう。

競技プログラミング AtCoder Beginner Contest 133 C - Remainder Minimization 2019 を解いてみます。

 

問題文

非負整数  L,R  が与えられます。 つの整数  i,j  を  L≤i<j≤R  を満たすように選びます。  (i×j) mod 2019  の最小値を求めてください。

 

これは難しくないですよ。 L から R までのすべての組み合わせを計算して余りを出せば良いです。すべての組み合わせを計算するというのは、前にやった B 問題で学んだことですね。

でも単純に総当たりするのは芸がありません。ある数を 2019 で割った余り m は 0 ≦ m ≦ 2018 ですから、0 が出たらそこで終了、答えは 0 です。0 が出なかったら答えは 2018 以下の最も小さな数になりますね。最も小さな数を抽出するのは A 問題でもやりました。

 

では、以下の流れでプログラムを書いてみましょう。

 

  1. 数値 L R を入力
  2. 範囲外なら Error! を表示してエラー終了
  3. 二つの整数の積を 2019 で割った余りを計算
  4. 余りの最小値を更新
  5. 余りが 0 ならば計算を終了し 7. へ
  6. すべての組み合わせで繰り返し
  7. 余りの最小値を表示

 

プログラム自体は簡単です。チャチャっと書いて入力例を試してみると、うまくいきました。

えらい簡単だったなぁ。でもまぁとりあえずいろんな数値入れて試してみよう。と、大きめの数も入れて確認していくと、500000 あたりからおかしな答えが出てきて、1000000 超えると負数になっちゃった (^_^;)

あれ〜、オーバーフローしちゃったのか〜

 

与える数の最大値が 2×109 だったので int 型でいけるよねぇ〜と考えていたのですが、余りの計算式を

 

remain = i * j % 2019

 

としたために、ここでオーバーフローしてしまったようです。計算の最大値は 4×1018 になりますから long long int 型にしなければいけません。

うーん、int 型でオーバーフローしないような計算方法はないのかなぁ〜 と、アルゴリズムを考え直してみるのは B 問題で学んだことです。

 

考えること小一時間 (^_^;) あった!合同式です。

 

合同式 a ≡ b ( mod n )         a を n で割った余りは b 

 

合同式の掛け算は

 

a ≡ c ( mod n ) 、b ≡ d ( mod n ) のとき、a × b ≡ c × d ( mod n )

 

となります。つまり、「2つの数の積 a × b を n で割った余りは、a、bをそれぞれ n で割った余りの積 c × d と同じ」ということ。このことから前出の計算式は次のようにできます。

 

remain = ( i % 2019 ) * ( j % 2019 ) % 2019

 

これで最大値は 2×109 に抑えられますから int 型で計算できるようになりました。

なお、合同式については「合同式の証明や問題の解き方を解説!大学受験で使いこなそう!」を参考にさせていただきました。

 

ということで、できあがったプログラムです。

 

/*  AtCoder Beginner Contest 133 C - Remainder Minimization 2019
    2019.07.25 by meyon */

 

#include <stdio.h>

 

int main()
{
  // input date
  int L, R;
  scanf("%d %d", &L, &R);
  if (0>L || L>=R || 2000000000<R) {
    printf("Error!¥n");
    return 1;
  }

 

  // modulo
  int ans=2018;
  for (int i=L; i<R; i++) {
    for (int j=i+1; j<=R; j++) {
      int remain=(i%2019)*(j%2019)%2019;
      if(ans>remain) {
        ans=remain;
      }
      if (0==ans) {
        i=R;
        j=R+1;    // end of modulo
      }
    }
  }

 

  // answer
  printf("%d¥n", ans);

  return 0;
}

 

余りが 0 になったときに二重のループを一気に抜けて計算を終了させるのは、条件式が偽になるような値を代入する方法をとっています。break では一つのループしか抜けられません。

 

今回はなかなか良い感じだろうと自画自賛してますが、提出はやっぱりドキドキしますね (^_^;)

 


■競技プログラミング AtCoder Beginner Contest 133 B問題 その3

AtCoder Beginner Contest 133 の B 問題「Good Distance」のプログラムを書いてみました。

 

/*  AtCoder Beginner Contest 133 B - Good Distance
    2019.07.25 by meyon  */

 

#include <stdio.h>
#include <stdlib.h>

 

void err()
{
  printf("Error!¥n");
  exit(1);
}

 

int main()
{
  // input N:point and D:dimension
  int N, D;
  scanf("%d %d", &N, &D);
  if(N<2 || N>10 || D<1 || D>10) {
    err();
  }

 

  // input X:coordinates
  int X[N][D];
  for(int i=0; i<N; i++) {
    for(int j=0; j<D; j++) {
      scanf("%d", &X[i][j]);
      if(X[i][j] < -20 || X[i][j] > 20) {
        err();
      }
    }
  }

 

  // calculate norm
  int ans=0;
  for(int i=0; i<N-1; i++) {
    for(int j=i+1; j<N; j++) {
      int norm=0;
      for(int k=0; k<D; k++) {
        int diff = X[i][k] - X[j][k];
        norm += diff * diff;
      }

 

      // check norm whether integer
      int flag=0;
      for(int k=0; k*k <= norm; k++) {
        if(k*k == norm) {
          flag=1;
        }
      }
      if(flag) {
        ans++;
      }
    }
  }

 

  // display answer
  printf("%d¥n", ans);

 

  return 0;
}

 

err() 関数は Error! を表示してプログラムをエラー終了します。exit() を利用するために stdlib.h をインクルードしています。

点の数 N と次元数 D を入力したら、その数で座標の配列変数を定義します。for 文で座標データを入力します。

calculate norm と check norm whether integer の部分は解説の実装例を参考にしました。ループの条件式がちょっと異なっているのと、差分の絶対値とはせずそのまま差をだしているところが相違点です。

ちなみに diff は差分、norm はベクトルの距離みたいな意味ですね。

実装例のように flag を boolean 型にするには別のヘッダファイルが必要になります。まぁ int 型でも問題ないかなと。

 

提出した結果、AC をいただきました。

今回はちょっと難しかったですけど、考え方さえ分かればなんとかなりそうですよね。たくさん勉強させていただきました。

 


■競技プログラミング AtCoder Beginner Contest 133 B問題 その2

AtCoder Beginner Contest 133 B - Good Distance を考えています。問題は理解できたので、次はプログラムを考えてみようと思います。

 

流れとしては、

 

  1.  点の数、次元の数を入力
  2.  座標データを入力
  3.  Yij を計算
  4.  k2==Yij かどうかを判定
  5.  3. 4. をすべての点間で繰り返す
  6.  4. が真だった数を出力として表示

 

といった感じですが、俺にはどうすればよいのかわからない部分があります。

一つは「3. Yij を計算」について。次元の数 D によって計算する項目数が変わってきます。D によって式を変化させるにはどうすればよいのでしょうか。もう一つは「5. すべての点間で繰り返す」です。漠然と「for 文を使って N、D の数だけ繰り返す」というイメージを浮かべますが、具体的な方法に考えが進みません。

 

今の俺の実力は「考えて悩むよりも真似してみよう」レベル (^_^;) 幸い解説に C++ の実装例がありましたので、これを参考にしてみましょう。

実装例で計算を行なっている部分は以下です。なるほど!と思ったのは太字の部分、( ) を計算し二乗して加算代入していくというところです。これで二つの疑問点は一気に解決できそうです。

 

for (int i = 0; i < N; ++i) {

for (int j = i+1; j < N; ++j) {

  int norm = 0;

  for (int k = 0; k < D; ++k) {

    int diff = abs(X[i][k] - X[j][k]);

    norm += diff * diff;

  }

 

では、入力例 2 の N=3、D=4 の場合で考えてみましょう。

座標は、

 

        1 番目の点 (X00 X01 X02 X03)

        2 番目の点 (X10 X11 X12 X13)

        3 番目の点 (X20 X21 X22 X23)

 

で、配列変数 X[N][D] に格納されています。

最初に 1 番目の点と 2 番目の点の距離の二乗 Y01 を求めます。

 

Y01 =(X00-X10)2+(X01-x11)2+(X02-X12)2+(X03-X13)2

 

次に 1 番目の点と 3 番目の点の距離の二乗 Y02 を求めます。

 

Y02 =(X00-X20)2+(X01-x21)2+(X02-X22)2+(X03-X23)2

 

最後は 2 番目の点と 3番目の点の間です。

 

Y12 =(X10-X20)2+(X11-x21)2+(X12-X22)2+(X13-X23)2

 

これですべての点の間の計算は終わりです。

X[i][k]-X[j][k] とすると、

 

for (i=0; i<N-1; i++) {

  for (j=i+1; j<N; j++) {

    for (k=0; k<D; k++) {

      X[i][k] - X[j][k]

 

といったループを作ればよいことがわかります。

ちなみに、N=10 とすると必要な計算式は、i=0 のときに 9 個、i=1 のときに 8 個、……、i=8 のときに 1 個の計 45 個 (10C2=45) となります。実装例では i=9 までループしますが、次の j のループが偽となって終了するので、結果は変わりません。ループが 1 回空振りするだけですね。

なお、実装例では差分の絶対値をとっていますが、どうせ二乗するのですから不必要だと考えています。

 

さぁて、ようやくアルゴリズムも理解できたので、次回こそプログラムを書いてみることにしましょう。

 


■競技プログラミング AtCoder Beginner Contest 133 B問題 その1

調子に乗った meyon さんはさらに挑戦してみました (^_^;)

AtCoder Beginner Contest 133 の B 問題「Good Distance」です。

 

画像キャプション

 

この問題はピンときました。座標上の 2点の間の距離を求めるのですから、いわゆる三平方の定理ってやつですね。

多次元の場合については俺は知らなかったのですが、問題に示された公式で適用できるのでしょう。基本的な考え方は三平方の定理も同じなんだろうなと想像できます。

 

例 1 を見てみましょう。

N=3 、D=2 ですから、平面 (二次元空間) 上に 3 個の点があるということです。ごく普通に三平方の定理で考えればいいですね。

たとえば 1 番目の点 (1,2) から 2 番目の点 (5,5) までの距離は √( (5-1)+ (5-2)) です。 え〜と式の表示が変ですけど、笑ってこらえてやってください (^_^;)

 

さて、次にこの式の値が整数かどうかを判定しないといけませんが、えーと、どうしましょう? 思いついたのは以下のようなものです。

 

  1. 小数部分を取り出して、それが 0 かどうか。0 なら整数です。
  2. 小数点以下を切り捨てて、それが元の値と同じかどうか。同じなら整数です。

 

でもなんだかねぇ、なぜだかいまいちすっきりしないんですよ…

迷ったのでちょっと解説をカンニングしてみました。すると

 

k2=Yij を満たす k が存在するかを調べれば √ Yij が整数であることを判定できます。

 

とあります。

そうか、平方根というムズムズするような値を判定するんじゃなくて、整数 k を二乗した値が (5-1)2+(5-2)2 と等しいかどうかを調べればよいのですね。それならすべての変数を int 型で扱えます。

ポン、なるほど、目から鱗のアルゴリズム (^_^;)

 

例 2 はどうでしょうか。

N=3 、D=4 ですから四次元空間上に 3 個の点が存在します。四次元空間…… う〜ん、四次元空間を想像することはできませんが、公式に当てはめて計算するだけのことです。

1 番目の点から 2 番目の点までの距離は、

 

Y12=(-3+12)2+(7-1)2+(10-8)2+(2-2)2=121

 

121 は 112 なので真 (整数) です。

2 番目と 3 番目の間は 、

 

Y23=(-2+12)2+(8-1)2+(10-9)2+(3-2)2=151

 

151 は 122 と 132 の間なので偽 (整数ではない) です。

同様に 1 番目と 3 番目の間は、

 

Y31=(-2+3)2+(8-7)2+(9-8)2+(3-2)2=4

 

これは 22 ですから真です。

したがって真が 2 つでしたから、出力は 2 となります。

 

例 3 は直線 (一次元空間) 上に 5 個の点があります。座標はすべて整数ですから、これらの点の間の距離は、計算するまでもなく整数であるとわかります。でも、プログラムでは何次元でも同じように処理できなければなりませんので、公式に当てはめてみましょう。

1 番目と 2 番目の間は Y12=(2-1)2=12 で真です。2 番目と 4 番目の間も Y24=(4-2)2=22 で真です。3 番目と 5 番目の間も Y35=(5-3)2=22 で真です。他の組み合わせもすべて同じく真になります。組み合わせの数は 10  ( 5C2 ) です。

 

さて、これで問題が理解できましたので、次回はプログラムを考えてみることにします。

 


■競技プログラミング AtCoder Beginner Contest 133 A問題

めげてないで努力してみましょう。

コンテストをよく見てみると「AtCoder Beginner Contest」というのがありました。先日飛びついたのは「AtCoder Grand Contest」でしたので、そりゃ難しいに決まってます (^_^;)

 

AtCoder Beginner Contest 133 の A 問題「T or T」です。

 

問題文
私たちは N 人で旅行しようとしており、その交通手段として電車とタクシーがあります。

電車を使うと 1 人あたり A 円かかります。

タクシーを使うと N 人で B 円かかります。

全員の交通費の合計は最小でいくらになるでしょうか。

 

なんか算数の問題っぽくってよさげなんですが、またしても問題の意味がわからない。「全員の交通費の合計は最小でいくらになるでしょうか」ってどーゆーこと?

 

例 1 を見てみましょう。人数 N が 4 人、電車 A が 2 円でタクシー B が 9 円とすると、電車が 4 人× 2 円で 8 円、タクシーが 4 人で 9 円ですから、全員の交通費の合計の最小値は 8 円、だそうです。や、安すぎる (^_^;)

えーとつまり、「交通費が安くなる交通手段はどっちか」ってことか。20 人いたらタクシーだと 5 台必要だから… なんてこと考えなくていいのね?

うぅ、なんかあまりに現実離れしていて頭がついていかない… orz

 

例 2 では、N=4 A=2 B=7 ですから、電車が 8 円、タクシーが 7 円で、出力は 7 。

例 3 では、N=4 A=2 B=8 で、電車もタクシーも同額の 8円で、出力は 8 となります。

 

わかりましたよ。こうしましょう。

 

  1. 数値の入力
    scanf() で変数にそれぞれ人数、電車の運賃、タクシーの運賃を入力します。
  2. 範囲の判定
    入力値が範囲外かどうかを判定して、範囲外の時は Error! を表示してプログラムを終了 (return 1;) します。たぶん、この制約の範囲内でプログラムを考えればいいよってことで、エラー処理はしなくてもいいみたいですけど。
  3. 最小値の計算と抽出
    最初は安いほうの運賃で分岐してどちらかを表示させる方法を考えたのですが、処理部分と表示部分は分けたほうがわかりいいよねってことで分けました。
    まず電車賃を最小値 lowestFare としておき、次にタクシー代と比較して、もしタクシー代の方が安ければ lowestFare を更新するという単純な方法です。
  4. 最小値の表示
    printf() で最小値 lowestFare を表示します。

 

で、こんなふうになりました。

 

/*  AtCoder Beginner Contest 133 A - T or T
    2019.07.24 by meyon  */

 

#include <stdio.h>

 

int main()
{
  // data input and judgment
  int N;    // number of people
  int A;    // train fare
  int B;    // taxi fare
  scanf("%d %d %d", &N, &A, &B);
  if(N<1 || N>20 || A<1 || A>50 || B<1 || B>50) {
    printf("Error!¥n");
    return 1;
  }

 

  // extract the lowest fare
  int lowestFare = N * A;
  if(lowestFare > B) {
    lowestFare = B;
  }

 

  // display the lowest fare
  printf("%d¥n", lowestFare);

 

  return 0;
}

 

なんだかね、やれそうな気がしてきましたよ (^_^;)

 

2019.07.26 追記

過去問題でも提出できることを知りました。

で、提出してみましたら、結果「AC」でしたよ。めでたい \(^o^)/

 


■競技プログラミング過去問題をやろうとしてみた…

やってみたんじゃなくて、やろうとしてみて、門前でめげたとゆ〜話 orz

 

C 言語を勉強しようと思い、なにか例題はないかなぁと探していたら、いいのがありました。

AtCoder:競技プログラミングコンテストを開催する国内最大のサイト

さっそく過去の問題に挑戦してみましょう。

 

7月14日の AtCoder Grand Contest 035 の A 問題「XOR Circle」です。

 

問題文
すぬけ君は N 枚の帽子を持っています。i 枚目の帽子には整数 ai が書かれています。

N 頭のラクダが円環状に並んでいます。 すぬけ君はそれぞれのラクダに 1 枚の帽子を被せようとしています。

どのラクダについても以下の条件が成立するような帽子の被せ方が存在するならば ' Yes ' を、そうでなければ ' No ' を出力してください。

・両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が自身の被っている帽子に書かれた数と等しい

 

すぬけ君って (^_^;) 「競技プログラミング_用語 - projecthikky @ ウィキ - アットウィキ」によると「AtCoder社の社員のレッドコーダーsnukeさんのこと」だそうです。

 

しかし、えっと、あの〜、なんてゆ〜か、問題の意味すらわかりません orz

 

だいたい、すぬけ君はなぜラクダに帽子を被せようとしているわけ? その帽子に書かれた数の排他的論理和が云々ってなんの意味があるん (?_?) 

あ〜そうか、なんか小難しい数値の処理をラクダと帽子に例えたってことね。

登場人物の名前といい、たとえ話の奇想天外さといい、俺みたいな一般人が容易に足を踏み込めそうにないオタクなにおいがしてくる… (^_^;)

 

閑話休題

 

最も理解できなかったのは「自身の被っている帽子」ってところ。帽子はラクダに被せるんでしょ? すぬけ君の被っている帽子ってなによ (?_?) ―― 考えること小一時間、気が付いた。「自身」というのは両隣のラクダに挟まれたラクダのことね。「自身」というからてっきり人だと思った。

つまりこういうこと。

あるラクダの両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が、そのラクダ自身の被っている帽子に書かれた数と等しい」

 

例 1 より、帽子の数 N を 3 、それぞれの帽子に書かれている数字 a を 1 、2 、3 とします。

あるラクダ自身の帽子に書かれた数が 1 だとすると、右隣のラクダの帽子に書かれた数が 3 で、左隣のラクダの帽子に書かれた数は 2 です。右隣の 3 を二進数表示すると 0b11 、左隣の 2 は 0b10 です。それらのビットごとの排他的論理和は 0b01 になります。ラクダ自身は 0b01 で、求めた値と等しくなりますから、与えられた条件は「真」です。

帽子に書かれた数が 2 のラクダについても、両隣のラクダの帽子に書かれた数 1 と 3 のビットごとの排他的論理和は 0b10 になりますから「真」、3 のラクダについても同様に「真」です。

ということで、「どのラクダについても条件が成立」したので ' Yes ' を出力します。

 

では例 2 はどうでしょう。N = 4 、a = 1 2 4 8 とします。

ラクダ a=1 (0b0001) の右隣のラクダを a=8 (0b1000) 、左隣のラクダを a=2 (0b0010) とすると XOR は 10 (0b1010) ですから「偽」です。

両隣を 8 と 4 にしてみても、2 と 4 にしてみても「偽」となり、a=1 について条件を満たすような帽子の被せ方は存在しません。

「どのラクダについても条件が成立する」ことが条件ですから、これ以上他のラクダを検討してみる必要はないでしょう。この場合は ' No ' を出力します。

 

ということで、ようやく問題の意味が理解できました。

 

では問題に従って 3 ≦ N ≦ 10、0 ≦ ai ≦ 109 について考えてみましょう …

 

わ、わっかりませ〜ん orz

 

ラクダの頭数が 10 万頭で、帽子に書かれる数は 10 億までの範囲のラクダの頭数分の個数。帽子に書かれた数がすべて異なるといった条件はありませんから、同じ数が書かれた帽子もありうると… あ〜、力業で総当たりするにしても、どうすればよいものやらさっぱり (^_^;)

つまりこれは、C だのなんだの言う前に、いわゆる「アルゴリズム」ってものをしっかり考えろというとても基本的な命題なのだと、改めて気が付いた meyon さんでした。

 


■電源ユニットに端子板を付ける

余っていたパソコンの電源ユニットを処分しようとしたんだけど、ふと、これ電源装置として使えるよなぁと思ったわけ。で調べてみました。

 

出力は +12V が二系統、+5V、+3.3V が各一系統と -12V 一系統。その他にスタンバイ用の +5VSB があります。

+5VSB は電源 ON で常に 5V が出力されていますが、他は出力していません。PS_ON という信号線を LOW に落とすと冷却ファンが回りだし、すべての出力が ON 。出力が ON になると PWR_OK が HIGH になります。

その他に 3.3Vsence というラインがありますが、これは +3.3V の出力検出用で、マザーボードに挿入するメインコネクタで +3.3V 出力に繋がっていました。

 

参考:ニプロン 製品情報 電源事典 Q&A Q. ATX電源_EPSのピンアサインについて教えて下さい。

 

 

電源ユニットからは、マザーボードや周辺機器を接続するために、さまざまな形のコネクタが付いたハーネスがたくさん出ています。これらを取り外して、出力と制御用に端子板を取り付けることにします。


電源ユニット

 

 

カバーを開けると、基板の出力部周辺はこんな感じ。同じ場所から何本もの電線が束になって出ていることがわかります。


出力線のようす

 

 

基板をひっくり返してみるとこんな感じ。大量のハンダが盛られていて、外し甲斐がありそうです (^_^;)


基板裏面のようす

 

 

電線を取り外しましたが、けっこう大変な作業でした。ハンダを取るとき、周辺の抵抗器などのハンダまで溶かしたり、パターンをショートしたりしないように注意が必要です。

信号線など一本だけ出ているところはそのまま残しています。


電線を取り外した基板

 

 

新たに出力線をハンダ付けし、ケースに戻します。


出力線を取り付け

 

 

ケースに端子板取付用の穴あけをします。ボール盤があればもっときれいにあけられるんですけどねぇ (言い訳 ^_^;)


ケースに端子板用の穴あけ

 

 

端子板を取り付け、出力線をハンダ付けして組み立てたら、完成です。


完成

 

 

端子板は以下のようになっています。3.3Vsence は No.4 端子に接続してあります。

 

No. 1 2 3 4 5 6 7 8 9 10
出力 12V(1) 12V(2) 5V 3.3V GND GND PS_ON 5VSB PWR_OK -12V

 

今回は 10pin の端子板を取り付けたのですが、これだと GND 端子が二つしか取れません。GND 端子は余裕があったほうが使いやすいので、12pin の端子板にしたほうがよかったかなと思っています。あと、端子板の表示をつけないといけませんね。

 


| 1/60PAGES | >>

■calendar

S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031
<< August 2019 >>

■search this site.

■recommend

毎日貯まるポイントサイト ECナビ

■recommend

* 楽天ROOM *

■Twitter

■recommend

■recommend

■selected entries

■categories

■archives

■recent comment

■recent trackback

■links

■profile

■others

■mobile

qrcode

■powered

無料ブログ作成サービス JUGEM