読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

Codeforces New Entry Crawlerをリリースしました

Web系

Codeforces New Entry Crawlerとは?

Codeforces New Entry Crawler
https://codeforces-new-entry-crawler.herokuapp.com

Codeforcesの新着記事をクロールして表形式・RSSで出力する。
最近、Codeforcesのブログ記事を追うのにはまっていて、RSSで最新エントリーを取ってくるものが欲しかったので作った。
APIが特に無かったので作った。
レポジトリ:https://github.com/hamayanhamayan/Codeforces-New-Entry-Crawler

使ったもの

開発メモ

  • Composerについて調べてからやるといい
  • herokuのphpチュートリアル通り作ればデータベース周りを組み込んで作る流れが分かる
  • Silexが凄い
  • herokuでローカル環境整えるいいやり方ってある?

Codeforces Round #404 問題と解説

競技プログラミング

http://codeforces.com/contest/785

A. Anton and Polyhedrons

http://codeforces.com/contest/785/problem/A
"Tetrahedron"なら4面体, "Cube"なら6面体, "Octahedron"なら8面体, "Dodecahedron"なら12面体, "Icosahedron"なら20面体である。
N個の上の5つの内の立体の種類が与えられるとき、全ての立体の面数の総和は?

B. Anton and Classes

http://codeforces.com/contest/785/problem/B
N個のチェスの授業、M個のプログラミングの授業がある。
各授業で開始時間と終了時間が決まっている。
チェスとプログラミングの授業を1つずつとる時、2つの授業の間の休み時間の最大値は?
(必ずかぶる場合は0とする)

C. Anton and Fairy Tale

http://codeforces.com/contest/785/problem/C
N個収容できる倉庫がある(最初はN個入っている)。
以下の行動が毎日繰り返される時、何日目で終了するか。

(i日目とする)
1. 倉庫からi個取り出す(取り出し切れないor空っぽから終了)
2. M個倉庫に入れる(N個を超える時は満杯のN個が倉庫に入った状態にする)

D. Anton and School - 2

http://codeforces.com/contest/785/problem/D
文字列Sの(非連続OKの)部分列のうち、RSBSである部分列は何通りあるか(mod10^9+7)。
※ RSBS: (),(()),((())), (((()))), ... みたいな文字列

E. Anton and Permutation

http://codeforces.com/contest/785/problem/E
N個の数列があり、中身は{1,2,3, ... ,N}である。
これについてQ個の以下のクエリを処理する。

1. L[i]番目とR[i]番目の要素をスワップする
2. 数列全体について反転数を答える

続きを読む

競技プログラミングにおける連立方程式問題まとめ

競技プログラミング

連立方程式を使った解法について

  • 一次連立方程式を解く
  • ガウスの消去法, 反復法(誤差に注意)のどちらでも解ける
  • 反復法で10^4ループぐらいすれば十分な精度が得られそう?(初期値も適当で大丈夫そう。誤差10^-9以内でもACできた)
  • 漸化式を作った時にDP更新とは違ってループしているようなものは連立方程式を解くかも

問題

yukicoder No.75 回数の期待値の問題

http://yukicoder.me/problems/129

yukicoder No.463 魔法使いのすごろく

http://yukicoder.me/problems/no/463

[多分] SRM504.4 Div1 Hard TheTickertsDivOne

https://community.topcoder.com/stat?c=problem_statement&pm=11098

続きを読む

モデル検査とその手法

研究

モデル検査

システムがある性質を満たすかを形式的に検証すること。
システムはプログラムとか仕様でもいい。
ある性質は活性とか、単にこういう値にならないとか。

以下、よく使われる手法。

帰納法

論文
  • 2011年 Software Verification Using k-Induction

AtCoder Grand Contest 011 解説

競技プログラミング

http://agc011.contest.atcoder.jp

以下、解説

続きを読む

Battle Conference U30 解説

競技プログラミング

http://bcu30.contest.atcoder.jp

以下、解説

続きを読む

yukicoder contest-158 解説 (yukicoder No.490 491 492 493)

競技プログラミング

http://yukicoder.me/contests/159

解説です。

続きを読む