金魚亭日常

読書,ガジェット,競技プログラミング

AtCoder ARC #075 / ABC #065

ARC に出て,Cしか解けず.

Dは,最小全域木の問題. 最小全域木を実装するには,プリム法とクラスカル法があって,解答を見るとみんなクラスカル法みたいだったのでそちらを使ってみた. クラスカル法は,UnionFind木を使う. 実装は,アリ本より.

次回からはまたABC

AtCoder ARC #075 / ABC #065

ImageJ の Python で __name__ が '__builtin__' になる

ImageJ (Fiji) の拡張をJython で書くとき,よくある感じで

if __name__ == '__main__':
  ...

というのを書いてたんですが,突然これやってる拡張が動かなくなりました.

調べてみると,どうやら __name____builtin__ になっているらしい.

一応Forumでも話題が出ており,scijava-common の方の最近の変更が原因らしいですが,どの部分かは不明.

forum.imagej.net

ワークアラウンドとして,

if __name__ in ['__main__', '__builtin__']:
  ...

が提案されてますが,元の挙動が正常なのでなおってほしい.

Google Code Jam Kickstart 2017 Practice Round 2

先日は過去問をやったが,ちょうど練習回があったので参加して見た.

これは,本番形式で過去問を解く,というものらしい.

出典は,

本番だと,入力をダウンロードしてから所定の時間内に解答を提出する必要がある. ソースコードも,提出する.

A

大きい方から小さい方を引く.

B

累積和で解くのだと思って書いて見たが,largeは通らず.

結局,トップの人のを見たところ,

というふうにすると解けるらしい. 考え方としては,下図のようだ.

f:id:what_alnk:20170612233223p:plain

C,Dは時間切れ.

Google Code Jam Kickstart 2017 Round B

Google Code Jam の学生を対象としたやつ? 就職につながる感じなんだろうか.

年中いつでも登録できて,数か月おきにコンテストが開催されるらしい.

とりあえず,過去問を解いてみた

ちなみに,AtCoder などのようにソースコードを提出するのではなく,解答を提出する.

A. Math Encoder

Dashboard - Kickstart Round B 2017 - Google Code Jam

例題を試していたら組合せ数に法則性が見えてきて,

  • ある(最小値,最大値)の組をとる部分数列の個数は,2の累乗

になりそうだったので,それで提出.

large は,素朴に書くと Ruby だと時間がかかって答えが出なさそうだったので,C++に変更. なお,解答を提出するので時間がかかっても答えが出ればよい.

C++ だと最初負の数が出てきて,どうやらオーバーフローしているみたいだと気づき,適宜 109+7 で割った余りを使うように変更.

最終的に,Ruby の方もC++ の解答に合わせて書き直すと速くなった(最初は2の10000乗とか計算していた).

AtCoder ABC #064

A,Bは解けた

Cは,なんで通らなかったか解明できていないけど,解説放送見て書いたら通った. 最初は色数の上限が8だと思ってたけど,違うらしい. 質問タブで複数人質問している人がいて,見ればよかった.

Dは有名問題らしい.

AtCoder ABC #064

Binary Indexed Tree

ARC #075 E より

arc075.contest.atcoder.jp

Index が微妙にずれる気がする…

class BIT
  attr_reader :bit
  def initialize(n)
    @n = n
    @bit = Array.new(@n + 1, 0)
  end
  def sum(i)
    s = 0
    while i > 0
      s +=  @bit[i]
      i -= i & -i
    end
    return s
  end
  def add(i, x)
    i += 1
    while i <= @n
      @bit[i] += x
      i += i & -i
    end
  end
end

AtCoder ARC #075 / ABC #063