[Paiza]二次元累積和やってみた

おもしろそうなのでやってみました。

あらかじめ累積和の二次元配列を作って、インデックスアクセスで値を表示する作戦。
累積和は、まず各rowごとに横方向に 足し算でscanして 横に累積和した配列を作り、縦方向に 足し算でzip でscanするとできるはず。

const scan //: <T>(a: T) => (b : (x : T) => (y : T) => T) => (c : T[]) => T[]
  = acc => f => xs => 
  xs.map(e => acc = f(acc)(e))

const zip_with //: <T>(a : (x: T) => (y : T) => T) => (b : T[]) => (c : T[]) => T[]
  = f => xs => ys =>
  xs.length < ys.length
  ? xs.map( (e, i) => f( e )( ys[i] ) ) 
  : ys.map( (e, i) => f( xs[i] )( e ) )

const add //: (a : number) => (b : number) => number
   = x => y => x + y

const numbereds //: (a : string[]) => number[][]
  = xs => 
  xs.map(e => e.split(' ').map(Number))

const rl = require('readline').createInterface( {input: process.stdin} )

const lines = []
rl.on('line', input => lines.push(input))
rl.on('close', () => {

    const [ [H, W, N] ] = numbereds( [ lines[0] ] )    
    const matrix = numbereds( lines.slice(1, H+1))
    const query = numbereds( lines.slice(H+1) )
    
    const sumScanneds = scan( Array(W).fill(0) )
                            ( zip_with(add) )
                            ( matrix
                               .map( e => scan(0)(add)(e) )
                            )
            
    query.forEach( ([y, x]) => 
                    console.log( sumScanneds[y - 1][x - 1] )
                 )
  }
)

やったね。クリア。

中間配列を作らないやりかた

上のやりかただと、横方向に足し算した中間配列が生成されるので、ちょっとムダかも。
中間配列ができないやりかたを考えてみた。

const scan //: <T>(a: T) => (b : (x : T) => (y : T) => T) => (c : T[]) => T[]
  = acc => f => xs => 
  xs.map(e => acc = f(acc)(e))

const zip_with //: <T>(a : (x: T) => (y : T) => T) => (b : T[]) => (c : T[]) => T[]
  = f => xs => ys =>
  xs.length < ys.length
  ? xs.map( (e, i) => f( e )( ys[i] ) ) 
  : ys.map( (e, i) => f( xs[i] )( e ) )

const add //: (a : number) => (b : number) => number
   = x => y => x + y

const numbereds //: (a : string[]) => number[][]
  = xs => 
  xs.map(e => e.split(' ').map(Number))

const rl = require('readline').createInterface( {input: process.stdin} )

const lines = []
rl.on('line', input => lines.push(input))
rl.on('close', () => {

    const [ [H, W, N] ] = numbereds( [ lines[0] ] )    
    const matrix = numbereds( lines.slice(1, H+1))
    const query = numbereds( lines.slice(H+1) )
    
    const sumScanneds = scan( Array(W).fill(0) )
                            ( acc => e => zip_with(add)
                                                (acc)
                                                ( scan(0)(add)(e) )
                            )
                            (matrix)
            
    query.forEach( ([y, x]) => 
                    console.log( sumScanneds[y - 1][x - 1] )
                 )
  }
)