2017-12-31
■ 2017年まとめ & 2018年目標
今年を凄く簡単にまとめたいと思います。
1月~3月
基本的に2月末までは受験勉強をした。
センターと2次はどちらも大きなやらかしはなく無事に終わり、東京大学理科3類に入学した。
APMOを受験し、10位で3回目の入賞をした。
3月には情報オリンピックの春合宿でチューターをさせてもらった。
長らく大学受験のせいで心の底から呑気に過ごせる時間がなかったのでこの時期は楽しかった。
4月~8月前半
入学する。何をしようか考え、とりあえず色々やろうということで、
- 東大特進のスタッフ
- ボート
- 水泳
を始めた。
最初のうちは授業もぼちぼち受けていたが意味を感じられなくなったので次第に行かなくなる。(は？)
5月の頭に、地元で行われたプログラミングの大会の副賞でアメリカ(西海岸)に連れて行ってもらう。
7月にはICPCの国内予選があり、Isplpl (僕、yokozuna57、namonakiaccount)で出場して3位を取った。
そして、7月中旬 ~ 8月上旬の間には東医体の新人戦に向けて週6でボートを漕いでいた。
(試験勉強で2h睡眠 -> テスト6時間 -> 夕方3乗艇の日は本当に死ぬかと思った)
結果は4位でしたが、真面目にスポーツに打ち込むこととはどういうことかが分かり、良かったです。
8月後半~12月
東医体が終わったところで大きくやることを変え、
- 競プロ
- 研究室
を始めた(再開した)。
競プロはAtCoderの問題がたくさん残っていたのでそれをひたすら埋め、研究室では病理画像をDeep Learningで分析するやつをやることになりました。
競プロは真面目にやったこともあり、すぐRedCoderに戻れ、さらにコドフェスで9位を取ったり、ICPCアジアでSeoul NUに勝って2位を取れたりしました。(最高)
研究室では今コンテストに向けて方針を考えたりコードを書いたりしているところです。
2018年の目標
以上のことを踏まえ、以下のように目標を据えます：
- SRM, CF レート 2700
- AtCoder レート 3200
- 国内予選かアジア地区どちらかで優勝する
- 研究室でまともな結果を残す
- Deep Learning系で何かいいインターンを探してやる
- 生活リズムをまともにして授業に出る
基本的にやるべきことは最低限に、やりたいことをやりたいだけやっていこうと思います。
来年も1年がんばるぞい！
2017-12-17
■ ICPC アジア地区予選 つくば大会 2017
12/16 (1日目)
7:30に起きてつくばに向かう。自分らしからず(？)かなり余裕を持ってつく。
JAXAの見学をして、namonakiaccountを待って、会場入りしてプラクティスをする。
人生で一度も触れたことがないのである程度覚悟はしていたが、あまりに英字キーボードが打ちづらすぎるのでチーム内でアメリカへの殺意を生やした。
懇親会でひたすらめしを食って、適当にチーム紹介をして、yokozunaとホテルに向かう。
ホテルでは大浴場の風呂がプールになっていること以外トラブルはなく、生活リズム破滅太郎にも拘わらず日付が変わる前に入眠成功した。
(ちなみに日付が変わる前に入眠したのと翌日忙しかったのとあり人生3回目のデレステログイン忘れ太郎をした)
12/17 (2日目)
8:00に起きて会場に向かう。今日は自分らしく余裕が全くない会場入りだったが、namonakiがTLEしたので全チーム内最下位の会場入りをした。コンテスト順位と会場入り順位の差で天下を取れるレベル。
まもなくコンテストが始まる。
まずnamonakiがテンプレをうち、自分がAをやる。しかし何故かバグらせ(は？？？？？？？)、namonakiと交代する。
書き直したらなぜかサンプルがあったので出して、Aを通す。(マジでごめんなさい)
まもなくnamonakiがBを通し、自分がCを通す。
DEFGHIJKについては、yokozunaがEを書き始め、FとKは簡単そう、Dは明らかにやばそう、Gはできそう、HIJはよくわからない、という感じになる。
Eが通り、namonakiがGを書き始める。
yokozunaとIを考え、結構解かれてるしギャグなのかなーって言っていたら本当にギャグでキレる。
WAが出たので一旦交代し、yokozunaがIを、自分がFを書いて通す。Gもすぐにバグが見つかり通る。
ここで残りが難しいDHJKになり、取りあえず書けるDをnamonakiが書き始めて残りをyokozunaと考える。
Hはかなり理解不能、Jはやばい(まぁ誤読してたからなんですけど)、Kは解法が分かっているので実装の仕方を考える。
実はKはlcaを考えるだけで良い(それはそうすぎる)ことが分かるので、途中でnamonakiからパソコンを奪ってKを通す。
Jを捨て、Hに全力投入すると、なんか正しそう、かつO(N^3)のDPが生えるので、yokozunaと2人で実装したりデバッグしたりして残り5分で通る。
かなりテンションが上がってハイタッチをする。チーム戦....最高やな！
コンテスト終了し、おそらく2位か3位だけど見える範囲にいたmolamolaの最後の提出への反応が芳しくなかったのでこれは？？？という気持ちになる。
そして、この直後ホールで統計情報が明かされてしまい9完:1チームで2位が分かってしまう。ウケる。
Jはチームで揃って誤読してた(大反省)、Dは幾何力的に仕方なし、Hはなんで通ったの？って感じだった。
最後に企業ブースが乱立する中での懇親会になりひたすらめしを食い (こいついっつもひたすら飯食ってんな)、適当に交流する。
PFNのブースでiwiさん、wataさんに熱烈な企業紹介をしてもらい、さらに蟻本にサインを書いていただいた。やったぜ。
つくば->駒場->前橋と移動して帰宅。このチームはこれで最後な可能性があるけど結構バランス良かったし良いチームでした。
来年は交流力と英語力と実装力と頭を備えて参加できるよう頑張ります～～～
■ KOMABA FESTIVAL & CODE FESTIVAL 2017
ICPCアジア地区予選の前にこちらを書きます (1ヶ月前なんですけどね)
11/23 (駒場祭0日目)
夕方に東京に行き、大学同期4人で飯を食い、翌日早くに用事がある1人を家に泊める。
夜中に起きて、デレマス4th SSA 1日目のBDの鑑賞会をしてブチ上がる。(Radio Happyは最高)(HoMoは3rdの方が好きかなぁ)
11/24 (駒場祭1日目)
昼から高校同期と食堂で喋ったり駒場祭を周って楽しんだりする。
夕方にいつもの勢で家でまったりした後、渋谷のサイゼでいつもの会をやって無限に騒ぐ。最高。
11/25 (コドフェス1日目)
朝遅く起きて秋葉原に行く。結構すぐにコンテストが始まる。
ABを爆速で通したあと、CとDで無限にバグを生やして人生終了する。
Cはすぐに直るが、Dは嘘解法を無限に投げてしまい嫌な気持ちになる。
いったん辞めてEFGを一通り読むと、Gが一瞬で分かったので書いて通す。
Fは昔このような概念を見たことがあったので、何となくやることは分かるが細部がわからんなぁ、となって飛ばす。
Eも昔こんな感じの問題を出したことがあるのでそんな感じで解けるな、と確信したが、細かい部分が詰まらず実装に入れなかった。
EとFを並列して細部を詰めていくと、Fが分かって通し、するとすぐにEが分かったので頑張って実装して通る。
ここでDに戻ると、貪欲の後にdpをしないといけないことに気づき (は？)、dpを書いて通す。
凍結前で10位だったのでこれは1桁順位ワンチャンか？？みたいな気持ちになる。
ほどなくコンテストが終わり、結果発表があり全体9位国内2位でした。明らかに出来すぎ。
(HIJはほとんど思考できませんでしたが、どの問題も、強いて言うならIがめっちゃ好きです。)
コンテスト後はそこらに生えているおいしいめしを食べ、解説を聞いたりいつもの勢で絵ウルフをしたりする。
国内3位以内に入ったのでDEGwerさんとhogloidさんとエキシビションに出て、1時間頭を抱える担当をしました。
海外チーム(tourist, Um_nik, ksun)(敬称略)が全完していて流石に天才すぎた。
ホテルに向かい、即座に寝落ちする。
11/26 (コドフェス2日目)
朝早く起きたがゆっくりしすぎてタクシーを捕まえて会場に向かうことになった。
朝はトーナメントがあり、1-16位グループにぶち込まれてかなり困惑したが、早解きなので意外と戦えた。(R2で嘘解法に粘着して落ちた)
rngさんのクイズ大会がかなり面白かった。
最後にチームリレーがあり、Shikさん、Reynaさん、ポテチ、reewさん、dnkさん、beetさん、btkさん、hamkoさん、suibakaさんと同じチームになる。
H担当になり、解法で大嘘をつき、終了間際にShikさんに冷静に解法を教えてもらうたのしいたのしいちーむせんでした。(死)
こんな感じです。(1ヶ月前なのでかなり記憶が曖昧)
駒場祭もそれにかこつけて普段会えない仲良い人と遊べたし、コドフェスは純粋に楽しかっただけではなくコンテスト本番でめっちゃいい成績だったのですごく満足でした。リクルートさん是非とも来年もよろしくお願いします。
2017-10-29
■ Codeforces Round #443 Div1
参加してないんですが、ACDEをupsolvingしました。最近のこどふぉらしからず(?)(B以外)どれも結構面白かったので書きます。
A
問題概要
N(<=5*10^5)回、0以上1023以下の値をAND,XOR,ORする。これと等価な操作を5回以内の0以上1023以下の値をAND,XOR,ORすることで作れ。
解法
はじめのi番目のbit(0<=i<10)が0,1だった時、操作を終えた時どうなっているかを見る。
0,1 -> 0,0となっているものは0とのANDで、0,1 -> 1,0となっているものは1とのXORで、0,1 -> 1,1となっているものは1とのORで作れるので実は必ず3回で出来る。O(N)
C
問題概要
N(<=5*10^4)人の人にK(<=10)種類のパラメーターが定まっている。
「ある2人があるパラメーターの値で競い、小さい方が敗北し、消える」
という操作を繰り返す時、1....i番目(1<=i<=N)の人に対して最後の1人になり得る人の数を求めよ。
解法
人i -> 人j iff 人iは人jに勝るパラメーターがある
として有向グラフを作る。
このとき、このグラフをSCCすると任意の2人に対し双方向、あるいは一方向の辺が貼られているのでクリークになり、
かつ全順序が定まっていることが分かる。
よって、一人ずつ追加していくと
どこかに挿入される or 連続した部分列と新規の人が一つの強連結成分になる
が起こるので、setで持って列を管理すると解ける。 O(NK log NK)
D
問題概要
K(<=12)匹の生き物が居て、N(<=10^5)種類のパラメーターが定まっている。
Q(<=10^5)個のクエリが来るので処理してください。クエリは以下の3種類:
- ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのmaxになる生き物を作る
- ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのminになる生き物を作る
- ある生き物のあるパラメーターの値を出力する
解法
2乗を1/64パワーでゴリ押す解法をしたくなるが我慢して考えると、これを思い出す。
2分探索をすることを考えると、値がmid以上 -> 1 otherwise -> 0と変換して、同じ操作をし0か1を見る、ということをすればよいとわかる。
ここで、考えられる0と1のパターンは2^K通りしかないので、2^K通りすべてに対してクエリの順番に操作を行っておくと解ける。O(2^K * Q)
E
問題概要
長さN(<=10^5)の数列aが与えられる。Q(<=10^5)個のクエリに答えよ。クエリの形式は以下の通り:
L,R(1<=L<=R<=N)が与えられるのでa[L..R]に対し
「隣接する2要素を選び(x,yとする)、削除してx+2yをその場所に追加する」
ということを要素が1つになるまで繰り返すとき、最後の値の最大値をmod 10^9+7で求めよ。
解法
2^b_i * a_iの形の値の和になることは明らかで、b_iの条件を考えると
- b_L = 0
- 1<=b_i<=b_(i-1)+1(L
となりそうなことが手を動かすとわかる(未証明)ので、
以下この問題を解く。
b_iをb_(i-1)+1にしない時のことを考えると、明らかに1にするしかないことが分かる。(中途半端な値を取るメリットはないため)
よって、b_iは0,1,2,...,x,1,2,...,y,1,2,...z,...のような階段を繰り返す感じが最適とわかる。
どこで区切るべきかを考えると、
後ろから見たときに負になったところで切るべきで、逆に負になったところで切らないのは最適ではないことが分かるから、
c_i = a_1 + 2 * a_2 + ....+ 2^(i-1) * a_i
とすると、Xが右端の階段は
c_Wはc_Xよりも大きく、かつそのようなWの中で一番右の値(Yとする)が左端になることが分かる。(ないときはL)
よって、c_iをソートし、ダブリングをすると解ける。 O((N+Q) log N)くらい?
2017-09-15
■ みんなのプロコン本選 E - 瞬間移動装置
本番ぶりに考察したら割とすんなり思いついた、良問です
問題概要
N(<=10^5)頂点のクリークからM(<=10^5)本の辺を取り除いたグラフにおいて、頂点cから頂点dに行く時の最短経路をQ(<=10^5)組求めよ。
解法
本質は、次数がN/2以上の頂点同士を選んだ場合答は1か2であることに気づくことです。(そそ)
そして、次数がN/2未満 <=> 補グラフでの次数がN/2より大 よりそのような頂点は高々2*M/(N/2) = 4*M/Nしかなく、
4*M/N <= 2*Nが成り立つのでNの値で場合分けするとそのような頂点は高々1000個くらいしかないことがわかる。
ということは次数がN/2未満の頂点からO(N+M)でBFSして答を前計算してやれば良いとわかる。
BFSのやり方は、バケツソートのような感じで距離が0,1,2....の順に見ていき
「距離Dの頂点全てに対し取り除かれた辺でつながっている頂点に+1した後、未処理の頂点をすべて舐めて今までの加算回数(=距離D以下の頂点の個数)と頂点の値が等しくないなら距離D+1として決定する」
という処理を行えばよい。(未処理の頂点をすべて舐めて良いのは、距離D+1にならない頂点を見る回数は合計で高々O(M)回、距離D+1になる頂点を見る回数は合計で高々O(N)回なので)
以上を実装すると、計算量O(sqrt(M) * (N+M))で通る。
2017-09-05
■ Codeforces Round #432 Div1 E Random Elections
めっちゃ良問だと思ったので書きます
問題概要
n個のbool値を受け取り1個のbool値を返す関数が与えられる。
この関数は「入力をflipすると出力もflipされる」が成り立っている。
今、n人の人間が3人の候補者に対しての3!=6通りの順序を独立にランダムに選ぶとき、
1人の候補者が他の2人に勝つような組み合わせは何通りあるか。
(2人の比較は各々の人間の(AをBよりも好むか)のbool値を関数に与えたときの出力が1ならA,0ならBとして定義される)
解法
答は、出力が1になるような2^(n-1)個のbitmaskのペア(重複を許す)に対し2^(一致している桁の個数)の総和を3倍した値。
計算において高速ゼータ変換の考え方を利用する。
dp[mask][i] = (上(n-i-1)bitがmaskに一致している値に対して、2^(下(i+1)bitでmaskと一致している桁の個数)の総和)
とすると、
dp[mask][i+1] = dp[mask][i]*2+dp[mask xor 2^i][i]
で求まる。
まともな実装で14行とか http://codeforces.com/contest/850/submission/30090122
2017-06-18
■ AOJ-ICPC埋め (2nd)
面白かったのをピックアップします。
鎖中経路 (550pts)
中心&交点を列挙してdijkstraする。辺を貼れる条件の言いかえが結構難しい。
ぼくのかんがえたさいきょうのおふとん (550pts)
dp[mask] = (maskに含まれる布団のぬくもりの和をSとするとき、maskに含まれる布団のあり得る順番すべてに対して需要がS以下の日に対する不快度の和の最小値)とすると通る。
Dictionary (550pts)
色々な意味で難しい。dp[L][R][K] = (L~Rの辞書をK文字目以降で辞書順に並べ替える方法の数)とする。
選挙活動 (600pts)
考えるべき点は(人-多角形の頂点)の直線同士の交点のみ。あとはライブラリを貼ってなんとかする。
ICPC Teams (600pts)
これはかなり難しい、あと良問。余事象を考えて包除原理すると制約がsameだけになるのでできる。
Polygon Guards (700pts)
凹多角形と点の包含関係は偏角の和で判定できるらしい。あとは解の上界を見積もって枝狩り探索。
Towns along a Highway (800pts)
探索木の大きさをO(2^N)にしようと考えると解ける。左右から1つずつ決めていくだけ。
回転と書換 (800pts)
区間DPである区間を文字chに変換できるかを求めたあと、2つの区間を持つDPで徐々につなげていって最大値を求める。
2017-06-14
■ AOJ-ICPC埋め (1st)
競プロ再開します。(今回はマジです。) 最近やった問題のまとめ的なことをします。
Rabbit Party (500pts)
クリークを全て調べて終わりです。(575)
引っ越し (550pts)
http://joisc2011.contest.atcoder.jp/tasks/joisc2011_bookshelf をします。
つながれた風船 (550pts)
高さで二分探索することを考えると、結局N個の円があった時すべての円が含む点が存在するか否かを判定すれば良くなる。
2円の交点と各円の中心を考えれば十分。
夕食 (550pts)
良問。そのままDiv1Medに使えそう。解法は食堂に使うべき順番(Ci+i*pの大きい順)が決まるので、食堂を0個、1個、2個...使う場合の幸福度を順に計算してmaxをとればOK.
Reverse Sort (600pts)
解の上限は9なので、8以下にできるかを考える。区間を選び反転する操作は可逆なことに気づけば半分全列挙のノリですり合わせるだけ。(カンニングしました。)
ほぼ周期文字列 (600pts)
sa+lcpを貼って、Tだけずらした文字列同士に対してグチャグチャやると通る。ハッシュを使った解法の方が綺麗に書けます。
最強の呪文 (700pts)
良問。解法は後ろから見て(dp[v] = (vからゴールに至る辞書順最小の文字列)とする)ベルマンフォードをする。存在しない場合を弾くのが難しくて結局良く分からないまま通してしまった(反省)。
800pts以上はなかなか手がつかなさそうですが国内予選まで頑張りたい。
