雑記

競技プログラミングについての話題(?)

ARC018-B 格子点と整数

 

解法が想定解と大きく異なったのでまとめておきます

arc018.contest.atcoder.jp

 

続きを読む

ABC063 ARC075

問題概要は雑に書いているのでどうせならコンテストページを見ようね♡

 

続きを読む

Macでの競技プログラミング環境構築

 

前まで使っていたMacが去年突如壊れてしまったので新しく買いました

 

続きを読む

JOI

JOI予選は460点で通過することができました (ブロック制による招待だったので九州沖縄2位みたい)

 

本当にほっとしていると同時に、未だに本当に通過しているのか

といった気持ちもあります。

 

本題に入るのですが、本番環境は設定ファイルなどを事前に用意しておくことができないので .vimrc .bashrc などを競技時間中に書かなくてはならないので面倒、といった話がTwitterでされていました。

その中で得た一番の知見であるところの .vimrc の省略表記について簡単にまとめます

 

JOI本番で使用する予定のvimrcです

 

1行目

これも初めて知ったんですが、set は1行に複数書けるみたいですね

それぞれ

nu : number

ts : tabstop

sw : shiftwidth

et : extendtab

cin : cindent

sta : smarttab

の略です

ほかにも書きたい気持ちはありますが、本番中という精神的にも時間的にも余裕がない状況なのでこれだけにします

 

2行目

sy on

sy on : syntax on

たぶんこれで動作するんじゃないかな......(今使っている環境だとそもそもデフォルトなので日曜日に本番環境に似せて実験をしてみます)

しっかり確認が取れないとこわいので確認がとれない限りは略さずに書くと思います

 

3行目

ima <C-]> <esc>

たぶんこれで動(

これも動作が確認できないと使わないと思います

というかいつも使っているPCのCtrlの位置にCapsが来ている可能性が否めないのでキーボードを見てから決めます

キーボードの状態によっては jj もしくは使わないといった選択肢になるかな

 

本番に1行だけ書いて終わる未来が見える

 

 おわり

 

さんすう

JOIが終わって翌日の12/12、1day1pro復活祭をしました

 

今度こそ死なないように頑張りたいところですがさっそく先が見えてきて怪しいなあみたいな気持ちです

 

まあ頑張る

 

 

さっそく違う話になりましたがさんすうの話をします

 

12/13の1day1proで出された問題です

 

宝探し | Aizu Online Judge

 

まあ実装する問題なんですが、ここで某氏に謎のエラーが起きます

 

そのあたり全然詳しくないので原因についてはさっぱりなんですが、sin、cosなどの三角関数が未定義みたいなことを言われているっぽく、誰にも原因がわかりませんでした。

 

まあコンパイラあたりの問題だろうしそのあたりを解決すべきだと思うんですけど、ぼくにはその力がなかったので、sinとcosを自分で実装しました

 

まあ有効数字15桁くらいあれば誤差は大丈夫そうだったので簡単に実装したんですけど、結構楽しかったです。

 

 

以下コード

sin, cosの実装(有効数字およそ15桁)

 

 

言われるまでもなさそうですが各関数の説明をします

 

 

abs(long double)

 

絶対値を返すだけの関数です

引数の値が負なら-1かけて返すだけ

別に必要なかったんですが、次の sqrt の内部の if 条件文が汚くなったので分けました

 

 

sqrt(long double)

 

引数の2乗根を返す関数です

処理自体は簡単なものなので見てもらえればいいんですが、数学的な話は適当に調べてください

piの値を求めるために使いました

 

 

pi(int)

 

特に引数は必要なかったんですがとりあえず書いておきました

Gayss-Legendre algorithmと呼ばれている有名なアルゴリズムです

この関数だけは有効桁数を大量に生やすことができます

この問題の角度は弧度法で与えられないのでsin、cos内部でラジアンに変更することにしたのでこれを書きました

 

 

fact (int)

 

引数の階乗を返すだけの関数です

int やら long long だとすぐ爆発して死んでしまうのであえてlong doubleにしました

制度が出せていない一番の原因はこいつです

 

 

pow(long double, int)

 

第一引数の第二引数乗を返します(わかりづらい)

こいつも精度を悪くしている

 

 

sin(int, int)

cos(int, int)

 

本来実装したかったやつらです

幾何学的な定義だとアルゴリズムとして処理できないのでいい感じにします(多分調べれば出てくる)

実装は似ているので片方実装したらコピペすると優勝します

 

 

内部のアルゴリズムに関して一切触れていなくて申し訳ないのですが(TeXが書けないので)

誤差をどうにかしたいみたいな気持ちがあります

 

おわり

JOI予選までにこの弱い頭はなんとかなったのでしょうか

※この記事は ICT Advent Calendar 2016 の12日目の記事です。

 

12/11、JOI予選がありました。ぼくが競プロを知ってからのことを振り返ります。

適当に勢いだけで書いたのでめちゃくちゃな文になっていると思いますが許してね❤️

 

 

競プロの存在を知ったのは去年の後期、M教授がもつプログラミングIの講義でkurokojiが隣の席になったときでした

 

ぼくはその頃から講義レベルなら普通に演習問題を解くことができていたので、その時間の演習問題を解終わると時間を持て余していたのですが、隣にいたkurokojiが「AOJとかやらないの?」と聞いてきたので初めてAOJと競プロの存在を知りました。

ただまあ、その時の僕はICTにはいってすらなく、興味だけはあったもののやる気がなかったのでそのまま時間が流れました。

 

2015年12月

ちょうど去年の今頃ですが、同級生らがJOIに参加するといっていたことでJOI自体の存在は知っていましたがやはりその時も参加はおろか、競プロすら始めていませんでした。

 

2016年1月末

なにを思ったか、C++をほんの少しかじります。その練習程度にHello Worldを書いたりなどしてAOJを初めて使いました。

 

2016年3月末 (?)

結局1ヶ月くらい競プロをせずに時間が流れます。

それで、いつの間にかICTの春合宿に参加することになっていて春合宿に参加しました。

確かこの時期にslackに入ったと思います。

1day1problemが始まったのもこの時期だったと思います。ぼくが競プロを本格的に初めたきっかけでもあるこの1day1proについては、運営をしてくださっていたコーヤ先輩がICT Advent Calendar 2016 の2日目の記事に書いていますのでぜひご覧ください。

Kick-ass 1day-1pro Carnival - さいどうにっき

 

春合宿中、アイデア出しがあってつらいつらい言ってました。午後から夜中にかけてはそれに時間が吸われていましたが午前は申し訳程度に競プロをしていたように思います。

あとお金があったので蟻本を買いました(ちなみに、現在財布に9円しか入っていません)

 

2016年4~5月

まばらではありますがちょこちょこ問題を解いていました

確かこの時期にはABCのC問題が解けことがある、程度の感じだったと思います

それとkurokojiとチームを組んでPCKに出ることになりました

kurokojiが自分より無限に強く、本当に自分でいいのかみたいな気持ちながらも誘いを受けたのを覚えています

 

2016年 6月

何もしませんでした(←!?)

今冷静に振り返ってみてもここは焦って精進すべきところだと思います。

多分テストがこの時期にあったんじゃないかと踏んでいます。

 

2016年 7月中頃まで

この時期もほとんど何もしていなかったに等しいですが、少しずつ蟻本をよんでいたりした記憶があります

 

2016年 7月下旬 ~ 8月上旬

夏休みです

各位が高専プロコンで死にそうになっていたのを覚えています

ぼくはぼちぼち蟻本を読んでいました

家がドがつく田舎にあるので、固定回線はおろか、モバイルですら怪しいみたいなところに帰省していたためですかね

 

2016年 8月下旬

PCKが近づいてきて、さすがに焦りました

合宿前日くらいにPCKの予選があり、超焦って蟻本を読んでいました。理解力を総動員して蟻本を読んだおかげでこの時にぼくの競プロ力はぐっと伸びたと思います

フローは流した(フローなので)

 

2016年 PCK予選当日(9月10日)

普通の結果を残しました。ダメダメでもなく、できたわけでもなく、ただ自分の実力が出て相応の結果が出た、といった感じでしょうか。

ただ、それが無性に悔しくて悔しくて、ここから目標を完全にJOIに向けます。

おりさの先輩と初めて話したのもこの日です。*1初対面で煽られました。Advent Calenderは書かないんでしょうか。

それと、久留米のらてまるたさんがPCK予選問を1WAも出さずに全完して1位で通過していたのを見て、「かっけぇ......」となったことを覚えています。そんなぼくの目標の一人であるらてまるたさんはICT Advent Calendar 2016 の22日目の担当になっています。*2

素敵な記事を期待しています。

 

2016年 9月 夏合宿

ぼくだけ高専プロコンに出ないせいで暇(相対評価です)だったので1年生の教育係?として1day1pro改め1day3proをしていました。

まあまあ辛かったけど楽しかったのでまあよし。

自分の精進も忘れてはいなかったので。(記憶が確かなら1日で50ACとかしていた気がする)

zig-zag numberをおりさの先輩*3に手伝ってもらいながら通したのもこの時でした

 

2016年 10月

学校が始まりだらだらしていた。

JOIの問題を解いている形跡があるので一応精進はしているみたいだけど、やる気が起きなくてやるだけをやっていた気がする。

 

2016年 11月

無限に焦っていた。JOIまであと1ヶ月しかないって時期なのに何も見ずに*4解けるDPが通学経路とか簡単な桁DPだけだったので絶望的だった。

テストがあると気がついたが迷わず捨てて、ただひたすら無限に精進していた。

朝起きて解いてない問題を数問見て覚えて午前の講義中ずっと考察、昼休みにコーディングして午後もまた考察。みたいな生活を11月半ばから続けていた。

11月も半ばにさしかかってきたところで簡単なDPの解法がすぐにわかるようになっている気がしていた。

 

11/20、中学2年生のsquareプロとE869120プロが作問しているs8pcがAtCoder上で開催された。

軽い気持ちで参加したぼくは1問しか解けないままコンテストが終了した。

本気でやったのに1完である。

 

この時ほど焦りを感じたことはなくて、今でも思い出すと鳥肌が立つし吐き気までしてくる。大嘘だけど。

ぼくはTwitterしまくり芸人なので多くの時間をTwitterに費やしていたがこのままえではまずいと思ってアカウントを一時的に消した。消えるのが怖かったので1週間後にひそかに復活させておいた。

 

 

2016年 12月

完全に競プロのこと以外考えていなかった。ボロボロの答案が返ってきてちょっと落ち込んだけど、そんな場合じゃなかった。

ひたすらにJOI非公式難易度表を埋めながら吸収できる分だけ吸収してと、無限に精進をしていた。

 

2016年 12月10日 (JOI前日)

偉大な先輩であるところのkagamiz先輩がJOI予選の模擬を開催していた。

結果は1 ~ 3問目AC、5問目ACの4完で、いい感じに実力がついていることはわかった。提出練習は何度もやっていたけど、緊張感を持ってやったのは初めてだったのでいい練習になった。本当にありがとうございました。

この日の夜、AtCoder Regular Contestが開催されていて、いつもなら普通に参加して普通に終わるところだけど、完全に自信を喪失したs8pcの件があったので問題を見るだけにとどめておいた。

F問題を一番最初に見たのだが、不思議とすぐDPだとわかったし、その解き方も少し考えればすぐにわかった。今思えばDPの特訓の成果だったかなと思う。

 

2016年 12月12日

JOI当日。みんな緊張しているみたいで、kurokojiなども険しい顔をして一人で昼食を食べていた。(一緒に食べたが)

まあ、不思議と緊張はなかった。緊張がなさすぎて午前中まるまる寝ていた。後輩が質問したいけどいいですかと言っていたのに2時間後くらいにレスポンスを返したことはこの場を借りて謝罪したい、大変気持ちよく寝させていただきました。

 

競技中、もうアドレナリン出まくりで競技前には無限に寒かった(このとき半袖です)のが、むしろ無限に暑くなっていた。

 

1から3問目ははいって感じですぐさま通した。

 

4問目

緊張しながら問題文を読んだら一瞬でbitDPだとわかった。これはいけると思って実装したがいくつかバグが出て少し苦戦、30分くらいでようやく書ききった。

 

ここまで1時間近く経過していて、5問目6問目を頑張ってみようとなった。

 

5問目

同じ標高の場所はないとなって、これは一番小さい場所から決め打ちしていくしかないと思ったのでpriority_queueだと思った。

周囲に尾根だと決まっている場所があるならその場所も尾根になるなとなって、そこを基盤に条件文を書いていたが、状態のもち方がよくなくて、1ケース目と4、5ケース目だけが通って60点になった。

 

6問目

ダイクストラを拡張するとよさそうだと直感的に思ったので、とりあえずダイクストラを生成。

priority_queueに いつもの重み、次の辺に加えて、部屋に入れるかの条件分岐に使うための時間を新たに持ってダイクストラを変形させていった。

時間の部分を正負をもって表現していたが、配列に使う問のめんどくささを考えて素直にbitを持てばよかったなと思っていたりします。

 

結局バグが生えて時間が足りず、5分前くらいにダメ元でoutputを投げたがもちろんWA、提出ミスがなければ460点になりました。

 

 

競プロを初めた2月3月あたりから今までにかけて、本当に楽しかった、といったのが感想です。

確かに精進は一人でしかできないしつらい時もあったけど、orisano先輩やlatte0119さんなどから知識を吸収して問題を解いて、解けた時は本当に気持ちよくて。

知識はそれ自体に価値があるんじゃなくて知る過程に価値があると学びました。

ただ知っているだけよりも、問題を解くことを通して得た知識は体の奥底に定着する感じ、といったところでしょうか。

これからも精進していきたいと思います。

 

ぼくをここまで育ててくれたorisano先輩、コーヤ先輩、もからとびあさん、本当にありがとうございました。*5

 

 

 

 

JOI予選までにこの弱い頭はなんとかなったのでしょうか?

 

 

 

 

 

 

PS : ところでorisano先輩はAdvent Calenderを書かないんでしょうか。25日が空いていそうですよ。

 

 

*1:初めましてさの先輩

*2:これは沖縄高専 ICT委員会のAdvent Calenderです

*3:守護霊さの先輩

*4:問題文は見ています

*5:別にお嫁に行くわけではありません。

JOI本選 - ぴょんぴょん川渡り ペンキの色

2008年の予選・本選の問題はこれで全完(?)しました

 

 

ぴょんぴょん川渡り | Aizu Online Judge

 

ぱっと見やるだけDP、やってみるとやるだけDP

AOJ特有の複数データセットのおかげでvectorの初期化を忘れており死んでいて無限に時間が吸われたのでAOJに感謝ですね

 

 i 行目の 左から j 番目の石から i + 1行目の k番目に渡る時のコストと今までのコストを足したものが先のコストより小さいなら値を更新、みたいなDP(m回まで1行飛ばしで進めるのでその分もうまく使いますが)

 

forでDPを解くのを避けてきていたけどそろそろ避けるのをやめていきたいと思ったのでfor で解いた

 

ぴょんぴょん川渡り

 

 

ペンキの色 | Aizu Online Judge

 

問題見た瞬間「あ!これ魚の生息範囲で見たやつだ!*1」となった

こんな感じの座圧は一度しか解いていなかったけどこれがわかったことには成長を感じています

座圧していい感じに処理した後は深さなり幅なりで数えあげて終了(完)

 

ペンキの色

 

 

どちらの問題も比較的簡単だった気がする(ほんまか)

ペンキの色は座圧だ!となってから時間がかかってしまったのでイメージだけでなくきちんと紙などに書きながら考察していきたい

 

JOI頑張るJOI

*1:進研ゼミでゎなぃ