n-knuu's logs

憧れ駆動。だいたい競プロ

SRM643 div.2 500 / div.1 250 TheKingsFactorization

研究室の練習会に途中参加してdiv2 easyしか解けなかった

問題

TopCoder Statistics - Problem Statement
N(10^18以下)と、Nを素因数分解したときの、全ての素因数を昇順に並べた列(a_1, a_2, ...)のうちprime = {a_i | iは奇数}となる列が与えられる。元の列を復元せよ(Nを素因数分解せよ)。

続きを読む

CODE RUNNER 2015 予選Bに参加しました

CODE RUNNER 2015 予選Bに参加しました。
この記事を2ツイートでまとめると以下のようになります。



結果: f:id:n_knuu:20151102175356p:plain
多分予選通過しました。

続きを読む

SRM644 div.2 1000 TreeCutting

問題*1

  • V頂点の木が与えられる
  • 各頂点vにはnum[v]が与えられる(正の数もしくは-1)
  • いくつかの枝を切断して以下のような木のみが存在する森をつくることはできるか
    • 正のnumをもつ頂点はただ1つのみ
    • その正の数字は木の頂点数と一致する
  • 作れる場合はPOSSIBLE、作れない場合はIMPOSSIBLEという文字列を返す

*1:UnratedになったからかProblem Archiveに問題がなかったが、Arenaにはあった

続きを読む

競技プログラミングにおける動的計画法の情報など

概要

この記事は、競技プログラミング界隈における動的計画法の情報を集めて雑多に並べたものです。自分用に集めていたものを並べただけであり、各記事の内容を保証するものでもありませんし、私も全て読んでいるわけではありません。おそらく、ここに並べている記事を探して理解しようとするよりもプログラミングコンテストチャレンジブック(蟻本)を繰り返し読んだ方が良いと思います。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

ただ、蟻本の内容を理解したうえで、動的計画法の他の人の理解などを見るにはいいかもしれません。

続きを読む

CTF for ビギナーズ 2015 滋賀 に参加しました #ctf4b

概要

CTF for ビギナーズ 2015 滋賀に参加しましたctf4b.doorkeeper.jp
楽しかったです(小並感)
ksnctfの問題を解いたりはしていたが、完全に我流だったので、こういう形で教えてもらえたのはよかった。

続きを読む