AOJ 1147 ICPC Score Totalizer Software
というものを見ていたら,ICPC・JAG非公式難易度表というのを見つけた.弐寺のDP非公式難易度表的なものらしい.せっかくなので一番上にあるやつを解いてみた.一応読んだことある問題で,面倒そうだしすぐ書けてしまいそうだからと言って飛ばしてしまったんだけど,書いてみるとかなりD言語っぽく綺麗に解けた.
問題
n人の審査員が付けた点数が入力されるので,最高点と最低点を除いた平均点を出力する
やりかた
そのまま.
import std.stdio; import std.algorithm; import std.conv; import std.string; import std.range; import std.math; void main() { while (true) { int n = readln.chomp.to!int; if (n == 0) break; int[] s; foreach (i; 0..n) { s ~= readln.chomp.to!int; } writeln((s.reduce!("a + b") - s.minPos[0] - s.minPos!("a > b")[0]) / (n - 2)); } }
最初に全部足したあと最高点と最低点を引いて,審査員の人数から2を引いた数で割ることで適切な値が出ます.
foreach (i; 0..n)
はfor (int i = 0; i < n; i++)
と等価(のはず)です.ドットを3つにすると右側の値を含むrangeになります.この書き方最近どっかで見て覚えたんだけどどこで見たんだっけ…….
std.algorithm.reduce
はそのままの関数です.確かa
がアキュムレータ,b
が各要素になって,テンプレート引数の評価した値がa
にどんどん入っていく仕様のはず.ちなみに初期値を設定したい場合は初期値が第1引数になるので,UFCSするなら100.reduce!("a - b")([1, 2, 3])
みたいにしないといけないのがインスタンスメソッドっぽくならなくてちょっとダサいです.テンプレート引数に文字列を指定するときはa
とかb
が実装で予約されている*1のでこれを使わないとダメですが,ラムダ式を使うときは(x, y) => x + y
とか出来ます.Rubyだとinject(:+)で等価になるはず.
klisのプログラミング環境
これは klis Advent Calendar 2014 の12月21日の記事(始まってから7日目)(間に2つ空白があるので5本目)の記事です.これにてアドベントカレンダー童貞卒業です.
About Me
klis12*1のYousackです.無芸なので前期入試です.知識情報システム主専攻にいます.自然言語を対象にした機械学習と人工知能を扱う研究室に仮所属しています(何もなければ本決まりの予定です).研究室ではまだ何もしてません(この前初めてのゼミに行ったら「皆さん試験とかレポートで忙しいでしょうから次は1月に集まりましょう」と言われました).
枕
@antefest メガネ部
— アッファ (@minjinaffa) 2014, 12月 18
という話もありましたがまあ去年放映の大人気*2アニメ「メガネブ!」についてはまた来世ということで.klisなんてメガネ学類(これは割と本当です)なんだし共通点あるからいいだろ! とか言ってゴネようかと思ったけど僕は真面目な人間なのでちゃんとklisに関連した記事を書きます.
klis内輪ントカレンダーではありますが,タイトルからも分かる通りたぶん既にklisにいる人が見るよりこれから入ろうかどうか考えてる人とかklisじゃない筑波大生が見たほうが得るものが多いかもしれません.
ちなみに最初は「klisに入って出来るようになったこと」という記事を考えていたのですが,この前の月曜日に出稿表明してから今日まで考え続けた結果僕が出来るようになったのはプログラミングぐらいしかなかった(あとは深夜アニメを見るようになった)のでこの内容にしました.
本編
全国でもあまり例を見ない「図書館情報学」を扱うklisですが,名前に「情報」と入っているからには情報科学関連の話やプログラミングの教育とかをしないといけないわけです.ではklisに入ってからのプログラミングの環境は一体どうなっているのでしょうか.
1年生の春Cモジュール(旧2学期前半,7月いっぱい)から,「プログラミング演習Ⅰ」という授業が始まります.次の年でOPAC(詳しくは後述)を作るための基礎になる授業です(ぶっちゃけプロ演Ⅰの時点でこの事をもっと主張してほしい).教える言語はRubyです.図書館関係に情報科学が割り込んだ学問領域のため,文字列処理をしやすい方がいいということで最近はRubyに落ち着いています.ちなみに過去はPL/IとかC言語とかを使っていたというのは内部生ならどこかの授業で聞いたことがあるでしょう(というかPL/Iの時代からこの授業があるのが凄い).作業環境はWindows 7/Meadow 3です.Linux(全学計算機にはUbuntu 12.04 LTSも入っている)ではありません.Windowsです.Emacsではありません.Meadowです.テキストは微妙です.「each文」とか書いてあります(当時はこの書き方の間違いに気付けなかったけど).もしGithubでテキストを管理していたらプルリクエストが確実に数件は学生から飛んでくると思います.
「情報基礎実習」は分からないなりに言われるがままにやっているだけでそこそこな能力が身に付く良い授業なのですが,「プログラミング演習」はその対極に居ると言えます.というか逆に大学の授業で教えるにはプログラミングの世界が広すぎなのが悪い(?)のですが.ただ他の環境が紹介されることもなく,WindowsはまだしもMeadowを使えと言われるのは2014年の授業にしてはかなり厳しいのではないかとは思ったりします.Meadowに関してはそもそもなぜ未だに全学計算機にインストールされているのかという話ですが(Windows向けのEmacsならGNUがWindows向けのバイナリを配布している).だいたい担当教員はプログラミングや情報科学の専門ではなかったりするし,学類の性質上プログラミングに全く興味が無い人も多い(むしろ多数派?)というのも要因ではあると思います.テキストの間違いについては,話を簡単にするために難しい部分を隠ぺいするのは時には必要だとは思いますが,だからと言ってよりにもよってこの1文字のタイポにも厳しい世界で間違った記述をするのはかなりマズいのではと危惧しています.そこら辺のプログラミングが出来る学生に金を払ってテキストを改善しろと言えば余裕で飛びついてきそうな気はします.ちなみにそういうことをボランティアでやろうとした結果が Yousack/rubylearn · GitHub (最終更新が1年前)なのでやっぱりお金が関わるというのは大変なことだなと思いました(授業にしても学生の授業料がかかっているわけだし).
ただ打開策はあります.大きく分けて2つ.
1つは,とにかく調べまくること.プログラミング入門者がぶち当たる壁の解決法はおそらくほぼ全てどこかのブログやQ&Aサイトに記述されているわけです.例えば「Meadowって使いづらいな」と思ったら「windows エディター」とか調べてみる.「あれ? Windowsにはインストールできないぞ?*3」となったらLinuxを使ってみる.「Linuxでこのエディターってどうやって使えばいいんだ?」と思ったらまた調べてみる.とか.ただ如何せん初心者なので限界があります.その時の打開策が次です.
この学類はなぜか毎年1-2人,大学に入る前からプログラミングが出来る人間が迷いこんできます.まずその人の存在を知ることが大事です(僕はクラスが違ったので冬口にようやく知りました).そこで「何なんだこいつは」で終わるか「この人は一体何をやっているんだろう?」と純粋な疑問を持つかが分かれ目です.後者になった人はおそらくプログラミングの沼に沈むでしょう.きっとそこには大学の(少なくともklisの)授業では得られない光景が広がっていると思います.前者になっても別に死ぬわけではありません.klisにはいろいろな道が用意されています.僕も図書館のことを勉強するぞ〜と言ってこの学類に来て「図書館概論」という授業を受け,「あれ,図書館意外と面白くないぞ……?」という印象を受け,当初の入学理由から一転してプログラミングの世界に転げ落ちて今に至ります.僕以外にも,当初は図書館マンだと思っていたのに気付いたらVimを使いこなしていた*4とか仕事でWebアプリケーションを書いていたとかそういう人がたまに居ます.
まとめ
- klisのプログラミング環境はぶっちゃけあまり良くない
- そもそも担当教員はプログラミングの専門ではない
- こういうことは大学ではままある
- プログラミングはプログラムと実行結果が全てなので,Meadowの使い方を紹介するのはいいが他のエディタの存在も示した方がいいのでは
- そもそも担当教員はプログラミングの専門ではない
- ただプログラミング関連の話題はWeb上に腐るほどあるので,自分で調べるということは出来る
- 調べ方(の基礎)は「情報基礎実習」で教えてもらえる
- どれだけ調べても万策尽きたら「このklisプログラマーが凄い」を調べてその人に教えてもらう
もともと思い付きで書き進めるくせがある上に久しぶりに長い文章を書いたのでかなりダメな記事なってしまいすみません.他にもklisには「知識情報演習」とか「データベース技術」とか「知識情報システム主専攻実習」とかいろいろありますが,どうもこの調子だととても長くなりそうなのでこの辺で…….他の話が聞きたければ Yousackの墓 (@antefest) | Twitter まで一報を.
明日はkng830さんです.音声で会話できる Droid -音声アシスタント - Google Play の Android アプリ,いわゆる「ドロイドちゃん」の開発者で,「このプログラマーが凄い!klis12」の一翼を担う彼の明日の記事に乞うご期待.
AOJ 0515 School Road
碁盤の目の左上から右下まで進む全事象の数を求める.ただし工事中のポイントがいくつかあってそこは通れない.
やりかた:左上に近いポイントから「ここまでの進み方は何通りあるか」を順番に右下まで計算する←動的計画法!
以下図解.
1--0--0--0--0 4行5列の例 | | | | | スタート地点を1にしておく 0--X--0--X--0 Xのところは工事中で通れない | | | | | (チェック用配列で先にチェックしておく) 0--X--0--0--0 | | | | | 0--0--0--0--0 1--1 | | ←1通り 1--? ←←←この?までの行き方は, ↑1通り ?の上の地点に行く全事象の数と ?の左の地点に行く全事象の数を足したもの→2通り (→↓と↓→) お分かりいただけるだろうか 1--1--1--1--1 | | | | | 1--X--1--X--1 | | | | | 1--X--1--1--2 | | | | | 1--1--2--3--5
実際にやるときは上と左に番兵を置いとく(与えられた行数と列数より1つずつ増やして,[1][1]
からスタートする)と境界チェックが楽.
import std.stdio; import std.algorithm; import std.math; import std.string; import std.conv; import std.range; void main() { while (true) { int c, r; readf("%d %d\n", &c, &r); if (r == 0 && c == 0) break; // 0行目と0列目を番兵にする int[][] map = new int[][](r + 1, c + 1); map[1][1] = 1; bool[][] bad = new bool[][](r + 1, c + 1); int n = readln.chomp.to!int; foreach (i; 0..n) { int x, y; readf("%d %d\n", &x, &y); bad[y][x] = true; } int[][] q = [[2,1], [1,2]]; while (!q.empty) { int[] p = q.front; q.popFront; int y = p[0], x = p[1]; // 工事中なら飛ばす if (bad[y][x]) continue; // 左と上の足し算が今いるポイントまで行く事象数 map[y][x] = map[y-1][x] + map[y][x-1]; // badをチェック済み配列としても使う bad[y][x] = true; // 右と下をキューに追加 if (y + 1 <= r) q ~= [y+1, x]; if (x + 1 <= c) q ~= [y, x+1]; } map[r][c].writeln; } }
AOJ - Problem 0515 : School Road - ひよっこプログラマのプログラミングを見ると工事中のポイントは上で言うmap
に-1
をセットしてたりキューを使わずにforループで処理しててなるほどと思った.キューの使い方を覚えたからと言ってやたらめったら使ってしまって良くない.
ABC#016 C問題 友達の友達
学期末のレポートに追い立てられて逃避で競技プログラミングの問題しか解いてない.
題意
N人のグループに対してM個の人間関係が与えられるので,各人について「友達の友達」(自分と自分の友達は含まない)の数を出力する.
やりかた
要はグラフなので,各ノード(人間)について幅優先探索で距離を数える
import std.stdio; import std.string; import std.conv; import std.array; import std.range; import std.algorithm; import std.container; import std.math; void main() { int N, M; readf("%d %d\n", &N, &M); bool[][] friend = new bool[][](N, N); for (int i = 0; i < M; i++) { int a, b; readf("%d %d\n", &a, &b); friend[a-1][b-1] = true; friend[b-1][a-1] = true; } // 1人目から順番に for (int i = 0; i < N; i++) { // アクセスしたかどうかの配列 bool[] check = new bool[N]; // 自分には先にチェックしておく check[i] = true; // 距離の配列 int[] d = new int[N]; // 幅優先探索用のキュー int[] q = [i]; while(!q.empty) { // 1人取り出す int p = q.front; q.popFront; // p番の人の人間関係について foreach (int j, isFriend; friend[p]) { // 未訪問 if(!check[j]) { // 友達なら if (isFriend) { // p番の人までの距離に1を足す d[j] = d[p] + 1; // 訪問チェック check[j] = true; // j番目の人をキューに追加 q ~= j; } } } } d.count(2).writeln; } }
図解(3人いて1番と2番,2番と3番が友達だとして,1人目からの距離を数える) friend [[0, 1, 0], [1, 0, 1], [0, 1, 0]] check = [t, f, f], d = [0, 0, 0], q = [0] qから先頭の要素を取り出す(p = 0, q = [], friend[p] = [f, t, f]) 2番がtなので1番(p)と2番(j)は友達 d[j] = d[p] + 1 = 1 d = [0, 1, 0] check = [t, t, f] q = [1] qから先頭の要素を取り出す(p = 1, q = [], friend[p] = [t, f, t]) 1番は訪問済み 3番がtなので2番と3番は友達 d[j] = d[p] + 1 = 2 d = [0, 1, 2] check = [t, t, t] q = [3] qから先頭の要素を取り出す(p = 2, q = [], friend[p] = [f, t, f]) 全て訪問済みなので何もしない qが空なのでwhileを抜ける
ざっとこんな感じ? 自分で書いてみて幅優先探索の仕組みがようやく分かった気がする.あと普段自分が競技プログラミングの簡単な問題で解説を調べてるときに全くコメントが入ってないプログラムとかを見ると初心者的には「は〜(°〜°)?????キレそーーwwwwwwwwwwww」ってなるので1行毎にコメントを入れたりループ毎の変数の状態を書いてみた.お役に立てれば.良い問題だった.
その他
- std.algorithm.countは便利
- テンプレート引数に述語を渡せる(
count!("a & 1 == 0")
とか)
- テンプレート引数に述語を渡せる(
- DPの教育的問題何か教えて下さい(AtCoderとAOJとCodeforcesはアカウント持ってます)
- 某太鼓ゲームの問題は何となく理解したつもり
2次元bool配列のテストケースを分かりやすくデバッグする
フィールドが与えられるのでその上でうんたんみたいな問題をこの前解きました.CODE THANKS FESTIVALで.まあAOJとかでもよくありますが.
で,大体の場合は「黒いマスだけを使って〜」とかそういう問題(当日はそうだった)なので,例えばD言語(というかC言語系統)ではbool[][]
で管理すると思うんですが,D言語でそのままwritelnすると[true, true, false]
みたいなものが直接吐き出されて見辛いなと思ってました.
が,コンテスト中にたまたま「配列の中身をmapで置き換えたものを出力してしまえばいいのでは?」ということに気付いてしまいました.のでやってみたら普通に出来た.
import std.stdio; import std.algorithm; void main() { bool[][] f = new bool[][](7, 9); for (int i = 2; i <= 4; i++) { for (int j = 3; j <= 6; j++) { f[i][j] = true; } } foreach (row; f) { row.map!("a ? '#' : '.'").writeln; } }
➜ ~ rdmd /tmp/hoge.d ......... ......... ...####.. ...####.. ...####.. ......... .........
mapのテンプレート引数の三項演算子でifもelseもchar
にすることによってrowがchar[]
になるので自動的に文字列形式で出力されるという話.ちなみにcharは(たぶん)UTF-8の2バイト以下の文字なら何でもいい(適当)ので,"a ? 'あ' : 'ん'"
とか"a ? '✔' : '✘'"
とかいろいろやって遊べます.
CODE THANKS FESTIVAL 2014 B日程 D,E問題
D 足ゲーム
矢印が判定エァリアに重なるタァーイミングでパァーノゥを踏むゲェーイム.パーノゥはN枚あってプレイ時間はT秒.i個目のパーノゥにはA_i秒間隔で矢印が降ってくる.パーノゥ1枚につき足を1本割り当てた時,最大で同時に何本の足が必要になるかを求める.以上,問題設定の拡大解釈版でした.
解法:最も多い公倍数が出現する頻度を答える
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; import std.numeric; void main() { int n, t; readf("%d %d\n", &n, &t); int[] a; for (int i = 0; i < n; i++) { a ~= readln.chomp.to!int; } int[] ldcary; foreach (e; a) { for (int i = 1; ; i++) { if (e * i > t) break; ldcary ~= e * i; } } auto countary = ldcary.sort.group; int maxcount = 0; foreach (tup; countary) { maxcount = max(tup[1], maxcount); } maxcount.writeln; } int ldc(int a, int b) { return a * b / gcd(a, b); }
各パネルの公倍数を持った配列を作ってその中で最も多い頻度のものをカウントして出力,という流れにしたけどちょっとストレートにやりすぎてごちゃごちゃになってしまった.逆に,サイズがT+1の配列を作って,インデックスが倍数の時にインクリメントして,その配列の中で一番大きい値を出力するというのが想定解だったっぽい.いま想定解で提出したら30msでした.はい.想定解は以下の通り.
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; void main() { int n, t; readf("%d %d\n", &n, &t); int[] a; for (int i = 0; i < n; i++) { a ~= readln.chomp.to!int; } int[] countary = new int[t + 1]; foreach (e; a) { for (int i = 1; i <= t / e ; i++) { countary[e * i]++; } } countary.minPos!("a > b")[0].writeln; }
~=
は配列に要素を追加する演算子.ついでに~
で配列同士を結合できます.
E マスゲーム
盤面上の黒いグリッドだけを通ってスタートからゴールまで行けるかどうかを確かめる.
解法:僕は(たぶん)幅優先探索で解きました.
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; void main() { int r, c; readf("%d %d\n", &r, &c); bool[][] field; for (int i = 0; i <= r + 1; i++) { bool[] f; for (int j = 0; j <= c + 1; j++) { f ~= false; } field ~= f; } bool[][] checked; for (int i = 0; i <= r + 1; i++) { bool[] f; for (int j = 0; j <= c + 1; j++) { f ~= false; } checked ~= f; } int rs, cs; readf("%d %d\n", &rs, &cs); int rg, cg; readf("%d %d\n", &rg, &cg); int n = readln.chomp.to!int; for (int i = 0; i < n; i++) { int ri, ci, hi, wi; readf("%d %d %d %d\n", &ri, &ci, &hi, &wi); for (int j = ri; j < ri + hi; j++) { for (int k = ci; k < ci + wi; k++) { field[j][k] = true; } } } bool result = false; int[][] queue; queue ~= [rs, cs]; while (!queue.empty) { int[] current = queue[0]; queue.popFront; int r_cur = current[0]; int c_cur = current[1]; // 黒い if (field[r_cur][c_cur]) { // ゴール if (r_cur == rg && c_cur == cg) { result = true; break; } if (checked[r_cur][c_cur]) continue; // チェックを付ける checked[r_cur][c_cur] = true; if (field[r_cur - 1][c_cur]) queue ~= [r_cur - 1, c_cur]; if (field[r_cur + 1][c_cur]) queue ~= [r_cur + 1, c_cur]; if (field[r_cur][c_cur - 1]) queue ~= [r_cur, c_cur - 1]; if (field[r_cur][c_cur + 1]) queue ~= [r_cur, c_cur + 1]; } } writeln(result ? "YES" : "NO"); }
そもそもスタートとゴールが白いマスである可能性に気をつける必要がある.ということで出だしから黒いマスのみを対象に処理することにした.というか黒いマスだけ処理するならエンキューする時にわざわざ黒いかどうかチェックする必要はないじゃないかと今更思ったので変更して提出したらちょっと速くなった.↑が45ms,↓が38msでした.
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; void main() { int r, c; readf("%d %d\n", &r, &c); bool[][] field = new bool[][](r + 2, c + 2); bool[][] checked = new bool[][](r + 2, c + 2); int rs, cs; readf("%d %d\n", &rs, &cs); int rg, cg; readf("%d %d\n", &rg, &cg); int n = readln.chomp.to!int; for (int i = 0; i < n; i++) { int ri, ci, hi, wi; readf("%d %d %d %d\n", &ri, &ci, &hi, &wi); for (int j = ri; j < ri + hi; j++) { for (int k = ci; k < ci + wi; k++) { field[j][k] = true; } } } bool result = false; int[][] queue; queue ~= [rs, cs]; while (!queue.empty) { int[] current = queue[0]; queue.popFront; int r_cur = current[0]; int c_cur = current[1]; // 黒い if (field[r_cur][c_cur]) { // ゴール if (r_cur == rg && c_cur == cg) { result = true; break; } if (checked[r_cur][c_cur]) continue; // チェックを付ける checked[r_cur][c_cur] = true; // 周りのマスをキューに追加 queue ~= [r_cur - 1, c_cur]; queue ~= [r_cur + 1, c_cur]; queue ~= [r_cur, c_cur - 1]; queue ~= [r_cur, c_cur + 1]; } } writeln(result ? "YES" : "NO"); }
D言語でキューとスタックの操作を実現するには~
,popFront()
,popBack()
を使います(というか僕は使ってます).具体的にはエンキュー・プッシュが~
,デキューがary[0]
を取り出した後ary.popFront
,ポップがary[$-1]
を取り出した後ary.popBack
(添字を書く場所では$
はその配列の長さに変換される.n..m
は[n,m)).何でこうしないといけないのかというとpopFront
もpopBack
も値を返してくれないvoid関数だからです.どうしてかは忘れた.確か公式サイトに書いてあった気がする.あとはstd.containerとかも使うのかもしれない.今やってみたら使えなかったのでよく分かりません.
ところでnew hoge[][](r + 2, c + 2)
みたいにすれば実行時に配列の大きさを決められるというのをarukukaさんのコードを見て初めて知ったんだけどこれってどこで調べればいいんだろう…….
CODE THANKS FESTIVAL 2014 B日程 A,B,C問題
CODE THANKS FESTIVAL,略すとCTFになって全く別のもの (Capture The Flag) になってしまうので来年もやるなら何とかしたほうがいいと思います.
Tasks - code thanks festival 2014 B日程(オープンコンテスト) | AtCoder
今回解くにあたってRubyとD言語で結構悩んだんですが,最終的に個性を発揮していこうということでD言語で書きました.僕以外にD言語を提出していたのはarukukaさん(F, G問題)だけでした.やっぱりアルゴリズム中心にプログラムを書くときはこっちの方が書きやすい気がする.ネイティブ吐くからC++並に速い(はず)なのでおすすめです.
A 朝食
コーヒーを淹れるのにかかる時間とトーストを焼くのにかかる時間が与えられるので,この2つを同時に始めた時に最終的に何分かかるのかを答える.
解法:maxを取る
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; void main() { auto input = readln.chomp.split.map!(to!int); writeln(input[0] > input[1] ? input[0] : input[1]); }
結構面倒な書き方をしちゃったけどD言語にはstd.algorithm.max
があるのでこれを使えばいいだけだった.ちなみにこれを使うとmax(input[0], input[1]).writeln
になる.
B 電卓ゲーム
3つの数字が与えられるので,足し算と掛け算を使って一番大きくなる数を求める.
解法:数の順番は同じだから全事象は4通りなので,全部やる
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; void main() { int a = readln.chomp.to!int; int b = readln.chomp.to!int; int c = readln.chomp.to!int; int pp = a + b + c; int pm = (a + b) * c; int mp = (a * b) + c; int mm = a * b * c; writeln(max(pp, pm, mp, mm)); }
いちいち代入せずに全部直接引数に書けばよかった.以下の通りになる.
max(a + b + c, (a + b) * c, (a * b) + c, a * b * c).writeln;
std.algorithm.maxの引数は2個以上です.可変長です.ちなみに配列の中で最小の要素を求めたいときはstd.algorithm.minPosを使います.この関数は引数の配列の中で最小の値が先頭になるような部分配列を返します.テンプレート引数に述語を渡すとその述語を元に大小を判断するようになります.公式ライブラリリファレンスにもある通り,この理由によりmaxPos関数はありません.以下のように動作します.
import std.stdio; import std.algorithm; void main() { int[] ary = [ 5, 9, 2, 3 ]; ary.minPos.writeln; // [2, 3] ary.minPos!("a > b").writeln; // [9, 2, 3] ary.minPos!("a > b")[0].writeln; // 9 }
C 人気投票ゲーム
全ての投票数の数列ときつね派の投票数の数列が与えられるので,各列についてきつね派が過半数を取った列を数える.
解法:過半数の定義は「半分より大きい」なので,この点に注意して比較する.
import std.stdio; import std.algorithm; import std.range; import std.string; import std.conv; void main() { readln; auto v = readln.chomp.split.map!(to!int); auto f = readln.chomp.split.map!(to!int); int count = 0; foreach (e; zip(v, f)) { if (e[1] * 2 > e[0]) { count++; } } count.writeln; }
きつね派の投票数が全体の投票数の2倍より大きければOK.基本的に割る系の処理は誤差とか切り捨てとか怖いので使わない方向で.あとD言語にもzip
関数はあります (std.algorithm.zip
).zip([[1, 2, 3], [4, 5, 6]])
が[[1, 4], [2, 5], [3, 6]]
になるタイプのやつです.あとforeach
も言語仕様でサポートされています.foreach_reverse
もあります.reverseの方はあんまり使ったことないけど.