2016年11月5日土曜日

DDCC2016 予選

リンク

問題 http://ddcc2016-qual.contest.atcoder.jp/
解説 http://ddcc2016-qual.contest.atcoder.jp/data/other/ddcc2016-qual/editorial.pdf


概要

Aはやるだけ。Bも中学校レベルの数学でやるだけ。writerがchokudaiさんだったので何事かと思ったけど、そういうことか。
Cはkとの関係によって同値類をまとめて全探索可能なサイズに帰着するというアイデアには至ったのだが、kとの公約数すべてを調べるものと思ってしまい重複をうまく扱う方法が分からなかった。
そんなことしなくても最大公約数でまとめるだけで簡単にできた……。
届きそうで届かないギリギリの問題をたくさん解いていくことが上達の近道だと思うので貴重な問題だった。
Dは未着手。

2016年8月29日月曜日

ABC044

リンク

問題・解説 http://abc044.contest.atcoder.jp/ 

概要

A, Bはやるだけ。CはDP。
おそらくだが解説よりも簡単かつ高速な方法で通したと思うので概要を述べる。

1枚目から $i$ 枚目までのカードだけを使ってどのような組み合わせを作れるかを順に求める。
問題設定から、平均がある値になるものだけが重要なので、「狙う平均からの差分の合計」だけを覚えておけば良い。使った枚数は不要。最終的にこの合計が $0$ となるような組み合わせを探す問題となる。

たとえば1つ目の入力例について考えると、狙う平均値は $8$ なので、
  • 1枚目 ($7 \equiv -1$) までを使うと $\{0, -1\}$ (何も取らないと平均が0, 1枚だけ取ると平均が-1になる)
  • 2枚目 ($9 \equiv +1$) までを使うと $\{0, -1, 1, 0\}$
  • 3枚目 ($8 \equiv \pm0$) までを使うと $\{0, -1, 1, 0, 0, -1, 1, 0\}$
  • 4枚目 ($9 \equiv +1$) までを使うと $\{0, -1, 1, 0, 0, -1, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1\}$
となり、全て使った時点で平均が $0$ になっているのは6通り。
ただし、カードを1枚も取らないという手を含むため、その分を引いて答えは5通りとなる。

うまくカウンタのようなものを使うことで全体で $O\left(N\right)$ くらい……のはず。

Dは出来なかった。
$2 \le b \le \sqrt{n}$ は全探索し、 $\sqrt{n} \le b \le n$ は $b$ 進数であらわすと必ず2桁の数になることを使って高速に解ける。
最初解説を聞いてやってみても間に合わずずっと悩んでいたが、unsigned intをlong longに置き換えただけで早くなって通った。いっそPythonで書けばよかったかな。

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時ごろ出発。出演。微妙だった。第一に練習時間が圧倒的に足りなかった。第二にコミュ症だからかもしれない。そのまましれっと抜けて、夜はコンビニで弁当を買いオフィスへ。ためていたタスクを少し片付ける。締め切りが近い。研究も締め切りが近い。

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