あたまがはてな

お久しぶりです。大体2ヶ月ぶりになりますね。まあTwitterには毎日いるんですが。

本当はもっと早く何か書きたかったんですが、就活のために棚上げにしていたありとあらゆるタスク*1に囲われ袋叩きにされる生活がここのところ続いていてそれどころではなかったという事情があります。

ということで、2ヶ月ほど遅れての報告になりますが、内定をいただきました。聡明な皆さんは今日の日付と2ヶ月前の投稿頻度を見比べて何かに気づいたりもしたでしょうが、そこはそれ: この "はてなぶろぐ" って奴を吸うとな……頭がスゥーーー…っとして現実のことなんてみんな忘れちまえるんだ……お前さんもどうだい？

ニシキヘビは足が遅い

今日の記事はほとんど技術ポエムみたいなもんなのでTLDRもないし、見出しにも情報がないです。あしからず。

最近まわりで競プロ始める人が多いんですよ。就活控えた情報畑の人とかはまあなんか分かるんですけど、今までプログラミングのプの字も見せなかった人までなぜだかこぞってatcoderで遊んでいます。なんで？まわりの人が偏ってるから？

それで感化されてというか、先日のabc129に参加しました。久しぶりの参加、そして元よりよわよわ緑マンとは言え、過去最低級のパフォーマンスを叩き出して少しカチンと来た*2ので、暇をみて修行しようと心に決めました。暇くれ。

ところで本題はここからです。先日のコンテストには python で参加したのですけど、あの言語遅っそいですね。知ってたけど。 D問題結局 TLE*3 で通せなかったので慣れない C で書き直して時間食いました。本当に悔やまれる。

あー、どっかに LL みたいにさらっと書けるコンパイラ言語いないかな～～～。

もしや今こそD言語くんと再び対話するときなのではないか……？

以前僕はD言語ニワカ勢としてちょびっと記事を書いたりしましたが、あれからめっきり触らなくなってしまったのでもはや何も覚えてません。いや、文法は好きなんだけどいかんせん用事がなくって……。

いい機会なので先日の問題をD言語で解き直してみようかなと思ったわけです。

D言語くんは言うことを聞かない

既に python で書いたコードばかりなので、写すだけだし楽勝やろと思ってたんですよ。

A - Airplane

3点 A, B, C と各点間の距離が与えられたとき、すべての点を回る最小距離を求める問題。言うまでもないことですが、AB, BC, CA の3つの距離のうち短い2つの和が答えになります。

コードは1行でさらっと書けます:

import std.algorithm;
import std.conv;
import std.stdio;
import std.string;

void main() {
  readln.chomp.split.to!(int[]).sort[0..2].sum.writeln;
}

ところが提出すると CE *4 が出ている。Warning: use std.algorithm.sort instead of .sort propertyだそうだ。なんでや手元じゃ動いたやろが*5。

どうやら原因はこの辺にあるらしい。手元の環境(DMD v2.083.0)では既に存在しないものの、配列には .sort プロパティというのがかつて存在して、これがジャッジサーバの環境(DMD v2.070.1)ではまだ存在するが deprecated なので警告が出たという話である模様。でもさっきのページ見る限り deprecated になったの 2.072 からっぽいんですけど……？おかしいな。

これを回避するには、ちゃんと std.algorithm の sort() を呼んだんだぞということを教えてあげればよい。つまり:

// .sort の後の () を省略しない
readln.chomp.split.to!(int[]).sort()[0..2].sum.writeln;

これでちゃんと AC *6 になりました。

B - Balance

長さ N の数列が与えられたとき、その数列を適当な位置で2分して、前半の和と後半の和の差の絶対値を最小化する問題。N が高々 100 なので全探索一択です。

1行とまでは言わないけどさらっと書けるでしょ。こんな感じでどうですか:

// import文は省略

void main() {
  auto n = readln.chomp.to!int;
  auto w = readln.chomp.split.to!(int[]);

  int ans = int.max;
  iota(1, n).each!(t => {ans = ans.min(abs(w[0..t].sum - w[t..$].sum));});
  ans.writeln;
}

はい、WA *7です。

今度は何だとブチ切れながら調べていると、このラムダ式が良くないらしい:

t => {ans = ans.min(abs(w[0..t].sum - w[t..$].sum));}

C# を書くときのノリで調べもせずに適当に書いたのですが、どうやらこの書き方だと「tを引数に取ってsum(w[0..t])-sum(w[t..$])の絶対値がansより小さければansを上書きする」という意味にはならないようです。なぜならば D言語の { /* ... */ } は デリゲートリテラル だからで、したがって先のコードは「tを引数に取って『sum(w[0..t])-sum(w[t..$])の絶対値がansより小さければansを上書きする』ような関数(正確にはデリゲート)を返す」という意味になります。そりゃ何も起こらんわ。

したがって以下のように修正する必要があります:

// {} を外す
t => ans = ans.min(abs(w[0..t].sum - w[t..$].sum))

// あるいはラムダ式をやめて直接デリゲートリテラルを置く
(t) {ans = ans.min(abs(w[0..t].sum - w[t..$].sum));}

これで AC です。

C - Typical Stairs

1段または2段ずつ階段を登れるとして、指定されたM個の段を踏まないように N段の階段を登りきる方法は何通りあるかを求める問題。N = 1 から順番に部分問題を解いていけばいいだけ。

「指定された段」を愚直に配列で管理すると O(NM) となって TLE になる*8ので、HashSet などを使って適切に管理する必要があります。 D言語に HashSet はありませんが、代わりに赤黒木があるのでこちらを使います。

// import文は省略

void main() {
  const MOD = 1000000007;

  auto nm = readln.chomp.split.to!(int[]);
  auto n = nm[0];
  auto m = nm[1];
  
  auto a = make!(RedBlackTree!int)(stdin.byLine.map!(to!int));

  int[int] dp = [
    0: 1,
    1: 1 in a ? 0 : 1,
  ];

  foreach (k; 2..(n + 1))
    dp[k] = k in a ? 0 : (dp[k - 1] + dp[k - 2]) % MOD;
  
  dp[n].writeln;
}

珍しくつつがなく AC が出ました。

D - Lamp

壁または床で構成されたチェス盤の適当な位置に1つルークを置くとき、ルークの移動可能範囲を最大化する問題。盤が広いので雑に実装すると TLE する。

各マスに「そこから左右に何マス動けるか」「そこから上下に何マス動けるか」の情報を持たせればよいので、「連続する床の枚数を数えながら盤を歩き、壁にあたったら折り返して各床に数字を書き込む」といった真似をすればよいことになります*9。コードは長いわりに中身がないので省略。

あまり綺麗な方法ではないですがちょっと横着して、連続する床の座標をPoint[] buf(Pointはユーザ定義の構造体)に記録し、壁に当たる度にbufに格納された各床に数字を書きに行くといった処理を書きました*10。当然、数字を書いた後はまたbufを空にしなければならないので、buf.clearを実行しますが:

Error: template `object.clear` cannot deduce function from argument types `!()(Point[])`
candidates are:
  `object.clear(T : Value[Key], Value, Key)(T aa)`
  `object.clear(T : Value[Key], Value, Key)(T* aa)`

なんで……？

ちなみにbufの型をSList!Pointにするとbuf.clearでもコンパイルが通ります。通りますし、手元でも動きますが、ジャッジサーバでは全ケース RE *11 *12になります。

どうして…………？

はーーーーーー知らん！！！今日はもうおしまい！！！

おわりに

D言語くん基本的に好きだけどこういう謎エラーたくさん吐くとこきらい。人と仲良くして。

(追記) 解決編です: On Error Resume Next (解決編)

*1:主に研究活動。

*2:逆ギレ。

*3:Time Limit Exceeded。プログラムの実行が制限時間内に終わらなかったことを意味する。

*4:Compilation Error。出直せの意。

*5:というかただの警告ならつべこべ言わずに動いてくれ。

*6:Accepted。正解したという意味。

*7:Wrong Answer。出直せの意。

*8:「指定された段」が昇順で与えられることを利用するならばこの限りでない。

*9:もっと賢い方針もあった。

*10:実際には連続する床すべての座標を記録する必要はなく、連続する床のうち最初の床の位置だけでよいのですが、こっちの方がコードが短くて済みそうだったので。

*11:Runtime Error。出直せの意。

*12:CE だとエラーログ教えてくれるけど RE の場合は教えてくれないので原因もよくわからない。