ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

競技プログラミング

SRM 762 Div1 Easy LexicographicPartition

問題概要 community.topcoder.com長さAの数列nを連続部分列に分解する。 ただし、連続部分列に含まれる要素の合計は正にならなくては行けない。 この時、Aの連続部分列を前から長さを見た数列をBとする。 辞書順最小のBを求めよ。 解法 前から貪欲するだけ。…

AGC030 B Tree Burning

問題 atcoder.jp 解説 最初に半時計回りに進むと仮定してよい。(座標を反転させて同じ処理をした結果とmaxを取れば正しい結果が得られる)このとき、最初に反時計周りにi個燃やして方向を逆にしないで進んだあとに各木を燃やす毎に方向を逆にしていくのが最適…

Tenka1 Programmer Contest 2018 D Crossing

beta.atcoder.jpゆるキャン△ 1巻 (まんがタイムKRコミックス)作者: あfろ出版社/メーカー: 芳文社発売日: 2015/12/04メディア: Kindle版この商品を含むブログ (12件) を見る 解法 下の図のように構成すればよい。 ただし N = k(k-1)/2となるようなkが存在…

SRM 736 Div2 Med ReRoll

問題概要 サイコロがN個ある。そのN個の目は配列Aで渡される。 Aのうち幾つかのサイコロを振り直して、その合計値をtargetにしたい。 最小で幾つのサイコロを振り直せば合計値がtargetになる可能性があるか? 解法 sum(A) = targetならば0個 sum(A) sum(A) > …

ICPC 2018 国内予選

ICPC2018 国内予選に出場しました。 チームIQ1 メンバー 吹雪(lrmystp) 睦月(kirito) 夕立(chakku)です。 結果としては学内4位全体22位で予選落ちです。方針としては睦月ちゃんがA解いた後に夕立吹雪でB,Cを倒してその間に睦月ちゃんがD,Eの解法を生やして吹…

Codeforces 488 Div2 D Open Communication

Readforces まず問題文が理解できなかった 問題概要 http://codeforces.com/contest/994/problem/D A君とB君が数字のペアを持っている。A君とB君の数字のペアは共通する数字をちょうど1個含んでいる。 A君とB君はお互いの持っているペアを知らないので、互い…

AOJ 1194 バンパイア

バンパイア | Aizu Online Judge各整数x座標において、どの時間までなら建物があるかを調べればよい。 (このx座標が建物の境界の場合とかに注意。特に座標-r,rとかは危険)あさがおと加瀬さん。 (ひらり、コミックス)作者: 高嶋ひろみ出版社/メーカー: 新書館…

Codeforces #462 Div2C Div1A A Twisty Movement

codeforces.com 問題概要 長さnの数列aが与えられる。 数列aの要素は1,2のどちらか。 区間[l,r](l,rは自由)を1度だけ反転する。 反転した後の数列aにおいて最長の非減少数列の長さを求めよ (非減少数列は に対してを満たすような数列) 解法 この問題は解法が…

SRM723Div1Easy TopXorer

概要 要素数nの配列xが与えられる。 に対してを満たすような配列aに対して の最大値を求めよ 解法 基本的に最大の数の最上位bitを1にして、残った数でそれ以下のbitを1にしていくみたいな気持ち。例えば1100,0100があれば1100->1100,0100->0011にすれば排他…

IQ1のICPC2017 アジア地区ナコーンパトム大会参加記

2017/12/19~25でICPC2017 アジア地区ナコンパトム大会に参加してきました。 チームIQ1はchakku(夕立),kuwa(吹雪),tjake(睦月),shimomireコーチ(提督)の4人で参加しました。 12/19 日本→バンコク 羽田から出発 羽田に早くついたので朝食を食べてた。 吹雪ちゃ…

ICPC2017 アジア地区つくば大会に参加してきたんだよ

12/16~18で行われたICPC2017 アジア地区つくば大会に参加してきました。 大会にはtjakeさん(睦月ちゃん),kuwaさん(吹雪ちゃん)とchakku(夕立)でチームIQ1として参加してきました。 12/16 エクスカーションと歓迎会 エクスカーションはJAXAに行く。午前の部と…

ARC085 D ABS

問題 D - ABS自分の解法はだが解説の方法がだった。 この解説に最初ちょっと納得できなかったのでメモどこで納得が行かなかったかというと「Xがまで取った時,Yはまでとる」という部分がよくわからなかった。 というのは「Xが途中までとって,その後Yがうまく…

Atcoder Beginner Contest 075に参加したよ

ABC075にScalaで参加しました. といってもScalaをScalaらしく書いてないので別にそんなに書くことも無いんですけど... A問題 はい Submission #1681801 - AtCoder Beginner Contest 075 B問題 はい Submission #1683393 - AtCoder Beginner Contest 075 C問…

JAG夏合宿2017に参加してきました

9/22 ~ 9/24にオリンピック記念青少年総合センターで開催されたJAGの夏合宿に参加しましたチームIQ1は全員参加できたので前日IQ1メンバーででました.Day0まで研究室の合宿に行ってて睡眠時間が異常に減ってたので3日間とも睡魔と戦ってた...Day1 僕はA問題を…

ICPC2017 国内予選

まえがき このストーリーはrianの書いたストーリー rian.hatenablog.jp に出てくるIQ1の物語です. IQ1視点のサイドストーリーという形になります 前日談 ~ チーム登録 ~ icpcたいてっく予選には登録が必要である.そして僕らは待っていれば唐突にコーチが生え…

ICPC国内模擬2017

ICPC国内模擬2017にチームIQ1で参加しました メンバーはkuwaさん,すごプロさん,僕で行動指針としては最初3完してあとは適当にって感じを予定してました 開始前 誰も蟻本を持ってきていない←??? TLE本も持ってきてない←まあしょうがないか コンテスト 開始直…

Codeforces #418 Div2 C An impassioned circulation of affection

コンテスト中に解けなかったやつ...Problem - C - Codeforces 概要 文字列sが与えられる.(sの長さ) クエリがq個飛んでくる(q) 各クエリはm()と文字cが与えられる. 文字列sの文字のうちm個をcに書き換えた場合,部分文字列でcのみからなるも文字列の最長の長さ…

ABC060D Simple Knapsack解いたんだよ

問題 D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder dp解 個使用して重さの総和がとなるときの価値の最大値 とする. ここで重さを直接持つと配列に収まらないのでの代わりにを使用することで配列に収まるようにできる 注意点 内部のループは…

RUPCに参加してきました

RUPC2017に参加してきたので参加記を...~前日~ 前日まで大学の友人と旅行をしていたので昼神温泉から中津川まで車に乗せていってもらい、中津川からはrian,葦くんとともに名古屋→京都に行く. 京都でちょっと観光してからホテルに向かおうということで伏見稲…

BCU30に参加したっぽい?

3/11にBattle Conference U30にプロコン枠で参加しました. (行くぞ~) 浜松町から思ったよりも遠くてお昼ごはんの時間がなくなった... のでコンビニを探したがなかなか見つけられなくて日の出駅?の近くでローソン?を見つけてお昼ごはんを買う. https://twitte…

Xmas Contestに参加したっぽい?

クリスマスイブ! とくに予定もないのでXmas contestに参加しました。このコンテストはチームでの参加が許されていたので、すごぷろさんにチームを組んで頂いて参加しました。(開始4分前に突然チームを組もうとお願いする馬鹿の図)https://twitter.com/chakk…

SRM 700 Div1 Easy FindingFriend

問題 TopCoder Statistics - Problem Statement 解法 (2017/4/29:解き直したので下にちょっと付け足す.解法を確認するなら下に追記した部分を読んだほうがよい) leader[i]がfriendPlaceよりも大きい場合、部屋i以降はleader[i]以上のランクの人だけで調整し…

AOJ 1138 Traveling by Stagecoach

解法 拡張ダイクストラを使ってd[現在のノード][使用した切符]を埋めていく。 使用した切符の枚数nはなのでbitで管理すればよい。 Queueにはを入れ距離でソートして取り出せばよい。 計算量は多分くらいだと思う(違ったら指摘してください)... ソースコード …

SRM699 Div1 Easy OthersXor

問題 TopCoder Statistics - Problem Statement要はN個の数字があり入力x[i]にはi番目の数字以外の数字のxorを取ったものが入っている。 入力xを満たすようなN個の数字の組み合わせのうち合計が最小となるようなものを見つけその最小値を求める(ただしそのよ…

技術室奥プログラミングコンテスト#2 C問題 有給休暇を解いたんだよ...

tkppc2.contest.atcoder.jp 解法 二分探索で長さL(実際のコード中では"mid")の連続した1を作るか確認していき、作れる最長の長さを出力すればいい。 ソースコード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i</bits/stdc++.h>

ICPC2016国内予選

ICPC2016国内予選に参加しました。 チームnikkuとして参加し、メンバーはすごプロ(@jken_ull),いしづ(@ish_774),僕でした。結果としてはA,B,Cの3完で97位でした。以下当日の流れです(時間はだいたい。記憶は結構あやふや)16:30 -- 開始 -- とりあえず問題を…

TCO2016Round2C Easy BearBall

TCO2016Round2C Easy BearBallの解き方 問題 N個の点がある。 N個の点から始点と終点を選ぶ方法はN*(N-1)通り。 この全ての始点と終点の組み合わせについて、始点から終点に向かってボールを飛ばしたい。 ただし、点1と点2の間に点が存在しなければコスト1で…

ICPC2016国内模擬Bにでたんだよっ

6/12に行われたICPC2016国内模擬Bにで出ました。 チーム名はnikku,メンバーはすごぷろさん(@jken_ull),いしづ(@ish_774)、僕でした。 開始前(13:20) : 大岡山駅前で宗教勧誘を受けた。「聖書を読んだことありますか」って聞いてきたのでキリスト教とかそのあ…

CodeFestival2015に参加してきたんだよっ!!

11/14~11/15に開催されたCodeFestival2015に参加してきたのでその感想とかをね11/14(Day1) 六本木駅から会場である泉ガーデンプレイスに向かった。地図を見る限り10分で着くはずなのになぜか30分くらい歩いた。会場で名札を貰う。やっぱtwitterIDとか書いて…