2016年7月31日日曜日

AGC002

リンク

問題 https://agc002.contest.atcoder.jp
解説 ?


概要

A, Bはやるだけ。
Bちょっと無駄に書いてしまったけど本質的にはあっていたということで。
CはDPで解けるのかと思ったらうまくいかず、「ある簡単な解法があってそれを実装するだけ」というエレガントな問題だった。
あとは手付かず。

2016年7月24日日曜日

ABC042

リンク

問題 https://abc042.contest.atcoder.jp/
解説 http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf

今回から新形式になっている。

概要

A, Bはやるだけ。
Cは繰り上がりなどを巧妙に考えたやや長いコードで通したが、全探索でいけるらしい旨が解説されている。
Dは解説があまりに不親切だが「フェルマーの小定理より $(x!)^{−1} \equiv x^{10^9+5} (\text{mod }10^9 + 7)$ である。」とのこと。全く意味がわからないがこれを一瞬で思いつけるかどうかで解けるかどうかが決まるらしい。数え上げの方法も非自明だと思うが、とくに説明がないので誰でも簡単にわかるようだ。天才たちのゲームはむずかしい。
Beginner Contestを名乗っておきながら初心者のためになるものを作る気がない感を隠さないのはいかがか。

フェルマーの小定理とは、平たく言うと、$p$ が素数、$a$ が $p$ と互いに素な整数としたときに $a$ の $p - 1$ 乗を $p$ で割った余りは $1$ になるということを述べたもの。
$10^9 + 7$ は素数である。またこのことから $2$ 以上 $10^9 + 7$ 未満の整数 $x$ はいずれも $10^9 + 7$ と互いに素であることが分かるし、更にそのことから $x!$ も同じく $10^9 + 7$ と互いに素になることが分かる($10^9 + 7$ と互いに素な整数のみを掛けあわせた結果であることから)。
つまりフェルマーの小定理を使って $2$ 以上 $10^9 + 7$ 未満の整数 $x$ に対して $(x!)^{10^9 + 7 - 1} \equiv 1 (\text{mod }10^9 + 7)$ 、すなわち $(x!)^{-1} \equiv (x!)^{10^9 + 7 - 2}$ となることが分かる。
これで右辺がただの正数による累乗になって式変形が簡単になり、
\[\begin{eqnarray*}
(x!)^{-1} &\equiv& (x!)^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{10^9 + 7 - 2} \times x^{10^9 + 7 - 2} \\
&\equiv& ((x - 1)!)^{-1} \times x^{10^9 + 7 - 2}
\end{eqnarray*}\]
てな感じで漸化式っぽく簡単に計算できそうになった。
…………あれ、解説とちがうなあ。

関係無いけどMathJaxを導入した。
やり方は http://irrep.blogspot.jp/2011/07/mathjax-in-blogger-ii.html に従っただけ。

更に関係無いけど:

このあともうちょっとアホな部分をまともに書きなおしたらPython3でも通った。
$(x!)^{-1}$ を事前計算しておくのを逆順に計算すると簡単。

と、思ったけどPythonにはpow(x, y, z)があるのでそんなことしなくてもいいのか。

2016年7月10日日曜日

ARC056

リンク

問題 http://arc056.contest.atcoder.jp/
解説 http://arc056.contest.atcoder.jp/data/arc/057/editorial.pdf

概要

Aから難しかった……解析的に解いたけど実は場合分けがそんなに複雑でなく大半のケースはシミュレーションで解ける。
B, Dは手付かず。
Cは終了後他の人のコードを見たりしていろいろ頑張ったが最終的に(x + 99) // 100とmath.ceil(x / 100)が同じことをしたいコードなのに後者は浮動小数点数の丸め誤差で動かないという悲しいずれにより撃沈。

2016年7月3日日曜日

ABC041

リンク

問題 http://abc041.contest.atcoder.jp/
解説 http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf

概要

A, B, C: やるだけ
D: N匹のうさぎが競争をした。ある2匹の組についてどちらのほうが早かったという情報がMこ与えられる。全体の順序としてありえるものの個数を答えよ。

D

x_iがy_iより早いという情報をグラフの有向辺と見たときに、トポロジカルソートした結果としてありえるものの個数を答える。想定解法はbit DP。
bit DPというのは集合をキーとするDPで集合をバイナリ列にエンコードするテクニックのことらしい。
「N! は大きすぎるが 2^N は小さい場合,bit DP」がよくあるらしい。
漸化式はdp[S] = sum([dp[s] for s in Sから一つだけを取り除いた集合])みたいな感じだが、制約条件を考慮にいれるとSから一つだけを取り除いた集合をすべてチェックすることにはならない。

2016年5月14日土曜日

2016-05-14 バイバイもう永遠に会えないね

たぶん11時位起床?布団でグダグダしつつ気がついたら昼に。そこの床屋で散髪。結構うまくいったと思う。隣の中華料理店に初めて入ってみた。とくにどうという感想もなかった。おねえさんはかわいかったけど。最後の悪あがきの練習というより暗記を家でして、16時ごろ出発。出演。微妙だった。第一に練習時間が圧倒的に足りなかった。第二にコミュ症だからかもしれない。そのまましれっと抜けて、夜はコンビニで弁当を買いオフィスへ。ためていたタスクを少し片付ける。締め切りが近い。研究も締め切りが近い。

行くかもしれない、と言っていたので「絶対来ないと思っていたよ」と言おうと思っていたが本当に来なかったので拍子抜けした。でも絶対来ないと思っていたので予想はあたった。そうなりますよね。そういう優先順位付けなんだから。はい。

2016年1月26日火曜日

無題

くそでかいワニを飼えるのはお金に余裕がある時だけ。

2015年11月15日日曜日

2015-11-11 可愛い女の子は可愛い

うーん、この日くらいは遡っておくか。たぶんどうにかして早起きしたんだろう。朝から和光。学食で昼食。その後ロードバイクのブレーキとリアディレイラの調整。どうにかそれなりの満足度のものに。若干気に喰わないところもあるが。1時からセッティングして頂いた某先生の講演。某先生から「何かお見せすれば」と頂いたのを見せるものが無いと断ってしまったが無いものを見せるべきであったかもしれない。その後某とすこし仕事のような何か。電車で秋葉原へ移動し例の観劇。何だかんだ気に入ってしまった。その後ごちそうになる。会の様子はいろいろと思うところもあったが、事前情報のせいかもしれない。うまくやりたければうまくやっていけるとは思う。終電で自宅へ。それなりに酔っていたのもあり速攻で寝たとの談。さもありなん。

やはり日をおいてから日記を書くのは良くない。何を考えたかなんて知らない。先週の自分なんて他人だ。