足跡-sokuseki-

りかの日進月歩の記録

topcoder SRM775 参加記

競技プログラミング topcoder

SRMそんなに出ないしすぐ忘れるのでコンテスト参加記を残そうかなあと思ったので（すぐ飽きそう）

前回、初回にして爆死はこちら→wk1080id.hatenablog.com

f:id:wk1080id:20200117023005p:plain
まともにACして早く灰色から脱出したいところ。
直前にtopcoderでのコードの書き方を前回の記事を見ながら思い出す。（提出はmain関数以外全部とか）

div2Easy

長さLで使われる文字がアルファベット最初のS文字であるような文字列のうち、文字列集合forbiddenに属するどの文字列とも完全に違う文字列はいくつあるか。
完全に違うとは、長さNの2つの文字列s,tがあったときに0以上N-1以下のすべてのiについてs[i] != t[i]をみたす。
Sは1以上26以下
forbiddenの要素数は1以上30以下
forbiddenの要素の長さはすべてL
Lは1以上6以下


完全に違うの定義を誤解していて時間をたくさん使ってしまった。
i文字目に使える文字の種類を調べて、それらをかけていけばいい。

div2Med

2次元のマップcaveが与えられる。マップは何もないマス'.'と岩のマス'#'と岩に隠れているkoboldがいるマス'K'のいずれか。
マップでは4方向に移動でき、'.'は連結。
desiredAreaという数が与えられるので、'#'のマスを'.'に変更してマップの'.'の数をdesiredArea個にしたい。
ただし変更後の'.'は連結で、koboldに隣接するマスは'#'でなければならない。
この条件をみたすようにマップの'.'の数をdesiredArea個にしたときにありうる変更後のマップを1つ出力せよ。（そのようなマップが存在しないときは空のvectorを出力する）
マップの縦の長さは1以上50以下
マップの横の長さは1以上50以下
desiredAreaは最初の'.'の個数以上、マップのマスの個数以下

'#'から'.'にできない（koboldと隣接している）マスを初めに調べておいて、あとで足りない個数分だけ色ぬりすればよい。
最初、連結に気づかなくて、変更できる'#'を上から順に塗っていたけど、連結なのでbfsで書いた。
challengeフェーズで部屋の人のコードを読むとみんなdfsで書いてたし前計算とかしてなかった。

div2Hard

Nとindexが与えられる

for sum = 0 .. 3*N-3:
    for x = 0 .. N-1:
        for y = 0 .. N-1:
            for z = 0 .. N-1:
                if x+y+z == sum:
                    visit (x,y,z)

の順でN*N*Nの3次元座標にアクセスするとき、index番目(0-indexed)にアクセスする座標を答えよ。
Nは1以上10^6以下
indexは0以上N^3 - 1以下

わからねー
xがiのときの通り数は(i+2)(i+1)/2なのでそれを使ってO(N)かけてsumを確定させて、そのあとはxを0から順に調べてyを順に調べて…
でできると思ったんだけど、sumを確定させるときのそれは嘘であることが終了直前にわかり、無（x,y,zはN-1以下でないといけないので）

challengeフェーズ

ルームのhard提出が1、med提出が3とかで、無
ルーム内challengeはなかった…

システス

Med落ちたけど
というかルームでMed落ちてるの自分だけ…
（Med落ちたということは、Medの日本語問題文が間違っている可能性があります）

レート

レート変動見るの難しすぎか？一度ログアウトしてログインしなおします。
734 -> 781(+47)
灰色コーダーの旅はこれからだ！〜次回作にご期待ください〜

C++のcomplexで円と線分の交差判定

競技プログラミング AOJ

ある円Cと線分Sの交差判定をします。

定義

円と線分（ここでは直線として管理します）の定義は↓

typedef complex<double> P;

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
  L(){;}
};

struct C {
  P c;double r;
  C(const P &c,double r):c(c),r(r){}
  C(){;}
};

実装

基本的な考え方は、円の中心と線分との距離を見ます。
円Cの中心と線分Sとの最短距離を d_{min} 、最長距離を d_{max} としたとき、
「 d_{min} \le 円Cの半径」かつ「円Cの半径 \le d_{max} 」
を満たすとき、円Cと線分Sは交差します。

以下のコードでは、円と線分の交差判定をintersectCS()、線分と点の距離をdistanceSP()、点と点の距離をdistancePP()で計算しています。（intersectCS()以外は省略）

bool intersectCS(const C &c, const L &l){//円と線分の交差判定
    double close = distanceSP(l,c.c);
    double far = max(distancePP(l[0],c.c),distancePP(l[1],c.c));
    if(close <= c.r && far >= c.r)return true; //重なっていても良い
    //完全に交差している場合のみだと、イコールを外す
    return false;
}

verifyと全体コード

verifyはAOJ0129で行いました。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129
提出したコード：
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4060205

ICPC2019　アジア地区横浜大会　参加記

競技プログラミング 参加記

11/16~18に行われたICPC2019アジア地区横浜大会に参加しました。
ICPC 2019 Asia Yokohama Regional

〜前日

国内予選が終わってから特に何もしてなくて、何もしないまま当日を迎えるのは怖かったので、チーム練は今年のJAG夏合宿の問題で3セットやりました。
ICPCに何年も出ると、チーム練で使える問題が枯渇しがち。

day1

朝から新幹線にのって横浜に。


横浜駅の地下においしい親子丼があったので実質ICPC名古屋！w
（ところで後から知ったんですが、今年のしまじろうコンサートは愛知だったらしくて、縁みたいなのを感じました）（いいえ）



会場についてチームメイトと合流し、レジを済ませる。
他大学チームと久しぶり〜〜〜〜〜をしているとアナウンスが始まって急いで席に戻る。

practiceは4問だった。
forループがどのくらい回るかとか、メモリサイズを確かめたりとか、スタックが無限という話をほんまか？とかいいながらdfs書いたりしてた。
何か印刷しようという話になって、一番美人な人が届けてくださいみたいなことを英語で書いたものをチームメイトが印刷しようとしてた。

practiceが終わって、チーム紹介が始まる。スライドで間違い探しするやつ好き。
去年はカツサンドが配られたけど、今年はカツサンド弁当にグレードアップしていた。

解散したあと、ツイッターの知り合い10人くらいと中華街に行く。



おいしかった。
駅に向かう途中、みんなでタピオカを買う。
初タピオカだったんですが、あまりのおいしさに、感動……
中華街散策したり赤レンガ街に行ったりして青春をする。

ホテルに帰るとABCが終わっていたので、ABCばちゃをしてから就寝

day2

夜景の赤レンガも良かったんですが、夜景じゃないのも見たかったので朝から行く


会場についてチームメイトと合流してから荷物チェックを受けて席に向かう。
筑波の人とめちゃくちゃ喋った。


コンテスト開始5分前にコンテストが始まる。（「こどふぉる」の対義語ってなんですか？誰か教えてください）
とりあえずAを読むことになっていたので、読む。難しい。
考えると「×3」を連続で何回か適用して、「×1/3」を連続で適用するのが最善なので、書く。バグる。
辛い気持ちになりながらデバッグし、pcをBの人に譲る。
Bもつらそう。Bも実装がうまくいかないみたいで、何度かpcを代わったりしているうちに、Bが通る。
Aも実装の仕方をちょっと変えてAC。この時点で1時間ちょっとが経過。
順位表を見て、Hに向かう。Hは括弧列を追加したり削除したりしながらvalidな区間を数えるもの。
削除があるので、構文解析みたいにdfsで探索して削除のときに前の状態にもどれるといいよねってなって、それを書く。
ちょっとバグらせながらサンプルがあったので提出するとREで、確かに添字がごちゃごちゃしてるからな〜とか言って印刷デバッグ。その間にEやGを考えてもらう。
Eができそうらしいので、Eを書いてもらうけど、こっちもやばそうで、サンプルがあわないらしい。
いろいろあって、HのREが配列外参照ではなくスタックオーバーフローが問題(???????)らしいことに気づく（開始4時間過ぎくらい）。再帰を使わないコードに書き換える。投げてAC。
そのままコンテストが終わる。
f:id:wk1080id:20191127182953p:plain

荷物を持って会場を移動。外が寒い。
英語がわからないのでツイッターをして過ごす。眠いなーとか思っていたらyes/noが始まる。
去年は凍結後に提出をしなかったのですが、自分のチームがyesって言われると、嬉しい。


応援していたUKUNICHIAが4位ですごかった。（まだyoutubeの中継みてないので、後で見ます）

コンテストをしていた会場に戻って懇親会。マスコットで交流したり、企業ブースをまわっていろいろもらったりした。
中盤からみんなGoogleの問題に夢中になってあまり話しかけられず………



懇親会が終わった後、2次会でカラオケに行った。


367Daysは「みんなで力を合わせて夢を実現して、そしてこれからもみんなで先を目指して頑張っていく」みたいなテーマの曲で、ICPCみたいなチーム戦の大会にはぴったりの曲すぎる。最高。みんなで力を合わせて国内予選を突破して、そしてみんなで世界大会を目指してほしいね、KiRaReに。

day3

企業見学なので、しながわ水族館に行きます。



イルカショーを見てすげーって言ってた

そのまま水族館の横で昼食

水族館ではしゃいだ結果、疲れ果てたうさぎの図


水族館とても良かったので、次は動物園とかどうですか？
動物園で時間制限あり幸福度最大化問題を解きたいです！！

ご飯を食べて、新幹線で帰る。在来線が事故でストップして帰宅困難になりました。

最後に


廻小宮*1ごっこ、楽しいのでオススメです。

ICPCはB1から今年B4まで出て、今回で引退になるんですが、本当に青春そのものでした。
余裕があればスタッフとして戻って来たいです！ありがとうございました！！

*1:ICPC2019模擬国内予選C https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2946

topcoder SRMに初参加してみた

topcoder登録

難しいと聞いていたんですが、そこまで難しくなかったです

  • topcoderのトップページ右上のcommunityをクリックし、competitive programingの「take me to the coders!」をクリックする

f:id:wk1080id:20191010233111p:plain

  • ページ中部のLaunch Arena(beta)を選ぶ

f:id:wk1080id:20191010233302p:plain

  • ログイン画面になるので、一番下の「NOT A MEMBER YET? JOIN NOW」を押していろいろ入力して登録する

f:id:wk1080id:20191010233605p:plain

  • 送られてきたメールのリンクをクリックして終了です



コンテスト

75分で3問を解いて、それが終わってからchallengeフェーズがあるので、75分間は問題を解くことに集中できます。嬉しい。


指定された名前のclassをつくって、その内部に指定されたmethodを作る必要があります。事前に問題を解いて練習しようね！

class $CLASSNAME$ {
   public:
   $RC$ $METHODNAME$($METHODPARMS$)
  {

  }

};

言語は初期設定はJavaになっているので、変更する場合はコードを書く欄の左上の歯車マークから選択します。


直書きしないでローカルで書いてちゃんとサンプルを試す！（素振り）






SRMさんいままでありがとうございました（完）

ACPC2019（会津大学競技プログラミング合宿2019）参加記

競技プログラミング 参加記

会津大学競技プログラミング合宿2019 : ATND に参加しました。

day0

6時間かけて関西から会津に移動


前泊組で喜多方ラーメンを食べる

ホテルにチェックインしてのんびりする

day1

無料朝食を食べる

早めに大学について学食に行く


会津のソースカツ丼は名物らしい、とってもおいしかったです


自己紹介で老害発言をして、コンテストのジャッジをする


3人でジャッジをしつつ風船配りをするの、体が足りなくて、自分が合宿に参加し始めた頃の北大はすごかったんだなあという気持ちになっていた



10人くらいでステーキを食べに行く
open cupの話がおもしろかった

day2

大学についてすぐチームメイトを確保する
メイドさんになった

コンテストは自明を解いた後は何も貢献できませんでした

懇親会会場までみんなであるいた




メニューはいつものなのではいなんですが、参加者が違うといろいろ面白いことがあって、うくさんがびーとさんに乗り移ったみたいに見えた
お酒を無限に飲んでいる人がたくさんいてすごいなあと思った

day3

day3は朝が早くてつらい
1億年ぶりにランダムチームを組みました、新鮮な気持ちになれて良い


Bを嘘でぱーっと実装してACできたのはいいんですが、DEのバグをとりきれず、Fで蟻本を見ておきながら文字列をくっつけてLCPすることに気づけなくて最悪をしました

学食でお昼を食べて駅まで歩いて、みんなを見送った

day4

観光をしました

まとめ

たのしかったので来年も行きて〜って感じなんですが、来年は社会人で厳しい…………
いろいろな人と話せた気がします、気がするだけです
会津バス北柳原停留所を返して……

ゆるふわ競プロオンサイト #2 参加記

競技プログラミング 参加記

9/14にゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状のオンサイトに参加してきました。

コンテスト前

新幹線に乗りながらオンサイト準備

新宿駅で迷っていたら着くのがギリギリになってしまいました…。会場にはすでに人がたくさんいました。

2時間12問で100点~600点とスピードランみたいなコンテストらしい、開始前にペナがないという話を聞きました。

コンテスト

www.hackerrank.com


時系列順で、

A：ifで分岐するだけだなーと思って下までみたらコードを書く欄があって途中まで書いてあったのでそこに直接書いて出しちゃった。

B：やるだけだったのでこれも直書きした。

C：どの列どの行にも1つだけ白いマスを作ればいいんだなーこれはN!！wとか思って直書きしたらCE出たので手元実行は大事だなあと思いました。次の問題からはエディタで書いてます。

D：n-ドイッチすこ。#の個数をもって、|が連続したら答えにして個数リセット、をした。

E：kameの場所はqiなので気にしなくてよくて、usagiはクエリごとにしゃくとり?っぽくして比較すればいいやーって思った。クエリが昇順なのありがたいなあ。

F：あれ、これクエリ先読みしてしゃくとりか？また？クエリ先読みの練習題？とか思ってたら、各暗唱の文字数を前計算しておいてクエリごとにlower_boundでいいことに気づいた。

G：各クエリで範囲Aを全部ひっくりかえして範囲Bを全部ひっくりかえしても等価なので、ひっくり返した回数を持つ2次元配列を用意して、クエリごとに長方形を2回加算して（加算場所は4箇所*2回）最後に累積和。2次元累積和わすれたのでいもす研をググっちゃったけどよく考えると覚えてた（は？）。回数が奇数のマスの総和を出して終了。

H：ゲーム苦手で実験したくないな…と思っていたら、制約が小さすぎたので、dfsで探索すればいいや！wって思ってたらバグらせた。デバッグ出力とかしてたけど、わからないまま残り時間があまりなかったので後でデバッグしようとして次の問題に進む。

I：なんだこれ…と思ったけど制約の「少なくとも2つは1」を見て、じゃあ各味について少ない人から貪欲にすれば、箱の数にぶたんでできるじゃーんって言って実装した。ピノ食べたことないので、バニラ10アーモンド7チョコ7で固定されてるの意味わかんなくて、これ与えれば良くない？ってずっと言ってた。

J：サイズが大きいので愚直DPはできなくて、500を使うんだな〜となる。DPの遷移は一定なので、これ行列累乗で高速化できるね！とか言ってたんですが、これは実は縦が10^9以下の奇数、横が500だと誤読していて、ずっと合わないなーとか言ってた。誤読していることに気づかなくては？とか言いつつ次の問題を見る。

L：Success Rateを見てKよりLを優先した方が良さそう？と思ってLを開く。なんかWUPCで似たようなの見た（ACはしていない）なあ*1とか思ったけど、わかんないからフローか？とか言ってた。

K：trieだと構築でTLEしそう、じゃあSAか？とか思って考えてたんですが、存在しなくて自分より後ろを調べるときに愚直に1つずつ見る以外の方法が思いつかなくて、1つずつ見てたらTLEしないか？ってなって、じゃあどうすんの、って思ってた。

最後まで問題見たあと残った時間が10分くらいしかなかったので、デバッグしたりしてた。


f:id:wk1080id:20190915174141j:plain
この画像からはわかりませんが（AtCoder ID が書いてある人はオンサイト参加者の一部）、オンサイト順位はけっこう良さそうに思える。わーい！

コンテスト後

prdさんがほぼ全ての原案をしたと聞いて、すごいなあと思いました。問題を思いつく秘訣を聞けばよかった。
Lの解法が天才すぎて、こういうのコンテスト中に思いつきたいなあって思った。

オンサイト優勝者と各色ごとの優勝者には賞状と賞品のバナナが渡されていました。さすが「ゴリラの挑戦状」…

懇親会ではピザが出ました。美味しかったです。FORCIA社ありがとうございます！！！！

懇親会でホワイトボードアンケしてたんですが、参加者は競プロ歴~2年くらいの人が多かったみたいです。

感想

日程がJAG夏合宿と被っていたのですが、そのぶん普段オンサイトで会えない人とも交流できてよかったです。ゆるふわオンサイトに参加した後JAG夏合宿に行く人すげえ…

*1:https://atcoder.jp/contests/wupc2019/tasks/wupc2019_d、今から思えばこれ解いてたら解けてたかも

ICPC2019　国内予選　参加記

競技プログラミング 参加記

noy先輩とHao君と一緒に「UnRated」というチームで出場しました。
3完54位でした。
f:id:wk1080id:20190713022124p:plain

〜前日

チーム練は3回くらいしたと思います。
HCPC 2019 Virtual Vol.20 - 足跡-sokuseki-
ICPC2019模擬国内予選 - 足跡-sokuseki-
four-t practice 2019 Vol.12 - 足跡-sokuseki-

国内突破には4完が必須なので、ABCを早くACしてD以降の考察に時間を割きたいと思っていました。
何度かチーム練して、ABCを自分とnoy先輩で考察&実装、D以降をHao君に考察してもらう戦略を立てました。
自分は今年でICPC引退なので、悔いの残らないようにしたいなあと思って個人でAOJ-ICPCをいっぱいときました。

コンテスト前

15時ごろに大学に着きそうだったので2人にpracticeを任せる。
ライブラリを印刷したやつと蟻本とティッピーを持って部屋に行く。

実装練習にICPC2017国内Cを解く。
チーム練では自分のPC（JIS）を使っていたのですが、突然外付けUSキーボードを使うことになり焦る。
さらに、プリンタを接続して印刷テストしようとしたらPC側でプリンタを認識してくれなくて、これどうするの？使うPC変える？とかいう話になる。（3人はみんなMacBookだけどエディタ等の環境がバラバラすぎるのでア）
いろいろググったりして試行錯誤したところ、開始20分前くらいにうまく認識してくれるようになったので、一安心。
ぞいぞい。

コンテスト

ACを自分が、Bをnoy先輩が、DをHao君が担当することにして、Aから読む。やるだけなので書く。AC。Bの方針を聞いて良さそうなので書いてもらっている間にCを読む。
Cがちょっと難しそうなのでHao君と一緒に考えると、右に載せる分銅と左に載せる分銅をビット全探索すれば0かどうかの判定はできることがわかる。1つ追加して〜のところがよくわかんないなーとか言ってるうちにBがかけたみたいなので見る。answerとprogramをまちがえそうになりながらもAC（複数人で提出チェックしててよかった）。
Cは右と左を全探索すると、そのとき必要になる分銅が一意に決まるので、その重さの分銅がすべてのAiで必要であればそれが答えとなりうるみたいな考察をして、実装する。Hao君に3^Mって言われたけど、計算量的に4^Mでも大丈夫そうだったので、4^Mを書く。


↑いかにもすんなり通りましたみたいな書き方をしているんですが、実はデバッグ出力と答えを見間違えていて「は？答えが出力されてないやが」とか言いつつ、解法が出てたDに実装を変わったりして、20分ほど溶かした（バカか？）。
DはCを実装している間にDP解が浮かんだらしくて、C終わった後に聞いたけどよくわからなかった（は？）。E以降を読んで解けそうなのを探したりしてると、Dのサンプルが合わないらしいので、Dを一緒に考えることにする。Dは区間add区間minの遅延セグ木でできるんじゃない？とかいう嘘解法をはやしつつ順位表を見てみるとEが0ACでFにACがでているのでFを考えてみる。FはAtCoderぽいな〜（Dもだけど）とか言いつつわからないのでDに戻ってくる。順位表をみるとEもACがでてきたので、noy先輩にEを任せてDの遅延セグ木解のコーナーを探す作業をしてた。コーナーみつからないのでサンプルあうか試そうとおもってコードを書いていると、Eは実装激重やるだけゲーらしいのでPCをnoy先輩に譲る。ここで残り45分くらい。Dは諦めてHao君とFを考えてた。
ラスト1分くらいでEの実装が終わったけど、サンプルが合わず終了。

コンテスト後

4完がアジアボーダーだと思っていたのですが、4完以上のチームが少なく、3完でもアジア行けそうな感じがする。
焼肉を食べた。


感想とか

Cのバカがなかったら10個くらい順位上がってたので泣いてる。
ICPC引退が（たぶん）半年延びたので嬉しいです。もっと精進したいです。