2019-03-08

RUPCの感想をまったりと書いていく

RUPC2019お疲れ様でした。本当に楽しくて全ての人にありがとうと言いたいです。

そんな私の感想を垂れ流していきます。

自分用に書くので絶対に読まないでください

Day1

行きのバスでけんちょんさん、ツカサさん、おるふぇさんに出会った。出会ってなかったら会場にたどり着けなかったし、その後の色々もなかったと思うと運命だったなぁと思った。

そして会場に着き、

フォローしている人は基本的に全員男性だと考えて生活していたので、本当に女性の競プロerが存在していたことに驚いた。しかも美少女だったのでなんかこうふむふむという気持ちになった。

rspcとして出場しAの実装を担当した後はFの問題をうんうん言いながら考えていました。この長さのコンテストに出たことがなく、とても大変だった。

Day2

起床部門AC。偉い。

KenGoriCideMedaとして出場。Bでしょぼしょぼのミスをし、ペナを積んだ。Iをずっと考えていたが分からなかった。

これはダメだなあと思いながらお菓子を食べているとおるふぇさんがいたのでお話をしてゲーセン行こうぜという話になった。うれしい。

そして懇親会

同席のNadareさんからICPCのSlackがあることを聞き、招待してもらった。とても感謝。来年は絶対に出たい。

同席の人が19卒の方や社会人の方がいて、就活のお話を聞けたのでとてもよかった。とくにらてあさんのお話が印象に残っている。

この人達ともっと分かりあえるようになるためにもっと強くなりたいと強く思った（なんだこの文章、日本語が下手か？）

そして、ゲーセンへ。

つたじぇーさん、てんぷらさん、おるふぇさんと卓球をしました。うらやましいだろ、へへーん。

とても楽しかったなぁ。ありがとうございました。

ほむてんさんはとてもかわいいかったのでかわいいなぁとずっと思っていた。

そして、おるふぇさんとチュウニをした。実は人生初マッチング。せいかちゃんのメイド服ドラマーが印象的すぎて頭から離れない。

ここで気づくcider、帰宅部門TLE。ネカフェ経験はあるのでまぁという気持ちになったが、帰るつもりだったのに終電逃したのは大学生としての自覚が足りないなぁと思った。

ちょうどこのころ、らてあさんが僕のツイートを見てくださったらしく、enblox布教に成功した。いぇい。

Day3

beginnerとして出場。ACDを担当した。Dの実装を無限にバグらせたため、D落ち6完という結果になってしまった。本当に申し訳ない気持ちでいっぱいです。今日は寝るが、絶対にちゃんとバグ取りしてACさせる。

1日目は時間長いなぁと感じたのに、3日目は短いなぁと感じ慣れてきたのかなと思う。

にぼに行った。三郎はお腹にくる。

そしてゲーセン。沢山マッチングをした。楽しかった。ありがとうございました。

そして帰宅。参加記を書くまでがRUPCなので僕のRUPCはここで終わりです。終わってほしくない。

関わる全ての方に感謝の気持ちを述べたいです。本当にありがとうございました。みんな、だいすきだー！

では

2018-07-15

Paiza一日限定問題でうんち💩したお話

解きながら問題整理するために書いてるやつです見苦しいところもあると思いますが、ご容赦ください。

まず、問題はこれ

paiza.jp

↑ログインしないとみられないっぽい

類問をあっとこで見たことある気がするけど覚えてない。

Pが大きいのでPがオーダーに絡まないように解くのがポイントかなぁ

問題の読み替えが重要だよなぁ

O(P^2)なら浮かんだ(は？)

O(NP)が通らないから難しいって話だよねこれ

ん？にぶたんかませばO(PlogN)になるか？

変数名定義

vector<pair<int,int>> single_atack,all_atack //pair<消費魔力,攻撃力>

全体攻撃と単体攻撃を魔力iで出せる最大値を求める(1<=i<=P)
全体攻撃でj、単体攻撃でP-jの魔力を使ったときの倒せる敵の数を求める(1<=j<=P)

1が例えば単体攻撃、魔力iででる攻撃力の最大値をsingle_damage[i]とすると

single_damage[1]=魔力が1の攻撃のうち攻撃力最大のやつ

single_damage[i]=max(single_atack[i-1], single_atackの各要素prのsingle_damage[i-pr.first]+pr.second)

いや、O(NP)やでこれ

確実にTLEやん

ちなみにTLEは3[sec]です。

わからんから、これで提出する

…

え、通った。

実行時間0.01[sec]って書いてあるけど

・1 ≦ N, M ≦ 100

・1 ≦ P ≦ 10,000

・O(NP)

あああああああああああああああああああああああああああああああ！！！！！！！！！！！（ﾌﾞﾘﾌﾞﾘﾌﾞﾘﾌﾞﾘｭﾘｭﾘｭﾘｭﾘｭﾘｭ！！！！！！ﾌﾞﾂﾁﾁﾌﾞﾌﾞﾌﾞﾁﾁﾁﾁﾌﾞﾘﾘｲﾘﾌﾞﾌﾞﾌﾞﾌﾞｩｩｩｩｯｯｯ！！！！！！！）

通るよ！！（怒）

f:id:cider68760155:20180714210808p:plain

はい、一桁見間違えてて、一桁勘違いして覚えてました。

まぁ、これを教訓にすればいいか（泣）

はぁ

教訓

f:id:cider68760155:20180714210757j:plain

【以下解法解説】

上記ステップ２について

各jについてまず、敵の体力をall_damage[P-j]ずつ引いて、それが0以下なら死んでる

1以上なら敵を倒すのに必要な魔力をsingle_damageから求める。lower_boundを使って求める。はじめてにぶたんSTL使ったから勉強になった。

てかこれオーダーO(NPlogN)だよな。関係ないけど。

では、ネタバレ禁止法に基づいて明日の15:00付けで投稿します。てか、今見てる問題のURLが明日404してるかもだしURLだけ張りに来なきゃだな

張りに来た

解説と解法一緒だったなぁ

これもDPの一種なのか

2018-07-08

SoundHound Inc. Programming Contest 2018 -Masters Tournament-に出て

３完までは簡単に行けたはずだったのにcoutの精度でCハマった。辛かった。

Dは上手いことダイクストラに持ち込むのかなぁと思ったけど、ダイクストラをそもそも書いたことがないので険しかったです。復習する価値ありそうだと思ったのでまたやります。ダイクストラは是非自分のものにしていきたいので(初めて知ったアルゴリズムがダイクストラ法っていうのがある。橋本環奈から教わったってinf回言ってる)

一応ギリギリ水パフォだったので良かった

以下総評

A:ばつはエックスです