カンマ区切りでwhile,for,if文などの条件式を書く時の注意点

自分はこれで苦労したことがあったので備忘録としても書いておくことにする

CやC++ではif(0 < n)などのように括弧内に条件式を書く.
これはwhile(0 < n) for(;i < n;) のようにwhile for文にも同じように書ける.

AOJ等でこんな問題が出る.
カードゲーム | Aizu Online Judge

標準入出力を行うプログラムを作成して下さい。
上記の形式で複数のデータセットが与えられます。nが0のとき入力が終了します。

nの入力の部分だけなら

while (1){
  scanf("%d", &n);
  if (n == 0){
    break;
  }
}

このように書けるだろう.しかしこういう風にも書ける.

while (scanf("%d", &n), n != 0)

後者のほうがコンパクトで見やすい.
因みに,while (scanf("%d", &n), n)と書いても同じような結果になる.
これは,(カンマ)以降に書かれているものを条件式としている.

ただし,このような書き方で注意すべき点がある.
ビデオテープ | Aizu Online Judge

複数のデータセットが与えられます。各データセットは以下のとおりです。
時(整数)分(整数)秒(整数)
入力は、3つの -1 で終わります。

分かった!!さっきの書き方でやると...

while (scanf("%d%d%d", &h, &m, &s), h != -1, m != -1, s != -1)

これでは間違い.この書き方ではs != -1しか条件式として扱ってくれない.
この問題では3つの終了する条件があるので,論理演算子 を使う必要がある.

h-1のときとm-1のときとs-1のときだから...

while (scanf("%d%d%d", &h, &m, &s), h != -1 && m != -1 && s != -1)

一見正解に見えるが,実はこれも間違い.ここで改めて論理演算子の意味を思い出してほしい.
以下はa && b,a || bのときを表している.

&&
a b 真偽
0 0 0(偽)
1 0 0(偽)
0 1 0(偽)
1 1 1(真)
||
a b 真偽
0 0 0(偽)
1 0 1(真)
0 1 1(真)
1 1 1(真)

例えば先程のコードで-1 2 2と入力したとする.
条件は 3つの-1で終わる ことだ.しかしこれではwhileを抜けてしまい終了してしまう.
詳しく見ていこう.

h には-1m には2s には2 が入る.
まずh != -1これは0(偽)になる.m != -1 これは1(真).s != -1も1(真)だ.
論理演算子&&なので表に合わせてみると0 && 1 && 1になり最終的に0になる.
0ということはwhile文を抜けることになる.3つとも-1ではない のにだ.

なので正解は

while (scanf("%d%d%d", &h, &m, &s), h != -1 || m != -1 || s != -1)

これなら0 || 1 || 11になり条件に合わずに抜けることが無くなる.
考えてみれば当然だが,,(カンマ)で区切らない方法で書くと

while (1){
  scanf("%d%d%d", &h, &m, &s);
  if (h != -1 && m != -1 && s != -1){ // ||じゃなくて&&
    break;
  }
}

となり&&で書くのでカンマ区切りと逆になってしまう.
僕のようなプログラミング初心者が躓いてしまい,AOJでWAを出される羽目になってしまうので注意していただきたい. (因みにこの問題ではチェックが甘いのでh != -1だけでも通る)

何か間違っている点があればコメント等で教えていただけると幸いです.

AOJ0611 - Silk Road (DP)

AOJ0611のSilk RoadをDPの練習として解いてみました.
また,この問題を解くにあたって以下のサイトを参考にしました.

コード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX_D (1000)
#define MAX_C (1000)
 
int N, M;
int D[MAX_D], C[MAX_C];
// -1ならまだ調べていない
int dp[MAX_D + 1][MAX_C + 1];
 
int rec_dp(int now, int day);
 
int main()
{
  scanf("%d%d", &N, &M);
  memset(dp, -1, sizeof(dp)); // -1でメモ化テーブルを初期化
 
  for (int i = 0; i < N; i++) scanf("%d", &D[i]);
  for (int i = 0; i < M; i++) scanf("%d", &C[i]);
 
  printf("%d\n", rec_dp(0, 0));
 
  return (0);
}

// nowは現在地,dayは何日目かを表す
int rec_dp(int now, int day)
{
  if (dp[now][day] != -1){ // 一度調べていたら再利用
    return (dp[now][day]);
  }
   
  int res;
  if (now == N){ // 目的地に到着
    res = 0;
  }
  else if (N - now == M - day){ // 目的地に到着するためには進むしかない場合
    res = rec_dp(now + 1, day + 1) + (D[now] * C[day]);
  }
  else { // 進むか待機するか決められる場合
    res = min(rec_dp(now, day + 1), rec_dp(now + 1, day + 1) + (D[now] * C[day]));
  }
 
  dp[now][day] = res; // 結果を保存
 
  return (dp[now][day]);
}

提出したやつ

今回はメモ化再帰のDPで解きました.
またmemsetを初めて使ってみました.(31行目がdp[now][day] != 0でもいけそう)
単純な再帰に手を加えると計算効率がだいぶ上がるので,マスター出来るようにしたい.
また,漸化式を用いたDPも出来るようになりたい.(forだけで書けるので見た目もタイプ量も減りそう)
もっとこここうした方がいいよ,などあればコメント等に書いて頂ければ幸いです.

(この記事はictechの「Markdown超入門」を受け,Markdownで書かれています)

AOJのsolve数が100問超えたよ!!やったね!!


ヤッタ-100solveコエタ-



こんにちは.kurokojiです.
やっとAOJで100solve超えました.年度内に100solveすることは目標にしてあったので達成することが出来たので良かったです.
次は200問ですね.



なんか100問解いた後,暇だったので



長方形 | プログラミング入門 | Aizu Online Judge
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1654385&tab=1

main(){int a,b;scanf("%d%d",&a,&b);printf("%d %d\n",a*b,2*a+2*b);return 0;}

なんだこれは!?

以上です.