2019年1月27日日曜日

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

リンク

問題 https://nikkei2019-qual.contest.atcoder.jp/
解説 https://img.atcoder.jp/nikkei2019-qual/editorial.pdf


C - Different Strokes

プレイヤは両者ともそれぞれ何らかの規則で料理にランク付けをして、それが高い順に選んでいくということはわかる。どういうスコア付けなのだろうか? 直接スコア関数を思いつくのは少し難しいので、一回比較関数を考えてみる。

料理 $i$ は高橋君が得る幸福度が $A_i$ 、青木さんが得る幸福度が $B_i$ だとする。今料理 $i$ と料理 $j$ の二つを比較して、どちらを取るべきか? まず高橋君の立場で考えると、料理 $i$ を取ると、次に青木さんに料理 $j$ を取られるし、逆の時は逆になることから、 $A_i + B_j$ と $A_j + B_i$ のうち大きいほうを取りたい、ということが分かる。正、負、ゼロのどれかを返すcompare関数風に書くと、 $$ (A_i + B_j) - (A_j + B_i) $$ で比較して降順にソートすればよいということが分かる。

同様に考えると、青木さんの比較関数は $ (B_i + A_j) - (B_j + A_i) $ となり、同じく降順にソートすればよいということが分かる。この二つの比較関数でソートしておいて、先頭から交互に取っていく、ただしすでに取られている場合は当然取れないのでその次の料理を取っていく、というような実装方針で行けそうだ。しかし、重複の検査があるのでちょっと面倒だ。うまくやらないとTLEするだろう。

ここでよく考えてみると、この二つの関数はどちらも同じものである。つまり項の順番を入れ替えると、 $$ (A_i + B_i) - (A_j + B_j) $$ となる。何ということはない、二人とも $ A_i + B_i $ の大きい順に料理を選ぶという単純な操作をしていたのである。不思議だねえ。

2018年4月11日水曜日

Google Code Jam 2018 Qualification Round

リンク

問題 https://codejam.withgoogle.com/2018/challenges/
解説 https://codejam.withgoogle.com/2018/challenges/00000000000000cb/analysis


概要

今回からジャッジシステムが新しくなっており、インタラクティブな問題も登場している。

Saving The Universe Again

SCSCCSSCCSのようなコマンド文字列を、Cを区切りと思って [ S ][ S ][ ][ S S ][ ][ ][ S ] というSがいくつか入った箱の並びと考えるとわかりやすい。
1番目の箱は重み1、2番目の箱は重み2、3番目は4、4番目は8、……という風に考えて、重み1が1つと重み2が1つと重み8が2つと重み64が1つだから合計 $ 1 \times 1 + 1 \times 2 + 2 \times 8 + 1 \times 64 $ ダメージ。
さて、可能な操作は文字列の隣接する2字を入れ替える操作だが、同じ文字を入れ替えても意味がないのでCSをSCにするかSCをCSにするかしかない。後者をあえてやることでのちのちいい結果になることがあるだろうか?ちょっと頭が混乱するが、箱のたとえを使うと、箱に入っているSを左の重みの小さい箱に移動する以外の操作は無意味ということが直感的に分かる(と思うんですけどどうですかね)。
また、こう考えると、一番右の重い箱に入っているSから順番に移すのが最も賢い、つまりgreedyに解ける、ということも直感的に分かる。
なお、どんなに操作を続けても元からSが $ x $ 個あれば最小ダメージは明らかに $ x $ であるので、最初にそのチェックを行ってもよい。上の操作をループで書くときに終了判定を実装する手間が省ける(impossibleでないことがわかっているときは絶対に操作がどこかで終了するので無限ループするだけでよい)。

Trouble Sort

実際にシミュレーションすると $ O(n^2) $ 。しかし、よく考えてみると、この操作を繰り返すと列の奇数番目の要素が偶数番目になることはないということが分かる。つまり、この操作の結果は奇数番目だけを取り出した列をソートしたものと偶数番目だけを取り出した列をソートしたものを交互に並べた列と一致する。これは $ O(n\log n) $ で得られる。エラー位置の判定は $ O(n) $ 。

Cubic UFO

Test Set 1だけ解いた。この制約下では、一つの座標軸に沿って高々45°回転させるだけでほしい結果が得られる。この回転角を $ \theta $ 、影の面積を $ A $ とおくと $$ A = \sin(\theta) + \cos(\theta) = \sqrt 2 \sin(\theta + \frac{\pi}{4}) $$ である。これを $ \theta $ について解いて、回転行列を使って各点を回転させた座標を求めと答えが出る。
ちなみにまじめに計算すると $$ \cos(\theta) = \frac{A}{2} + \sqrt{\frac{1}{2} - \frac{A^2}{4}}, $$ $$ \sin(\theta) = \frac{A}{2} - \sqrt{\frac{1}{2} - \frac{A^2}{4}} $$ という感じで三角関数は消せる。数値誤差的にもこちらの方が望ましいか。
なおこれをやってもサンプル入力に対する出力がサンプル出力と大きくずれ、すごく不安になるが正しいはずと信じて出すと通った。つらかった。


あとはやってない。

2016年12月17日土曜日

dwacon 2017 予選

リンク

問題 https://dwacon2017-prelims.contest.atcoder.jp/
解説 なし


概要

Aはやるだけ。
Bは/([2?][5?])+/にマッチする最長部分列の長さを求める問題なのだが、オーバラップがあるためたとえばPythonの標準ライブラリreだけでは単純に記述することは出来ない(はず)。
具体的には、入力例4を見てみると2???5????に対して225252525とはてなを埋めたときに長さ8の最長列を得られることが分かるが、オーバラップが扱えないと

$ echo '2???5????' | grep -Po '([2?][5?])+'
2???
????

と欲しい部分を見つけることが出来ない。
ここで少し考えると、最長の列を得られるような埋め方というのは「先頭から奇数文字目のはてなは2、偶数文字目は5」またはその逆、のどちらかであることが分かる。
これを使って、この2種類の埋め方で得られる2つの文字列から最長の列を探すだけで全体の最長の列を見つけることが出来る。
Cは貪欲にやる(という言い方であっているのかな)。つまりある搬器にあと2人乗せられる状況で1人乗せるか2人乗せるか迷う必要はなく、常に多い方を乗せればよい。
したがって、各時点で乗せられる限り大人数の団体を優先的に乗せる、というのを繰り返すだけで解ける。
Dは時間内に思いつける気がせず撤退してしまったが、解説している人のツイートなどを見て理解した。
問題は、短くまとめるとn個の寿司を順番に食べるとき、各寿司に「少しスコアが得られる食べ方」と「たくさんスコアが得られる食べ方」があり、「たくさんスコアが得られる食べ方」は全体でm回しか使えず、m回使ったあとに出てくる寿司はどちらの食べ方でも食べられない、というルールでスコアを最大化する問題。限られたm回の使い所を選ぶ方法を考える必要がある。
i皿目まででちょうどm回の権利を使い切るとして最大のスコアはいくつか?というのを前から順番に考えていくと、i + 1皿目を食べるときに「i + 1皿目でm回目の権利を使い切る」ために今までに食べた「たくさんスコアが得られる食べ方」を1回諦める、というのを繰り返して更新していけばよいが、ではどれを諦めるのが良いか?というと2つの食べ方によるスコアの差が一番小さかったものを諦めるのがよい。
これは優先順位付きキューを使うことで効率よく実装できる。
このiの結果を使ってi + 1を求めていく感じ、DPっぽいけどそう呼ぶのかどうかはわからない。
Eはわからず。

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

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

2016年1月26日火曜日

無題

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

2015年11月15日日曜日

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

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

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

2015-11-15 100%の集中を

10時にマイナンバー通知の再配達で起床。布団にこもったり昼食の支度をしていたりしたら出る時間に。よくない。生卵を台所のマットに落としてしまい、へこむ。洗うついでに洗面所の掃除を少しした。図書館に一瞬寄ってから和光。また女性ばかりだった。若干危険を感じる場面があった。終了後そのまま入室。ずっと居たが何も手につかず。Emacsの一部機能 (ewwなど) がうまく動かないのはgebenがopen-network-streamに変なアドバイスを貼っているからということが分かった。11時半すぎ退室。

某がFbでシェアしていたホリエモンの記事 [1] を見てそのとおりだなと思った。ビジネスにかぎらず研究も。集中力のない人間は、何も考えずにテレビを見てゲラゲラ笑いながら人生を終えるしかない……。日記すら続いていないじゃないか?

そういえば某でずっと前からファンだった絵を描く人がじつは商業誌で漫画を描いているということをたまたまTwitterで知った。びっくりした。この間は某Ezアプリの作者をTwitterで見かけたし(これは検索したからだが)、こういう体験は面白い。

[1]: http://ameblo.jp/takapon-jp/entry-10500476221.html

2015年11月1日日曜日

2015-11-01 振り回されるのも

九時過ぎにまた事故で起床したような気がする。その後昼過ぎまで。昼食などを済ませ和光。帰り道で某が女の子を待っているのを見てちょっと可笑しかった。地下周辺で作業しようかと思ったが片手間になった。帰宅要請があったが二転三転で結局無しに。二十三時帰宅。

三たび携帯ストラップがバラけてしまった。困る。一度目は四月に武道館の入口でだった。まだ直していない。そう言えば先週末これがEmacsのロゴに似ていると言われた。三人目。この蜻蛉玉は自作したものだが色のチョイスは完全に某に委ねたのでそういう意図はないのだけど(そもそも言われるまで気が付かなかった)。面白いからいいけど。

2015-10-31 無題

9時半に事故で起床。二日連続。昼からJS。はっきり言って時間の無駄だったのでかなり腹立たしい。森なんとかという人間をクビにして欲しいと思った。話は半分も聞いていない。交通費千円も払って何をしているのか。帰宅後地下で某コンテスト。あまり振るわず。帰り道スーパーに寄りたい気もしたが我慢して帰宅。

2015年10月30日金曜日

2015-10-30 日記を始める

結局やっぱり日記は書きたいなあと思うので日記を書く。どうするのがいいのかわからないので試行錯誤。
とりあえず名前付き実体に通し番号をつけるというアイデアは失敗に終わったと思うのでやめる。わたしの人生にそんなに毎日毎日他者とのインタラクションが無いというところに問題があるのだと思う。問題だと思うわけではないが。

7時事故により起床。14時半くらいまで在室。予想外に早く終わったのでSkypeで画面共有しながら某と仕事。20時ごろまで。いまは22時。いいかげん本業の進捗を得なければならないが時間的リソースを全然割いていないのでよろしくない。
たぶん本業をその他の挿入される用事のない空き時間全て(←!)のうち好きなときにやればいいや、と考えることが結果的に非効率を生んでいるような気がするので、学校の時間割のごとく何曜日の何時から何時はこれに使うと手帳に事前に書いておくのが良い。
必要ならば家族や恋人や同僚を騙しておかなければならない。

2015年10月12日月曜日

今日のweblog

「恋愛童貞」その見抜き方と攻略法 - あの子のことも嫌いです
http://uzuramadoka.hatenablog.com/entry/2015/01/05/225117

わたしが、この人恋愛童貞なのでは……と薄ら思ったときに、確信を持つためにぶつける質問がある。それが
「元カノとはどんなデートしてた?」
だ。これに対して「家で会うことが多かった」という回答は、やや怪しい。
(中略)
ただし、これだけではどちらもインドア派だったとか、共通の趣味がテレビゲームだったとかの可能性も大いにあるので「そのときの食事はどうしてたの?」と尋ねる。
その際に「ほとんど俺が作ってたなあ」との回答が得られれば、9割以上の確率で恋愛童貞だ。 
!!!!!!!!!!!

2015年10月9日金曜日

いくつかの記事を非公開に戻した

自分でもどうしたいのかわからないが、一つ確かなのは某氏の某は予想外であったということ。
意地悪を言うけど普通本人に面と向かって言わないと思う。
どうしたいのやら。

2015年8月25日火曜日

例のプロジェクト

分担うまくできるのか問題だ。
なんたってNLP×Webなので全方位俺のためにあるようなものだし、このままでは「人が考えたテーマで俺が独りで何かを為す」をやってしまうのではないかと不安あんど申し訳無さを感じる。
なんたってNLP×Webなので。

2015年8月20日木曜日

ほげ

例の会
* 普通の意味で面白そう
* 人の金で旅行
* 人脈ほしい
* 先約の方が重要では?
* 自分は何も持っていないのでつらい可能性もある
* 遊んでばかりでいいのか
* seccap休まないといけない
* seccap合法的に休める??

例のカンファ
* リファクタリングしたくない(うまくいく気がしない)
* するって言っちゃった
* それはデータが糞だったことを言えばよいか
* 下に時間を割くべきでは?
* 発展性・将来性の不透明さ
* 性にあっている(自分が世界でも第一人者)

例のプロジェクト
* 興味
* 発展性
* 業績ほしい
* 時間的不安
* らぼ・ぼすとの外交折衝
* メンバー内でうまく分担できるのか?
* 先生がいなくていいのか?