■Arduino シリアル通信 Serial.print() を試してみる

前回の「Arduino シリアル通信を試してみる (文字列)」で、シリアルモニターから送られるデータは ASCII コードになっているらしいとわかったわけですが、じゃ Arduino からシリアルモニタへ出力するときはどうなってるのか、調べてみます。

 

Reference の Serial.print() を確認してみました。

 

Prints data to the serial port as human-readable ASCII text. This command can take many forms. Numbers are printed using an ASCII character for each digit. Floats are similarly printed as ASCII digits, defaulting to two decimal places. Bytes are sent as a single character. Characters and strings are sent as is.

 

データは ASCII コードで出力されます。数字も各桁ごとに ASCII コードになるようですね。浮動小数点数も同じですが、小数点以下 2桁になるとのこと。

バイト形式は一つの文字として送るということなので、この場合は数字のようにバラバラにはならないということでしょうか。あとで確認してみましょう。

文字と文字列は「そのまま」です。

 

では、実際に確認してみます。ちなみに Serial.println() はデータの末尾に改行コード (CR+LF) を付加する関数で、それ以外は Serial.print() と同じです。

文字列を送ってみます。

 

  1. Serial.println("hoge");

 

シリアルモニタには「hoge」とそのまま表示されます。内部的には ASCII コードで送るのでしょうが、文字形式は「そのまま」の文字として出力されるということです。

変数ではどうでしょうか。

 

  1.   char str[]="Hello world!";
  2.   Serial.println(str);

 

変数の場合も意図したように、そのまま「Hello world!」と表示されました。

 

数字形式で試してみます。

 

  1.   int num=65;
  2.   Serial.println(num);

 

シリアルモニタには「65」と表示されました。この場合は「65」が文字列としてそのまま送信されたということなのでしょう。

浮動小数点数を送ってみましょう。

 

  1.   float num=12.345678;
  2.   Serial.println(num);

 

「12.34」と小数点以下 2桁になって表示されました。

 

数字では表示フォーマットを指定できます。

 

  1.   int num=65;
  2.   Serial.println(num, BIN);

 

この場合は「1000001」と 2進数形式で表示されます。あくまでも文字列として扱っているのですから、BIN を指定した場合は改行コードを含んで 9 バイト送信しているということになるのでしょうか。

なお、浮動小数点数の場合はフォーマットで小数点以下の桁数を指定できるようです。

 

バイト形式を試してみましょう。バイト形式はひとつの文字として送るということでした。

 

  1.   byte b=B01000001;
  2.   Serial.println(b);

 

「65」と表示されました。B01000001 は 10 進数の「65」を表していますので、文字列「65」を送信したってことですね。

では、これはどうでしょうか。

 

  1.   byte b='A';
  2.   Serial.println(b);

 

文字「A」をバイト形式にして送信すると、シリアルモニタには「65」と表示されました。「A」の ASCII コードの値「65」が送信されたということですね。

フォーマットを指定してみます。

 

  1.   byte b='A';
  2.   Serial.println(b, BIN);

 

今度は「1000001」と表示されました。「65」が 2進数形式で送信されたということです。

 

さてと、こうしてみてくるとなんだか様子がわかってきました。Serial.print() 、Serial.println() では、

 

  1. 文字も数字も改行コードもすべて ASCII コードにして送信する。シリアルモニタ側では、受け取った ASCII コードに該当する文字を表示する。
  2. 文字形式はそのまま送信する。数字は桁ごとの文字列として送信する。
  3. バイト形式はひとつの値として扱い、その値を文字列として送信する。

 

ってことです。わかってしまえば当たり前のことですけど、どうやら俺は、数字と ASCII コードを混同してわけわからなくなってしまうようです。

次はもう一度、シリアルモニタから Arduino へ送る場合を試してみたいと思います。

 


■Arduino シリアル通信を試してみる (文字列)

以前「Arduino シリアル通信でLチカを試す」で Arduino とパソコン間のシリアル通信を試してみたことがありました。でも、やってみたらできたって感じでよくわかっていなかったので、今回はもう少しちゃんと調べてみようと思います。

 

まず、Reference の Serial.available() にあるサンプルスケッチで試してみましょう。

 

  1. int incomingByte = 0; // for incoming serial data
  2. void setup() {
  3.   Serial.begin(9600); // opens serial port, sets data rate to 9600 bps
  4. }
  5. void loop() {
  6.   // reply only when you receive data:
  7.   if (Serial.available() > 0) {
  8.     // read the incoming byte:
  9.     incomingByte = Serial.read();
  10.     // say what you got:
  11.     Serial.print("I received: ");
  12.     Serial.println(incomingByte, DEC);
  13.   }
  14. }

 

シリアルインターフェースから受信したデータをそのまま送り返すスケッチです。シリアルモニタを開いて試してみました。

 

入力 出力
123 I received: 49
I received: 50
I received: 51
I received: 10
ABC I received: 65
I received: 66
I received: 67
I received: 10

 

シリアルモニタから「123」と入力して送信すると、出力のように表示されます。ここで、あれ?と思っちゃう。そのまま送り返しているはずなのに、違うじゃん (^_^;)

よーく考えてみると、文字「1」の ASCII コードは「49」、文字「2」は「50」です。入力したデータが ASCII コードとしてやり取りされている、ということですね。

最後の「10」は改行コードの LF を表します。シリアルモニタでは送信ボタンをクリックすると LF が送られるんです。シリアルモニタの右下の「LFのみ」を「CRのみ」とすると改行コード CR の「13」が表示されます。

 

シリアルモニタから入力された文字列は Arduino に送られてシリアルバッファに格納されます。Serial.read() を実行するとバッファの最初の 1 バイトが読み取られます。そして最初の 1 バイトはクリアされる (のじゃないかと思います) 。Serial.read() を繰り返すたびに 1 文字ずつ読み取っていき、読み取れるデータがなくなったら次のデータを待ちます。

そんな仕組み。間違っているかもしれません。間違っていたら笑ってやってください。

 

ところで、これを文字列にしようと思ったら 1 文字ずつ配列変数に格納するなどしなくてはいけません。Serial.available() で文字数を取得して配列変数を定義し、1 文字ずつそこに格納していくって感じかな。難しくはないけれど、面倒くさい (^_^;)

 

文字列を簡単に読み取れないのかなぁとググってみたら、Serial.readString() という関数があることがわかりました。ただ、この関数はタイムアウト (デフォルトは 1000ms) で終了するので、処理が遅いのが欠点。実際試してみると、データを送信して 1 秒後に表示されます。

そこで、Serial.readStringUntil( terminator ) 関数を使うことにしました。terminator に '¥n' を指定すると、改行コードを受信した時点で終了してくれます。

 

作り直したスケッチはこんな感じ。変数名やコメントは変えてないので、ちょっと違和感もありますが、ご容赦。

 

  1. String incomingByte; // for incoming serial data
  2. void setup() {
  3.   Serial.begin(9600); // opens serial port, sets data rate to 9600 bps
  4. }
  5. void loop() {
  6.   // reply only when you receive data:
  7.   if (Serial.available() > 0) {
  8.     // read the incoming byte:
  9.     incomingByte = Serial.readStringUntil('¥n');
  10.     // say what you got:
  11.     Serial.print("I received: ");
  12.     Serial.println(incomingByte);
  13.   }
  14. }

 

これで入力した文字列と同じ文字列が出力に表示されるようになりました。

 


■AtCoder Beginner Contest 138 A - Red or Not

簡単なA問題をちょこちょこやってみてます。これぐらいのソースはリファレンスとか見なくても書けるようになりたいよねぇって思いなんですけど、それでも、あれ?どうするんだっけ?ってなることが日常茶飯な meyon さん。

 

AtCoder Beginner Contest 138 A - Red or Not

問題文

整数  a  と、英小文字からなる文字列  s  が入力されます。

a  が  3200   以上なら   と出力し、  が  3200   未満なら  red  と出力するプログラムを書いてください。

 

難しいことは何もないのですが、いざソースを書こうとしたら文字列の扱い方がわからない (^_^;)

 

文字列は配列に入れる。文字数が10文字ならば最後にヌルを付けて11文字分必要になるので、

 

  1.   char s[11];
  2.   scanf("%s", s);

 

とする。間違えて s[10] としてもヌルの分は自動的に足してくれるらしい。s[] としておけば必要なだけ割り当ててくれる。

代入するときは s[] じゃなくて s だけ書く。これはポインタを示しているらしい。

出力は同様に、

 

  1.   printf("%s¥n", s);

 

とすれば、文字列として出力される。

 

  1.   printf("%c¥n", s[2]);

 

のようにすると、3 文字目が出力される。

まぁそんな感じかな。

 

ってことでこんなふうになりました。

 

  1. #include <stdio.h>
  2. int main()
  3. {
  4.   int a;
  5.   char s[11];
  6.   scanf("%d %s", &a, s);
  7.   if (3200<=a) {
  8.     printf("%s¥n", s);
  9.   } else {
  10.     printf("red¥n");
  11.   }
  12.   return 0;
  13. }

 

 

なお、ソースコードの表示には「srctohtml ソースをHTMLで見やすく出力するツール」を利用させていただきました。ありがとうございます。

 


■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 ) です。

 

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

 


<< | 2/61PAGES | >>

■calendar

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
<< November 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