課題

paizaで公開されている以下の練習問題をbashで解いてみたい。

https://paiza.jp/works/mondai/a_rank_skillcheck_archive/max_range_large

解決策

入力

5 3
1 2 3 2 1

以降は説明のしやすさから上記が入力されることを想定する。

データ正規化

# 入力
5 3
1 2 3 2 1

# 処理
awk '
NR==1 { n = $1; k = $2; }
NR==2 { for (i = 1; i <= k; i++) { print; } }
'

システムからの入力は最初にawkで受ける。引数としてファイル名を指定しない場合は標準入力からデータを引っ張ってきてくれる。

paiza等の競技プログラミングにおいてシステムから入力されるデータはたいてい「正規化」されていない。ここで言う「正規化」とは、各入力行のデータのフォーマットが同一であることを意味する。本問では第一行に日数を表すnとkが、第二行に各日の訪問者数のリストが記述されている。これは「正規化」されていない。 UNIX的なシェルスクリプトでは「正規化」されていないデータは扱いづらいため、いち早く「正規化」することを目指す。

本問での正規化はどのように行うべきであるか。内容的にはk回だけ加算する可能があるため、データをk個に「複製」するという発想をしてみる。

処理をしたあと、nとkの情報は消えておらず、n はデータの列数、kはデータの行数として保存されていることに注目したい。

総和計算の準備（1）

処理
awk '
NR==1 { n = NF; }
{
  for (i = NR; i <= NF;   i++) { printf "%s ", $i; }
  for (i = 1;  i <= NR-1; i++) { printf "0 ";      }
  print "";
}
'

「連続する」k日の訪問者数の総和を求める必要がある。 kはデータの行数として表現されていることを考えると、「連続する」は、各行の先頭位置をスライドさせたうえで列方向に観察するときに表れると考える。

「正規化」した状態を保持するため、スライドにより末尾に発生する空白は、加算しても影響が無いゼロで埋める。

総和計算の準備（2）

# 処理
awk '
{
  for (i = 1; i <= NF; i++) { a[NR,i] = $i; } 
}
END {
  for(j = 1; j <= NF; j++) { 
    s=a[1,j]; for (i=2; i<=NR; i++) { s=s " " a[i,j]; }
    print s
  }
}'

この工程ではいわゆる行列の転置を行っている。転置を行う理由は、たいていのコマンドが行指向だからだ。つまり、加工の対象が行内で完結すると都合が良いので、そのように変換（＝転置）する。なお、ここで言う加工はもちろん加算のことを指す。

総和計算の準備（3）

# 処理
tr ' ' '+'

# 出力
1+2+3
2+3+2
3+2+1
2+1+0
1+0+0

k日の総和を求めるために bc コマンドを用いることとする。 bcは各行ごとの計算式を評価して値を返してくれる。各行に合計するべき数値のリストが空白区切りで並んでいるので、これを加算の記号「+」で置き換えることで計算式を生成する。

総和を求める

# 入力
1+2+3
2+3+2
3+2+1
2+1+0
1+0+0

# 処理
bc

# 出力
6
7
6
3
1

bcコマンドに計算させるのみ。

日付情報を付加する

# 入力
6
7
6
3
1

# 処理
nl

総和の最大値を求めるだけであれば容易である。 sortコマンドにより降順で並び替え、その先頭の要素を取り出すだけで良い。

しかし、本問の解答としては、単純に最大値を返すだけでなく、最大となる候補の数と、候補の最も早い日付を返す必要があり、少しだけややこしい。そこで、ソートすることをベースに、この２つの観点を満たすために小細工する。

まずはnlコマンドを通す。本来の意図としては行番号を表現するものだが、今回の文脈では日付と捉えることができるだろう。

最大値を持つ区間を集約

# 処理
sort -b -k2,2nr -k1,1r

そのうえでソートをしてみよう。ソートの最優先のキーはもちろん総和を表す第二列だ。これは数値の降順としている。次点の優先度として日付を表す第一列を指定する。これは数値の昇順である。

不要な情報を上書き

# 処理
awk '
NR==1 { 
  day = $1; 
}
{
  print day, $2; 
}
'

カウントの常套手段はuniqコマンドであるが、現在の入力をそのままuniqに渡しても何もならない。ここで解答のために必要な情報を改めて整理する。

各「総和」の数を計算すること...①
各「総和」の区間の先頭の日付を取得すること...②

①はuniqの-cオプションで対応できる。ただし、-cは行の重複によるカウントなので、最大数を持つ行の記述を統一しなければならない。現在は第一列の日付が存在するため、これを実現するためには支障がある。

一方で、第一列の日付は、最大数をもつ行の先頭にのみ興味があるので、第一列をすべてこの値で書き換えると、重複のカウントが可能になると気づく。書き換え後の値は、これまでのロジックから入力の第一行第一列に位置しているので、これをすべての行に対して上書きする。

カウントと解答の抽出

# 処理
uniq -c                                          |
head -n1                                         |
awk '{print $1,$2}'

# 出力
1 2

ここまで来たらやることは一本道。 uniqにより各「総和」のカウントを行い、その先頭行（最大カウント値と先頭日付）のみを出力して、本問の解答とする。

この入力例では最大数を持つ区間がひとつのみであったが、複数でも問題なく成り立つ。そのときはuniqが出力するカウント値が1ではない値になるだけだ。

スクリプト全体像

awk '
NR==1 { n = $1; k = $2; }
NR==2 { for (i = 1; i <= k; i++) { print; } }
'                                                          |
awk '
NR==1 { n = NF; }
{
  for (i = NR; i <= NF;   i++) { printf "%s ", $i; }
  for (i = 1;  i <= NR-1; i++) { printf "0 ";      }
  print "";
}
'                                                          |
awk '
{
  for (i = 1; i <= NF; i++) { a[NR,i] = $i; } 
}
END {
  for(j = 1; j <= NF; j++) { 
    s=a[1,j]; for (i=2; i<=NR; i++) { s=s " " a[i,j]; }
    print s
  }
}'                                                         |
tr ' ' '+'                                                 |
bc                                                         |
nl                                                         |
sort -b -k2,2nr -k1,1n                                     |
awk '
NR==1 { 
  day = $1; 
}
{
  print day, $2; 
}
'                                                          |
uniq -c                                                    |
head -n1                                                   |
awk '{ print $1,$2; }'

所感

転職のひとつの手段としてpaizaに興味を持ち、初めて登録してみた。最近はコードやスクリプトを書く機会が減っており、なまっていると思いながらも、bash（シェルスクリプト）で解くことができた。

本問に対するbashでの解法をわざわざ執筆した理由は、UNIX的な考え方を適用してスマートに解答を求められるからだ。つまり、パイプラインを通してデータを次々と加工し、その出口で最終的な解答を得ることができる。アルゴリズム的に最適化された解法と比較すると効率は落ちるが、それはUNIX的な考え方の範疇ではない。

（注意）スクリプト提出時のチェックでは計算時間切れになる入力セットあり

arterminalのブログ

paizaのランクA相当の練習問題をbashで解く

課題

解決策

入力