唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Pythonワンライナーでpaiza Online Hackathon 4 liteに挑戦してみた

paizaで新しいオンラインハッカソンが出題されていたので挑戦してみました

マンガ版「エンジニアでも恋がしたい!」〜転職初日にぶつかった女の子が同僚だった件〜|paizaオンラインハッカソン4 Lite
今回は簡単な感じだったので、最近以下のスライドを読んでよい機会だったのでPythonワンライナーで解くのに挑戦してみました

pythonワンライナーのすゝめ

Pythonワンライナーの注意点

まったく実用的ではないので注意

以下の記事がわかりやすかったです

闇Pythonista入門(Pythonワンライナーのテクニック集) - Qiita

ワンライナーでは全部のプログラムを1行で書くので、改行とインデントが必要なif, for, whileなどは書くことができない(その他は改行の代わりに;を置けばだいたい書ける)
何ができなくて、代わりにどうするか以下に列挙する

関数定義

defから始まる関数定義は改行とインデントが必要になるのでもちろん使えない
代わりにラムダ式が使えます

ラムダ式の中には式しか入れられないので、代入文やprint文などをいれることができません。
代わりに関数を呼ぶことができるので、グローバル変数の辞書を返すglobals()を使ったglobals().update({key:value})や、sys.stdout.writeなどを呼ぶ必要があります
また複数の式を入れる場合にもタプルやリストで入れるなどの工夫が必要です

条件分岐

複数行のifが使えないので、三項演算子A if condition else Bや、論理演算子A and BA or Bや、演算結果でリストなどの参照先を変えるなどのテクニックが必要になります

ループ

mapや内包表記などが使えると書きやすいです
他にもitertoolsの便利な関数や、ラムダ式再帰などが使えます
ただし再帰回数の上限はデフォルトで1000なのでsys.setrecursionlimitで上限を変えないといけないかもしれません
単純に内包表記の全要素に対してループしたいとかなら、maxminの引数に与えるだけでもよいです

1問目

1行目に要素数、その後の各行に数値が与えられるので総和を答える

入力は標準入力にて以下のフォーマットで与えられます。 
N 
S_1 
S_2 
・ 
・ 
S_N

すべてのテストケースにおいて、以下の条件をみたします。 
1 ≦ N ≦ 100 
0 ≦ S_i ≦ 100 

解答

1行で表示すると読めなくなるので、;ごとに改行しておきます

import sys;
print sum(map(int, sys.stdin.read().splitlines()[1:]))

2問目

現在の在庫数\(S\)が必要な在庫数\(T\)以下のものがあったら一つにつき価格\(P\)で補充する
全部の商品について補充した時の合計金額を答える

入力は標準入力にて以下のフォーマットで与えられます。 
N 
T_1 S_1 P_1 
T_2 S_2 P_2 
・ 
・ 
・ 
T_N S_N P_N

すべてのテストケースにおいて、以下の条件をみたします。 
1 ≦ N ≦ 100 
1 ≦ T_i ≦ 100 
0 ≦ S_i ≦ 100 
1 ≦ P_i ≦ 10,000 

解答

import sys;
print sum(map(lambda x: (lambda y: max(y[0] - y[1], 0) * y[2])(map(int, x.split())), sys.stdin.read().splitlines()[1:]))

3問目

\(n\)個の数列が与えられるので、連続した\(t\)個の数列の総和のうち最大のものを答える

入力は標準入力にて以下のフォーマットで与えられます。 
t n 
m_1 
m_2 
m_3 
... 
m_n 

すべてのテストケースにおいて、以下の条件をみたします。 
1 ≦ t ≦ n ≦ 300,000 
0 ≦ m_i ≦ 10,000

解答

t個の総和に1個ずつ要素を足し引きして各時点での総和を計算していきます
ループの書き方がよくわからなくて苦戦しました

import sys, itertools;
set_global = lambda x, y: globals().update({x: y});
lines = sys.stdin.read().splitlines();
t, n = map(int, lines[0].split());
num = map(int, lines[1:]);
set_global('sum', sum(num[:t]));
print max(sum, t < n and max((((set_global('sum', sum + num[i] - num[i - t]), sum)[1] for i in xrange(t, n)))));

Python 3.3以降だとitertools.accumulateがあるのでもうちょっと短くかけました

import sys, itertools;
lines = sys.stdin.read().splitlines();
t, n = map(int, lines[0].split());
acc = list(itertools.accumulate(map(int, lines[1:])));
print(max([acc[i] - acc[i - t] for i in range(t, n)] + [acc[t - 1]]))

まとめ

Pythonワンライナー初心者なので、パズルとしては結構ややこしくて楽しかったです
ただし、もう二度とやりたくないような気もします

-->