naoya_t@hatenablog

いわゆるチラシノウラであります

中央値の中央値 (median of medians)

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。 厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に3n/10個ずつ、それより小さい(or 大きい)値が存在することが示せる。 真のmed…

〈AGC埋め〉AGC 500点問題 (AGC 001 B, 002 C, 010 B, 013 B, 014 B)

日課 400点まで埋めてしまったので500点を埋めた

〈AGC埋め〉AGC B問題 (006-015)

暑いのでAGC埋め。 ABC/ARC/AGCの400点までの全問*1が埋まった。 *1:新スコア体系以降

AtCoder Grand Contest 026

7/14 21:00-23:30oxo--- 2完パフォ1885 レーティング1743→1759(+16) Bも通したかった

〈ABC埋め〉A,B問題埋め

〈ABC埋め〉現行の配点になる前の時代のA,B問題を埋めた。 これでA,B問題のAC率が100%になった。 基本的にPython2で埋めたが 「ABC 019 B 高橋くんと文字列圧縮」は、RLEのスニペットが使えるか試したかったのでC++で通した。 「ABC 034 A テスト」は部分点5…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-(C,D,E問題解決編)

C,D,E問題解決編

ARC埋め状況(7月13日現在)

最近は典型力UPを目指してARC(+AGC+ABC)の過去問ばかり見てる Daily Effortが一箇所ぴーんと伸びてるのはABCの簡単問題を一晩で100ACしたせい ARCのE問題あたりがメインターゲット。(それ以下は梱包のぷちぷち潰し。) AtCoder Problems 先週MacBookを修理…

期待値の線形性(が腑に落ちるまでの長い軌跡)

「期待値の線形性」について、けんちょん先生やふるやん先生の解説を参考にしながら自分の理解を整理するためのメモ。 期待値の線形性そのもの E[ax+b]=aE[x]+E[b] は分かってるし、「E[Σf(x)]の形で書けるものはΣE[f(x)]に書き換えて解ける」という事実にも…

Facebook HackerCup 2018 - Qualification Round

7/7 10am〜7/10 10am JST 予選。72時間の開催期間の好きなタイミングで適当に参加して3問中1問でも通せば良い。(順位は参加のタイミングに依存するもので、QRでは特に意味をなさない) ↑facebookのお友達が参加していると結果が"Friends"スコアボードで見え…

Microsoft Q# Coding Contest - Summer 2018

MSのQ#を使った量子コンピューティングのプログラミングコンテスト(本選)。 週末の3日間で15問を解く。 12完で151位。 量子コンピューティングの授業の演習問題、みたいな教育的な感じだなと思った。 ところどころトリッキーではあるけれど難しすぎるとい…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

7/7 21:00〜コンテストのタイトル長いよそれはさておき 出た MacBook修理中につきレンタル代替機にて。Cで詰まって戦意喪失の2完。 レート激落ちくん 1805→1743 (-62)

Microsoft Q# Coding Contest - Summer 2018 - Warmup

MSのQ#を使った量子コンピューティングのプログラミングコンテスト。 Macに環境入れるのとか面倒で、Warmupラウンドをやってたのは知ってたけどスルーしてた。

〈ARC埋め〉初期ARC A問題

取るに足りない問題だけど やる気の出ない日に埋めるのに良い

〈AGC埋め〉AGC B問題 (002 - 005)

AGC埋め

高速ゼータ変換/高速メビウス変換

ゼータ変換/メビウス変換は互いに逆変換の関係なのはわかったんだけど…どっちがどっち?というか、4種類あるんだけど…どれがどれ?(けんちょん先生が全ての謎を解いてくれるのを待ちつつ)

AtCoder Regular Contest 100

7/1 20:30-22:10(通常より30分早いスタート)ARCの記念すべき第100回。 先週オフィスでMacBookを落として画面が縞々(修理待ち)なので代替機で参戦。 (問題読んでからatomをダウンロードしたりとか)2完(oox-)210位。パフォ1994でレーティング1780→1805。…

SRM735

起きてたのでSRM(追加開催が決まったTCO18 Algo R2Cと同時開催)に参加 touristと同じroom3だった →2完409.95点で37位 1491→1611 (+120) 黄色ワーイヽ(`▽´)/

〈ARC埋め〉ARC 057 C - 2乗根

旧スコア体系(現行のE問題相当)。

〈ARC埋め〉ARC 091 E - LISDL (700)

今夜もE問題に挑戦

〈ARC埋め〉ARC 058 E - 和風いろはちゃん / Iroha and Haiku (700)


1から10までの数がN(≦40)個並んだ10^N通りの数列の中に、部分列の和が5,7,5(あるいはそれに代わるX,Y,Z)になっている区間があるパターンがいくつあるか数え上げる問題。DPしたんだけどサンプルケース#3,#4で答えが合わないまま時間切れ。

〈AGC埋め〉B問題集中アタック(022-)

AGCも埋めていこう

AtCoder Regular Contest 099

6/23 21:00〜22:40 2完(oox-)219位 1741→1780 (+39; パフォ2051)

〈ARC埋め〉D問題集中アタック(残りの500点・600点のやつ:ARC 069,067,066,064,060 D)

途中まで書いたやつがネットのエラーで消えた… 家のネット最近不安定だ(DNSにアクセスできず名前解決できなくて気づく)気を取り直して ARC D問題の残ってるやつ(500点・600点のやつ)を粛々と埋めていく。

ABC A/B問題のWA原因リスト

水曜深夜の比屋定先輩タイムまですこし時間を持て余したので、ABCの不出場回のA/B問題*1を埋めていった。 使用言語: Python2 (2.7.6)*2 エディタ: 問題ページのフォームに直接書き込み*3 これで現行のスコア体系になってからのABCはD問題1つ*4を残して全部埋…

〈メモ〉AtCoderでnumpyを使う

ABCのA,B問題埋めをpythonでやってて AtCoderはnumpyが使えることを知ったのでメモ ABC 047 B - すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit) (200) (問題文はこちら)

〈ABC埋め〉C問題+D問題集中アタック

ABC単独開催回のC問題・D問題を解いておく

〈ARC埋め〉D問題集中アタック(続き:071 - 056)

引き続き埋め

〈ARC埋め〉ARC 072 D - Alice&Brown (500)

「二人とも最適にプレイすると仮定した」系のゲームが苦手すぎるのでじっくり考えた回。こういうのが考えられるようになったら色1つぐらい上がる気がすると思うぐらい苦手だ……なんでみんな自明なことみたいに考えられるんだろう。

〈ABC埋め〉C問題集中アタック (089 - 051)

出場していない回のC問題を解く。C問題は解けないことはないんだけど、解説を読むと「もっと簡単に書ける」みたいな気づきがたまにある。

〈ARC埋め〉D問題集中アタック(093 - 073)

D問題埋め(随時更新)