2019-07-07

AtCoder ABC #133 D - Rain Flows into Dams

反省

二分探索で解けると思ったが、上限下限が決定できるような問題じゃなかった。

解説

$X_1 = S - (X_2 + \dotsc + X_N) = S - 2(A_2 + A_4 + \dotsc + A_{N-1})$

に気づけたら実装は簡単。

fn solve(aa: &[i64]) -> Vec<i64> {
    let s = aa.iter().fold(0, |sum, i| sum + i);

    let x1 = s - 2 * aa.iter().skip(1).step_by(2).fold(0, |sum, i| sum + i);

    let mut ans = Vec::new();

    aa.iter().fold(x1, |x, a| {
        ans.push(x);
        (a - x / 2) * 2
    });

    ans
}

しまった、step_by()はRust 1.28からだった。。。

fn solve(aa: &[i64]) -> Vec<i64> {
    let s = aa.iter().fold(0, |sum, i| sum + i);

    let x1 = s - 2 * {
        let mut acc = 0;
        for (i, &a) in aa.iter().enumerate() {
            if i % 2 == 0 {
                continue;
            }
            acc += a;
        }
        acc
    };

    let mut ans = Vec::new();

    aa.iter().fold(x1, |x, a| {
        ans.push(x);
        (a - x / 2) * 2
    });

    ans
}

2019-07-06

AtCoder ABC #131 F - Must Be Rectangular!

AtCoder AtCoder ABC AtCoder 600点 Rust ABC#131

AtCoder Beginner Contest 131 - AtCoder

反省

UnionFind木使うとかどうやったら思いつくんですかね…。

解説

参考: AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録

fn solve(xys: &[(usize, usize)]) -> usize {
    let n = xys.len();
    const MAX: usize = 110000;

    let uf = UnionFind::new(MAX * 2 + 1);

    let mut mx = vec![0; MAX * 2 + 1];
    let mut my = vec![0; MAX * 2 + 1];

    for &(x, y) in xys.iter() {
        uf.unite(x, y + MAX);
    }

    for i in 1..(MAX + 1) {
        mx[uf.root(i)] += 1;
        my[uf.root(i + MAX)] += 1;
    }

    let mut ans = 0;

    for i in 1..(MAX * 2 + 1) {
        ans += mx[i] * my[i];
    }

    ans - n
}

問題文にある操作が完了すると、長方形のグループがいくつか出来上がることになる。長方形の横の格子点数と縦の格子点数を掛けて（つまり長方形の）元の点の数を引けば、その長方形を作成する際に追加された点の数がわかる。

それを全長方形グループについて行うということは<長方形の格子点数> - Nを計算することになり、これが最後のans - nとなっている。

後は長方形グループを探せばよい。座標(x, y)をxとy+MAXの無効グラフとしてUnionFind木に登録していくことでこれを構築することができる。

mx[i]にはiをrootとする長方形グループに属するx座標の数、my[i]には同様にy座標の数が格納されるためmx[i] * my[i] で長方形に含まれる格子点の数が得られる。なお、iをrootとする長方形グループがない場合はmx[i] * my[i]は0となる。

2012-03-18

Play2.0のIterateeを理解したい

Scala Play2.0

Play2.0がついにリリースされました。早速ダウンロードしてかねてより興味のあったWebSocketで遊んでみようとしたところIteratee/Enumeratorなるものにぶち当たりました。
とりあえずソースを見てみるもののさっぱり理解できず、google先生に泣きついたところどうやらHaskellから来た概念のようで日本語の解説としては以下のページを教えてもらいました。

iterateeとは何か、何が良いのか
 Enumerator Package – Yet Another Iteratee Tutorial
使ってみよう Enumerator

現時点での理解をもとに簡単な関数から初めてPlay2.0のIterateeに迫ってみたいと思います。

Inputとstep関数

Iterateeは「入力を受け取り何かをする」ということを抽象化したものだそうです。
というわけでまず入力を表すInputを作ってみました。

sealed trait Input[+E] {
}

object Input {
  case class El[+E](e: E) extends Input[E]
}

次に計算結果を表すInt型の変数とInput[Int]を受け取って何かする関数stepを考えます。
例えばこんな感じ、

def step(result:Int)(in:Input[Int]):Int = in match{
  case Input.El(e) => {println(e); result + e}
}

入力を表示して、計算結果に足し合わせて返すだけです。
以下のように使えます。

scala> var res:Int = _
res: Int = 0

scala> res = step(res)(Input.El(1))
1
res: Int = 1

scala> res = step(res)(Input.El(2))
2
res: Int = 3

scala> res = step(res)(Input.El(3))
3
res: Int = 6

さすがに返される計算結果をいちいち変数に入れるのは格好悪いので、foldLeftを使ってみます。

scala>   val l = List(1,2,3).map(Input.El(_))
l: List[MyIteratee.Input.El[Int]] = List(El(1), El(2), El(3))

scala>   l.foldLeft(0)((r, e) => step(r)(e))
1
2
3
res7: Int = 6

かなりすっきりしました。

Iteratee登場

しかしまだ不満があります。そもそも、計算結果をいちいち外に返してしまうのはよろしくない感じなので、stepの実行と計算結果をワンセットで保持するIteratee[E,A]を定義します。
IterateeはInputを引数にとってstepを駆動し、Iterateeを返すメソッドfeedを持つものとします。

trait Iteratee[E, A] {
  def feed(in:Input[E]):Iteratee[E,A]
}

先ほどのstepをIterateeを返すようにして、さらにstepを内包する形でIterateeを作成してやるとこうなります

val it:Iteratee[Int,Int] = new Iteratee[Int,Int]{
  def step(result:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
    case Input.El(e) => {
      println(e)
      new Iteratee[Int, Int]{
        def feed(in:Input[Int]):Iteratee[Int,Int] = 
	  step(result + e)(in)
	}
      }
    }

  def feed(in:Input[Int]):Iteratee[Int,Int] = 
    step(0)(in)
}

stepが呼ばれるとこの次に実行するstepを含むIterateeを新たに作って返すのがポイントです。
実行してみます。foldLeftの初期値として上で作ったitを渡しています。

scala>   val l = List(1,2,3).map(Input.El(_))
l: List[MyIteratee.Input.El[Int]] = List(El(1), El(2), El(3))

scala>   l.foldLeft(it)((res, e) => res.feed(e))
1
2
3
res1: Iteratee[Int,Int] = $anon$1$$anon$2@3e1dfb2

Iterateeが計算結果を返せるようにする

計算結果をいちいち外に漏らさなくなったのは良いのですが、計算結果に全くアクセスできなくなってしまいました。
計算を終えたら結果を取得できるようにしてみましょう。入力の終わりを表すInput.EOFを定義して、Input.EOFを受け取ったらrunというメソッドで計算結果を受け取れるようにします。

sealed trait Input[+E] {
}

object Input {
  case class El[+E](e: E) extends Input[E]
  case object EOF extends Input[Nothing]
}

次にIterateeです。

trait Iteratee[E, A] {
  def feed(in:Input[E]): Iteratee[E,A]
  def run(): A
}

val it:Iteratee[Int,Int] = new Iteratee[Int,Int]{
  def step(result:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
    case Input.El(e) => {println(e);
      new Iteratee[Int, Int]{
        def feed(in:Input[Int]):Iteratee[Int,Int] = 
	  step(result + e)(in)
	def run() = this.feed(Input.EOF).run()
      }
    }
    case Input.EOF => {
      new Iteratee[Int, Int]{
        def feed(in:Input[Int]):Iteratee[Int,Int] = 
	  sys.error("diverging iteratee after Input.EOF")
	def run() = result
      }
    }
  }

  def feed(in:Input[Int]):Iteratee[Int,Int] = 
    step(0)(in)

  def run() = this.feed(Input.EOF).run()
}

Input.EOFを受け取る前にrunが呼ばれた場合は一端thisにInput.EOFを渡した後で、runを呼ぶようにしています。

fold導入

上で書いたstepを見てもらうと、Input.ElとInput.EOFを渡したときで異なるIterateeを作って返しています。
それぞれ、「計算中の状態」と「計算終了の状態」を表していると考えることができます。

ここで少々天下りですが、Iterateeに状態ContとDoneを導入します。Contはまだ計算中であることを表し、Doneは計算が終了したことを表すこととします。
さらにメソッドfoldをIterateeに持たせます。foldはcontとdoneというそれぞれ状態がContだった時、Doneだった時に実行する処理を与えることができます。

trait Iteratee[E, A] {
  def fold[B](done:(A, Input[E]) => B,
              cont:(Input[E] => Iteratee[E,A]) => B): B
  // ...
}

doneの型はさておきcontの型はstepを駆動させることが想定されています。

Condはfoldでcondが実行される状態、Doneはdoneが実行される状態と考えると、それぞれの状態を作り出すobjectは次のように実装されます。

  object Cont{
    def apply[E, A](k: Input[E] => Iteratee[E, A]): Iteratee[E, A] = new Iteratee[E, A] {
      def fold[B](done: (A, Input[E]) => B,
		  cont: (Input[E] => Iteratee[E, A]) => B
		  ): B = cont(k)
    }
  }

  object Done {
    def apply[E, A](a: A, e: Input[E]): Iteratee[E, A] = new Iteratee[E, A] {
      def fold[B](done: (A, Input[E]) => B,
		  cont: (Input[E] => Iteratee[E, A]) => B): B = done(a, e)
    }
  }

なんか狐にでもつままれたような感じですが…関数型言語すごいよ関数型言語
Iterateeのfeedやrunはfoldで書くことができます。

  trait Iteratee[E, A] {
    def fold[B](done:(A, Input[E]) => B,
		cont:(Input[E] => Iteratee[E,A]) => B): B

    def feed(in:Input[E]): Iteratee[E,A] =
      fold( (a,e) => Done(a,e),
	   k => k(in))

    def run():A =
      fold((a, _) => a,
	   k => k(Input.EOF).fold( (a1, _) => a1,
				  _ => sys.error("diverging iteratee after Input.EOF")))
  }

入力を足し合わせるIterateeは次のようになります。

  val it:Iteratee[Int,Int] = {
    def step(state:Int)(in:Input[Int]):Iteratee[Int,Int] = in match{
      case Input.El(e) => {println(e); Cont(i => step(state + e)(i))}
      case Input.EOF => { Done(state, Input.EOF)}
    }
    Cont(i => step(0)(i))
  }

foldを導入することでここまでスッキリ書くことができるようになりました。

今回はここまで。Enimerator/Enumerateeについては後日（書けたら）書こうと思います。

最後に今回のコード全体を掲載しておきます。なんちゃってEnumeratorが実装されてますが、単にfoldLeftを実行するだけのものとなっています。

2011-12-21

Scala Advent Calendar jp 2011: トレイトと自分型で簡単！コード分割

Scala

Scala Advent Calendar jp 2011の21日目の記事です。

最初に

『Scala実践プログラミング』に記載されていたCakeパターンの解説を読んで自分型の威力を思い知り、自分でも簡単な例で実践してみました。

お題となる分割前のコードはこんな感じ。黒い四角がjkhlキー押下で上下左右に動くだけのswingアプリです。

import scala.swing._
import scala.swing.event.KeyTyped
import java.awt.Color

object Main extends SimpleSwingApplication{

  def top = new MainFrame{
    val panel = new Panel() {

      object Block{
        private var (px,py) = (0,0)
        def x = px
        def y = py
        def down(){ py-=1 }
        def up(){ py+=1 }
        def right(){ px+=1 }
        def left(){ px-=1 }
      }

      val blockSize = 10
      focusable = true
      peer.setPreferredSize(new Dimension(200, 200))

      override def paintComponent(g:Graphics2D){
	super.paintComponent(g)
	g.setColor(Color.BLACK)
	val (startx, starty) = (5,5)
	  g.fillRect((startx + Block.x) * blockSize, (starty - Block.y) * blockSize,
		     blockSize, blockSize)
      }

      listenTo(keys)
      reactions += {
	case KeyTyped(_,'h',_,_) => Block.left();repaint
	case KeyTyped(_,'j',_,_) => Block.down();repaint
	case KeyTyped(_,'k',_,_) => Block.up();repaint
	case KeyTyped(_,'l',_,_) => Block.right();repaint
      }
    }
    contents = panel
  }
}

Panelのインスタンスにほぼすべてのコードが入っていて、結合度が高い状態です。
このコードをトレイトと自分型を使って分離していきます。

Modelの分離

まずはobject Blockをtrait Modelに入れてobject Mainの外に出してやります。

trait Model{
  object Block{
    private var (px,py) = (0,0)
    def x = px
    def y = py
    def down(){ py-=1 }
    def up(){ py+=1 }
    def right(){ px+=1 }
    def left(){ px-=1 }
  }
}

PanelのインスタンスにMix-inしてやればコードの他の部分からもBlockオブジェクトは以前と同様に参照可能です。

val panel = new Panel() with Model {
  // Blockを参照するコード
}

Controllerの分離

次に入力の部分もトレイトでくくり出してobject Mainの外に持って行き、panelにMixinします。

trait Controller{
  listenTo(keys)
  reactions += {
    case KeyTyped(_,'h',_,_) => Block.left();repaint
    case KeyTyped(_,'j',_,_) => Block.down();repaint
    case KeyTyped(_,'k',_,_) => Block.up();repaint
    case KeyTyped(_,'l',_,_) => Block.right();repaint
  }
}

コンパイルしてみると、

[error] /Users/papamitra/src/scala/cake_tutorial/main.scala:20: not found: value listenTo
[error]   listenTo(keys)
[error]   ^
[error] /Users/papamitra/src/scala/cake_tutorial/main.scala:21: not found: value reactions
[error]   reactions += {
[error]   ^
[error] /Users/papamitra/src/scala/cake_tutorial/main.scala:21: reassignment to val
[error]   reactions += {
[error]             ^
[error] three errors found

おっと、コンパイルエラーです。Blockや、Panelのメンバであるreactions,listenToが参照できない為です。

そこで登場するのが自分型です。
自分型としてComponent(Panelの親クラス)とModelを指定すると、あたかも自身が指定したクラスであるかのように参照が解決されます。
そのため先ほどの参照エラーは回避されるようになります。

trait Controller{
  self: Component with Model =>  // 自分型の指定
  listenTo(keys)
  reactions += {
    case KeyTyped(_,'h',_,_) => Block.left();repaint
    case KeyTyped(_,'j',_,_) => Block.down();repaint
    case KeyTyped(_,'k',_,_) => Block.up();repaint
    case KeyTyped(_,'l',_,_) => Block.right();repaint
  }
}

これで入力部分も分離できました。後はModelのときと同様にPanelにMix-inしてやればOKです。

val panel = new Panel() with Model with Controller{
  // 省略
}

Viewの分離

続いて表示部分を分離します。blockSizeはPanelインスタンス生成時に決定できるよう抽象メンバとしました。
Controllerと同様に自分型としてComponentとModelを指定してやります。

trait View {
  self: Component with Model =>

  def blockSize:Int

  override def paintComponent(g:Graphics2D){
    super.paintComponent(g)
    g.setColor(Color.BLACK)
    val (startx, starty) = (5,5)
    g.fillRect((startx + Block.x) * blockSize, (starty - Block.y) * blockSize,
	       blockSize, blockSize)
  }
}

しかしこのコードはコンパイルエラーとなります。

[error] /Users/papamitra/src/scala/cake_tutorial/main.scala:35: value paintComponent is not a member of java.lang.Object with ScalaObject
[error]     super.paintComponent(g)
[error]           ^
[error] one error found

自分型のsuperを直接呼び出すことはできないのです。
ではどうすればよいか？実は以下のようにして回避が可能です。

trait ComponentTrait{ def paintComponent(g:Graphics2D)}

trait View extends ComponentTrait{
  self: Component with Model =>

  abstract override def paintComponent(g:Graphics2D){
    super.paintComponent(g)
    // 以下省略
  }
}

Componentが持っているpaintComponentと同じシグネチャのメソッドをもつトレイトを作り、Viewがそれを継承するようにします。Viewはそのメソッドをabstract overrideしています。
これでうまく機能する理由はコップ本に書いてあります。(第2版 p.223)

(前略)変わったこととは、abstract宣言されたメソッドでsuperをよびだしていることである。
通常のクラスでは、間違いなく実行時にエラーになるので、このような呼び出しは認められていない。
しかし、トレイトでは、このような呼び出しも成功するのである。
トレイト内でのsuper呼び出しは動的に束縛されるので(中略)、メソッドに対して具象定義を提供している他のトレイトないしはクラスの後で(afterメソッドとして)ミックスインされる限り正しく機能する。

Scalaスケーラブルプログラミング第2版

作者: Martin Odersky,Lex Spoon,Bill Venners,羽生田栄一,水島宏太,長尾高弘
出版社/メーカー: インプレス
発売日: 2011/09/27
メディア: 単行本（ソフトカバー）
購入: 12人クリック: 235回
この商品を含むブログ (46件) を見る

つまり抽象メソッドを持つtrait(ここではComponentTrait)を継承してabstractをつけてオーバーライドしてやれば、具象メソッドを持つクラスを探しだしてsuper呼び出しを成功させるということらしい。
Scalaすごい！！

これでViewの分離も出来ました。最終的にobject Mainは以下のようにすっきりした形となりました。

object Main extends SimpleSwingApplication{
  def top = new MainFrame{
    val panel = new Panel() with Model with Controller with View{
      val blockSize = 10
      focusable = true
      peer.setPreferredSize(new Dimension(200, 200))
    }
    contents = panel
  }
}

まとめ

Scalaではトレイトと自分型を使うことで自由自在に感心事を分離できることがお分かりいただけたかと思います。

以下に完成したコードを上げておきます。
(repaintの位置が気に食わなかったので少し変更してあります)

import scala.swing._
import scala.swing.event.KeyTyped
import java.awt.Color

trait Model{
  self: View =>
  object Block{
    private var (px,py) = (0,0)
    def x = px
    def y = py
    def down(){ py-=1; reflect }
    def up(){ py+=1; reflect }
    def right(){ px+=1; reflect }
    def left(){ px-=1; reflect }
  }
}

trait View{
  def reflect
}

trait Controller{
  self: Component with Model =>
  listenTo(keys)
  reactions += {
    case KeyTyped(_,'h',_,_) => Block.left()
    case KeyTyped(_,'j',_,_) => Block.down()
    case KeyTyped(_,'k',_,_) => Block.up()
    case KeyTyped(_,'l',_,_) => Block.right()
  }
}

trait ComponentTrait{ def paintComponent(g:Graphics2D)}

trait ViewImpl extends ComponentTrait with View{
  self: Component with Model =>

  def blockSize:Int

  def reflect=repaint

  abstract override def paintComponent(g:Graphics2D){
    super.paintComponent(g)
    g.setColor(Color.BLACK)
    val (startx, starty) = (5,5)
    g.fillRect((startx + Block.x) * blockSize, (starty - Block.y) * blockSize,
	       blockSize, blockSize)
  }
}

object Main extends SimpleSwingApplication{
  def top = new MainFrame{
    val panel = new Panel() with Model with Controller with ViewImpl{
      val blockSize = 10
      focusable = true
      peer.setPreferredSize(new Dimension(200, 200))
    }
    contents = panel
  }
}

2011-12-20