■Arduino / ubuntuとシリアル通信してみた -2-

Arduino / ubuntuとシリアル通信してみた」で試してみたターミナルコマンド cu による LED の PWM 制御を、少し改良してみました。

前回は数字を 3つ入力すると LED の明るさが変わるというものでした。これを 0 から 255 までの数字を入力して Enter を押すと、その値に従って LED の明るさを変えるようにしたいと思います。

そのために、桁数の異なる数字をシリアル通信で Arduino に送り、数値として PWM 制御に渡す必要があります。少しググってみたのですが、シリアル通信で数値を送るには、文字列を数値に替えるだけでなく、桁数の違いをどう処理するかなど、けっこう面倒な雰囲気です。単純な処理なのでもっと簡単な方法がないかなと探していたところ、こんなチュートリアルを見つけました。

 

String to Int Function

The toInt() function allows you to convert a String to an integer number.

In this example, the board reads a serial input string until it sees a newline, then converts the string to a number if the characters are digits. 

 

ドンピシャです。文字列を数値に変換する、まさに求めていた内容ですよ。

toInt() は String オブジェクトの関数です… よくわかりません (^_^;) でもこうやって使うとこういう結果が出るということは、簡単に理解できます。なお、このチュートリアルにあるサンプルコードは、IDE のスケッチ例「08.String」に「StringToint」として附属しています。

 

さて、そのサンプルコードを参考にした、cu から送信するデータに従って 3番ピンに接続した LED を PWM 制御するスケッチです。

 

  1. // PWM control LED from cu 2019/09/09 meyon
  2. const int ledPin = 3;
  3. String inStr = "";
  4. void setup()
  5. {
  6.   pinMode(ledPin, OUTPUT);
  7.   Serial.begin(9600);
  8. }
  9. void loop()
  10. {
  11.   while(0 < Serial.available()) {
  12.     int inChar = Serial.read();
  13.     Serial.write(inChar);
  14.     if(isDigit(inChar)) {
  15.       inStr += (char)inChar;
  16.     }
  17.     if(13 == inChar) {
  18.       int ledBri = inStr.toInt();
  19.       ledBri = constrain(ledBri, 0, 255);
  20.       analogWrite(ledPin, ledBri);
  21.       Serial.print("¥nBrightness: ");
  22.       Serial.println(ledBri);
  23.       inStr = "";
  24.     }
  25.   }
  26. }

 

16行目は cu へのエコーです。Serial.write() はデータを byte 型で出力するので、受け取った数字の ASCII コードをそのまま cu へ送り返し、入力した数字を表示させることができます。

18行目で入力データが数字かどうかを判断し、数字なら文字列として inStr に追加していきます。

22〜25行目。入力データが Enter の場合 ASCII コード (13) が届きますので、それまでに届いた文字列を数値に変換して 3番ピンへアナログ出力します。

数値は 0〜255 の範囲に制限し、256 以上の場合は 255 としています。int 型なので 32767 を超えると出力は 0 になってしまいますね。また、入力に数字以外が含まれていると無視されます。数字だけを抽出して制御値になります。

 

これでかなりエクセレントになった気がします (^_^;)

 


■Arduino / ubuntuとシリアル通信してみた

ubuntu と Arduino 間でシリアル通信してみます。

ubuntu では cu コマンドを利用します。まずはインストール。

 

$ sudo apt install cu

 

起動・接続は以下。切断・終了は「~.」ですが、Arduino で受信したデータを送り返すスケッチを動かしていると ~. も折り返されてくるだけで終了できません (^_^;) 正しい方法かどうかわからないのですが、Ctrl+c 押した後に ~. で終了できました。

 

$ cu -s 9600 -l /dev/ttyACM0

 

シリアルモニタとは動作が異なります。

シリアルモニタでは入力した文字列が「送信」ボタンを押すことで一括して送られましたが、cu では入力ごとに即送信され、たとえば「A」キーを押すとすぐに「65」が返ってきます。

 

そこで、数字を 3つ入力するとその値で LED の明るさを制御するようなスケッチを書いてみました。

LED は 3番ピンに繋ぎますが、最大で 20mA 程度流しますので LED 駆動用にトランジスタを 1個入れてます。まぁ毎度の回路です。電源は USB を刺しているので、Arduino の 5V 出力を利用しました。

 

  1. const int ledPin=3;
  2. void setup() {
  3.   pinMode(ledPin, OUTPUT);
  4.   Serial.begin(9600);
  5. }
  6. void loop() {
  7.   while(0 < Serial.available()) {
  8.     int data = Serial.read();
  9.     Serial.println(data);
  10.   
  11.     static int val[3];
  12.     static int i=0;
  13.     val[i]=data-48;
  14.     i++;
  15.     if(2<i) {
  16.       int bri = val[0]*100+val[1]*10+val[2];
  17.       bri = constrain(bri, 0, 255);
  18.       Serial.print("Brightness: ");
  19.       Serial.println(bri);
  20.       analogWrite(ledPin, bri);
  21.       i=0;
  22.     }
  23.   }
  24. }

 

Arduino へ書き込んだら IDE を終了します。

cu を起動し接続。数字を 3つ押すごとに LED への出力が変化します。「255」 と押すと LED が 100% で点灯します。「128」なら 50% 、「000」で消灯です。入力値が 255 を超える場合は 255 にしますが、contrain() なんて便利な関数があったので使ってみました。

受信したデータは 48 を引くことで数値に変換しています。3つデータを受けたら 3桁の数字に計算しているだけですが、このあたりがどうもエクセレントじゃないですよねぇ (^_^;)

 


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

Arduino シリアル通信 Serial.print() を試してみる」で、Arduino からシリアルモニタへデータを送るときはすべて文字列として扱っていることがわかりました。文字は ASCII コードとしてシリアルポートへ送られ、シリアルモニタ側では受け取った ASCII コードに対応した文字を表示しています。

 

では、シリアルモニタから Arduino へ送信する場合はどうでしょうか。簡単なスケッチで試してみます。

 

  1. void setup() { 
  2.   Serial.begin(9600); 
  3. void loop() { 
  4.   if(Serial.available() > 0) { 
  5.     int data = Serial.read(); 
  6.     Serial.println(data, DEC); 
  7.   } 

 

シリアルモニタから「A」と送信すると、

 

65
10

 

と表示されました。

シリアルモニタ側で「A」と入力すると、文字「A」の ASCII コード (65) がシリアルポートへ送られるはずです。

Arduino 側では、Serial.read() で読み取ったデータを数値変数 data に代入し、Serial.println() で 10 進数のフォーマットで出力しています。そこで表示されたのが「65」ということは、Serial.read() がシリアルポートから送られてきた ASCII コードそのものを読み取っている、ということです。

 次に表示されている「10」は、シリアルモニタから送信されるときに付加された改行コード LF のASCII コードです。シリアルモニタでは、入力されたデータは「送信」ボタンを押したときに改行コードを付加してまとめて送出されています。

 

ということはですよ、入力した文字をそのまま表示させるには、読み取った ASCII コードを文字に変換すればいいんじゃないですか?

 

  1.     char data = Serial.read();
  2.     Serial.println(data);

 

スケッチの一部を上のように書き換えます。シリアルモニタで「A」と入力すると、

 

A

 

と出力されました。ASCII コード (65) を文字変数 data に代入すると、その中身は文字「A」となりますね。そーゆーことです (^_^;)

ところで、「ABC」と入力するとどうなりますか?

 

A
B
C

 

となってしまいます。スケッチをちょっと工夫しましょう。

 

  1. void loop() {
  2.   if(Serial.available() > 0) {
  3.     char data = Serial.read();
  4.     if(10 == data) {
  5.       data = '¥n';
  6.     }
  7.     Serial.print(data);
  8.   }
  9. }

 

末尾に改行コード LF がついてくるのですから、LF のときだけ改行するようにしました。これで出力は、

 

ABC

 

となりました。

 

  1. Arduino → シリアルモニタでは、データは文字列としてそのまま送信される。
  2. シリアルモニタ → Arduino では、データは文字列として送られ、Serial.read() は文字の ASCII コードを読み取る。

 

これでシリアル通信の状況がわかりました。わかってしまえば、まぁなんてことないですよねぇ (^_^;) たぶん、ね。

 


■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 では一つのループしか抜けられません。

 

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

 


| 1/61PAGES | >>

■calendar

S M T W T F S
1234567
891011121314
15161718192021
22232425262728
2930     
<< September 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