ytnk531の日記

日々調べたことを書きます。

日記 久々にプロコン系のプログラムをした

HackerRankでプログラミングをしました。 Dashboard | HackerRank

HackerRankの問題では、入出力系の部分はすでに実装されていて、問題になっている部分の関数やメソッドだけを実装すればいいようになっていました。 PaizaやCodeIQでは入出力系も書かなければいけなかった気がします。
Javaで書く場合、メソッドの引数と返値がたいていはプリミティブ型でした。
プリミティブ型を操作するのは久しかったのでちょっとてこずりつつ、プリミティブ型のストリームの使い方を覚えてみました。

調べたこと

  • IntStream
    • intのStream。Streamはクラスにしか使えないので、プリミティブ型専用のStreamが用意されている。他にLongStream、DoubleStreamがある。
    • mapとかforEachは普通のStreamと特に変わらず使える
    • collectやredumeは引数がちょっと違う。Collectorsがうまく使えない
    • boxedを使うとStreamに変換される
  • StringBuilder
    • char型の要素からStringを作るのに使える
    • (ちょっと使いにくいけど)Stringを反転させるメソッドがある

やったこと

HackerRankの問題を解いて撃沈した

www.hackerrank.com

これに挑戦しました。難易度Mediumがそんなに難しくなかったので、Hard余裕やろって感じでやりました。 計算量の減らし方がまったく思いつかず撃沈しました。

問題

  • 0埋めされた長さnの配列(インデックスは1から開始)が与えられる。
  • m個与えられるa, b, kの組み合わせを使って、配列のaからbに対してkを加算するという操作をm回行う。
  • 操作終了後の配列の中で最大の値を求める。

という問題でした。 細かい制約などは、是非HackerRankの問題ページをご覧ください。

nとmはわりと大きな数をとるので、計算オーダーが大きくなりすぎないように注意が必要です。

愚直なやり方(計算量やばい)

私が真っ先に思いついたやり方を示します。

gist.github.com

ものすごーく単純に、問題文通りの操作をします。 二重for文になっていることからもわかるように、a-b回(最大 n回)の配列操作をm回行うことになります (これはO(n**2)なのでしょうか…時間があれば調べます…)

HackerRankのテストケースを試すと、半分くらいのケースがタイムアウトして失敗してしまいました。 制約では、nとmは大きな数字をとりうるので当然の結果でした…

差分から計算できるようにする

HackerRankには、問題に対して議論できるDiscussionsページがあります。 こちらにとってもクレバーなやり方を示しているかたがいらっしゃいました。

Array Manipulation Discussions | Data Structures | HackerRank

Javaで実装すると以下のようになります。

gist.github.com

全体の流れは、

  • 長さnの配列を用意する
  • ちょっと工夫してqueryを適用する
    • 配列のa番目だけにkを足す
    • 配列のb番目からkを引く
  • 配列から最大値を計算する
    • 変数xに配列のi番目の値を加算する
    • 変数maxとxを比較して、大きければxを新たなmaxとする

といった感じです。

この方法は、用意した配列にクエリの適用結果を記録するのではなく、前の値とどれだけ差があるかを記録します。 そうすると、クエリを適用した配列のi番目の値は差分を記録した配列の先頭からi番目の値をすべて足した値になるというわけですね。

例えば、クエリを適用した結果が

[10,10,10,20,20,0,0]

となる場合、差分の配列を使えば

[10, 0, 0, 10, 0, -20, 0]

という形で表せるというわけです。 この方法なら、m個のクエリに対して必ず2回の操作を行えばいいわけですから、オーダーはO(n)で済むというわけですね。

あっぱれすぎました。世界は広い…。