マンガ版「エンジニアでも恋がしたい！」〜転職初日にぶつかった女の子が同僚だった件〜｜paizaオンラインハッカソン4 Lite

ものすごい頭が痛いタイトルだ。こういうことをするから「プログラマ=アニメ好き」と勘違いされるのではないだろうか。

いや、私以外のプログラマはアニメが好きなんだろうか。いや、アニメ好きでなければプログラマとは言えないのであろうか。

いやぁ、でも攻殻機動隊SACは面白いし(∌GIG)、魔法少女隊アルスもなかなか面白い、でもまぁNiea_7が一番かな。あっ。

ということで、「マンガ版「エンジニアでも恋がしたい！」〜転職初日にぶつかった女の子が同僚だった件〜｜paizaオンラインハッカソン4 Lite」を解いてみたので記録として残しておく。

通常のpaizaはアカウント登録が必要になるがこれはアカウント登録が不要な様子(メールアドレスは必要)。そして、解答はブログに掲載しても良いとのことなので一応掲載しておく。私はPythonで解き、アルゴリズムもわからなかったので自己流になる。

プレゼントのラズベリーパイは初期版を未開封で放置しているし、ねるねるねるねは食べないが120個は魅力だ(10個入り1ダース、10個セットと表記がまばらだがどっちなんだろう)。

プログラムはこうして作られる―プログラマの頭の中をのぞいてみよう

ということで私の解答。問題はサイトを参照して欲しい。

一問目

print sum([input() for i in range(input())])

二問目

print sum([(line[0]-line[1])*line[2] for line in [map(int, raw_input().split()) for i in range(input())] if (line[0]-line[1])>0])

三問目

(cell_length, block_length, sums, max_size) = map(int, raw_input().split()) + [[0,0], 0]
[sums.append(sums[-1]+i) for i in [input() for i in range(block_length)]]
print reduce(lambda a,b: max(a, sums[b+cell_length]-sums[b]), range(len(sums)-cell_length))

こんな感じ。

一問目と二問目は見たまんまのコードかと思う。一問目は入力をそのままリストにしてそれを合計する。二問目は入力をリストにしたものをループで回して在庫のほうが少なければ差分を値段とかけたリストを作り合計する。

わざわざワンライナーのリスト内包表記にしてるのは、paizaのPythonが糞遅くて真面目にforで配列に追加していくとそれだけで非常に時間がかかるためそうする他ない。一問目二問目なら真面目にコードを書いても問題ないかと思うが、三問目はそうはいかないだろう。

三問目を解くには専用のアルゴリズムがあるようだが、私はアルゴリズムが全くわからないので自分で考えるほかなかった。最初はクソ真面目に頭からcell_length(区間長さ)分を加算してみたが、やはりそう簡単に問屋は卸してくれずにタイムアウト(15秒)した。

なので一晩考えて、一コマ毎に区間の総計を計算するのではなく、全コマを順に加算しておいたリストから、区間長の間を取ったセル同士の差分が区間長における合計であることを思いついてそれを一コマ毎にぶん回して最大を取る。Pythonでreduceは初めて使ったが、Python3では無くなっているようだ。残念。

今思うと区間長のリストを新たに作り最大をとっても良かったかも知れない。これであれば二行に省略できたし、更に無理すれば三問目もワンライナーに出来る。速度のために調整なので無理にワンライナーにする必要ないが(三問目の1行目は無理やりワンライナーにしているが)。

これで三問目の大規模データ(テスト4、テスト5)でもPythonで2秒以内に解答が出るようになったので上等だろう。

リストを加算と操作で二周するので少々無駄があるようにも思えるが、他の方の解答が出るまでどんなアルゴリズムがあるのかもわからない。誰か知っている方がいれば教えて欲しい。

とにかくpaizaのPythonが遅いのはどうにかならないだろうか。他の言語でも試してみたが、Pythonだけずば抜けて遅いように感じる。Cではそこそこ速く解ける。

久しぶりにpaizaを見ると対応言語が増えているが、Objective-CやBash、VBで解いたところでプログラミング能力が問えるというのだろうか。それで提出するのは悪ふざけの他はないだろう。paizaは転職のスキルチェックとしてのプログラミング能力を計る問題のはずだが、その問題をプログラミング能力の測れない問題で解いても意味があるようには思えない。