いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

連続ACを8か月続けた感想

はじめに

adventar.org
4日目の記事です
自分が長けているといえばこれくらいしかテーマが無かったため連続ACについて書きます

f:id:ratetion:20171203185740j:plain
AtCoder Problems

2017/4/8にABC58に出たところから連続ACを本日まで続け、今日でちょうど8か月になりました
単純に良かったことと良くなかったことを書きます

良かったこと

  • 毎日最低でも1問は解けるため萎えない
  • 頑張ってなくてもみんな褒めてくれる
  • モチベーションを保ちやすい
  • 日が変わったら解いているので習慣が出来た

良くなかったこと

  • 簡単な問題ばかりに手を伸ばしてしまう、意外と簡単な問題が尽きない
  • AtCoderでしか解かなくなる
  • 解ける問題が減るため1日1問しか解かなくなる
  • 遠出しても何があろうと解かないといけないので、特にネット環境が無い時のスマホコーディングなどが辛い

感想

続けてよかったとは思いますがデメリットも目立つ結果になったと思います
今後続けていくかはわかりませんがもっと別の目標に焦点を当てたい気持ちがあるので気が付いたら切れてるかもしれません
始めたての頃は連続ACの存在を知らずとも勝手に連続ACが生えていたため、そういう場合ではなく、モチベーションが保ちにくくなる時にやると意味があるのかもしれないなと思いました

まとめ

連続ACは勝手に生える

CODE THANKS FESTIVAL 2017参加記

行ってきました、どうぞよろしくお願いします
コンテスト内容も言及しますがいつも通り時系列にやっていきます

参加まで

5月ごろだったか記憶が曖昧だがodan氏が大学へ来たことがあった
彼はその時CODE FESTIVALのTシャツを着ていて、デカデカとよくわからないグラフが描かれていてかっこよかった
Yazaten氏もおり、学生しか出れないことや、むしろ出やすいコンテストだとかそんな話をしていた
まだまだ競プロ始めたてで何もわからなかったが、とりあえず出たいなあと思っていた

予選AはJAG夏合宿中に参加し、絶望を感じた
本戦どころかTHANKSさえ行ける気がしなかったし、あまり予選に出る気も起きなくなってしまった
しかしその頃からICPCまでに青コーダーになるという別の目標を立てていたため、予選はレート上げに最適だった
予選Cでは早解き力を生かしてレートを大きく上げた
これが奇跡的にTHANKS参加権を獲得していた
嬉しいような複雑な気持ちだったけど日に日にうれしさが増していくのであった

前日

東京

前泊が許されたので、早起きして新幹線で東京へ
駅のホームで佇んでいると後ろから肩を叩かれ変な声が出た
Yazaten氏だった、車両がは違ったが同じ新幹線だった
社内では噂のtouristじゃんけんのアップデートを行っていた
そろそろ怒られてもおかしくない


東京へ着くと、同学のきりん氏と合流、3人で昼食へ
良かった、これは美味しい、美味しい、どうかなと思ったけど、美味しい、美味しかったよ
www.nicovideo.jp
解散してホテルにチェックイン、リクルート様ありがとう、リクルート様ありがとうコンテストって感じ

ボドゲ会1

荷物を置いて品川へ
駅でTIke氏と竹雄氏と合流しファミレスでも行くかーって感じになる
小粋な旅(ただの遠回り)をしてファミレスへ、僕は昼ごはん直後だったのでパフェを食べました
力強い💪💪💪


店内で待っているとこうき氏、つたじろう氏とも合流、食事を済ませてフェリン氏と合流しカラオケでボドゲ会を始めた
やったゲームはNot My Fault! ~俺のせいじゃない!~(蔦さんが買って来てくれた)とインサイダーゲーム(フェリン氏持参)です
僕は7個ほど持って行ってたけど色んな都合で出来なかった
感想としてはNot My Fault!は一手が重い、始めたてだからかわからないが数字が想像より大きいことが多く、もう数戦すると裏をかいたりし始めるのかなと思った
インサイダーゲームは僕が悪かった💪
退店後、ふーらくたる氏と合流、晩御飯へ
ポルチーニおいちかった>

ホテル

ホテルに宿泊勢で戻ると、すぐに外へ出て、ドクペマックスコーヒーと明日の朝食を買った
マックスコーヒーは甘すぎて凄かった
アパホテルの漫画があったので読んだけど、まあ感想は控えさせていただきます

ボドゲ会2

ホテルで宿泊勢で続きをやるぞやるぞやるぞおいおいおいつりーわん
と言う話になっていたつたj
ということでつたじろう氏と竹雄氏とギャンブラーギャンブルをプレイ、なかなかに受けた
他者心理を読むゲームでセオリーは少ないと思っていたが勝ってしまいア
その後treeone氏が僕の通知欄を壊しながらやって来て一緒にラブレターをやった
Tなんとかさんがやりたいといっていたものをプレイしました!
こうき氏、Yazaten氏も集まって来てみんなでクーをした
寝坊が怖い時間辺りで解散しました

当日

開場まで

余裕の起床をした
まさかTLEするような人がいるなんて思えない><
TIke氏がいつ来るのみたいなメッセージをくれたのでウッキウキで向かった
開場最寄り駅で合流し向かうと、20分前くらいに着いて開場横の休憩スペースでたむろしている競プロ勢っぽい人が声をかけてくれたので一緒に開場まで待つ

この文章会場と開場が入り乱れていていいですね
しばらくするとちょくだいさんがやって来てアイドルっぷりを発揮していて凄かった
開場したので並んで名札受け取って交通費やら誓約書やらやってTシャツゲット
早速着ましたが意外と着ない人もいるんだなあって
前日会った方や、minami氏、ツカサ氏、りか氏、隣の席の馬氏らに話しかけたりしていた
コンテストは1800点取るとパーカーがもらえるみたいなので軽く絶望を感じたが、最後まで戦うぞと決意
Yazaten氏がやって来て、500点を解けばもらえるし、解けるよと励ましてくれた

コンテスト

CODE THANKS FESTIVAL 2017 - CODE THANKS FESTIVAL 2017 | AtCoder

A問題
風船が見えたためFA賞だと思って問題文で雰囲気を感じ取りコンパイルもせず投げたら通った
全然FAじゃなかった・。・v
問題文とか覚えておらず

B問題
開いてしばらく焦った
変な実装とかをしていたが、後ろから区間を決めて回文かどうか判定してmaxを取ればいいことが分かった
文字列をくっつける処理とかが苦手なので添え字を頑張って動かした
なんとかAC

C問題
開いてしばらく上昇量をグラフにして交点を求めていくかとか思っていたが無謀そう
priority_queueを以前一度だけ使ったことあるので、計算量覚えてないけど多分それだろうと思った
しかし2値を扱えるか知らなかったのでググって出てきたのを必死で真似して実装
オーバーフローに悩みながらもなんとかAC、今までの成果が出た問題って感じで嬉しかった

D問題
これは解説をじっくり読めばいいと思うの
全探索を色々やろうとして絶妙に通らずWAを連発
これがダメならgcdを使うんだろうと思ったのでgcdの使いどころを探しながらサンプルと自分で作ったケースをにらめっこした
すると法則が降ってきたのでえいAC

E問題
意味が分からない
双子の問題を思い出した
sist8.com
これの答えみたいな感じで頑張れば実は何か出来るんじゃないかなって
ちょくだいさんが解説で「そんなものはいりましぇ~~~んwww」
みたいな感じでとても辛い時間を過ごした
もちろん解けなかったさ

F問題
問題を見るにDPするんだろうと思った
しかし10^5*10^5必要でメモリは配列使いまわしで出来るけど計算量が無理だった
制約も不明で、これを使うんだろうなあとは気付いていたけどわからなかった
ので、排他的論理和の性質を必死でググって何か得るものはないか考えていた
方向性は間違ってなかったみたいで、思いっきり排他的論理和の性質利用して計算量落としててふえーん
フェーン現象
WA
いいえ

G問題
UFするまでもない、深さ優先探索してやるぜ
しかしわからないのでWFしてやるぜ
タイムオーバーだ!

H問題
読んだだけ
速読のプロ

ABCDの4完でした
パーカーまでは2問届かず、普段より難易度難しいように感じてしまったが、解けなかったことに変わりはない
来年がラストチャンスなので精進するぞと誓った

懇親タイム

CONNECTION HUNTでは、「touristに勝てる日が来ると思いますか?」という質問をさせていただいた

集団で喋ってるところへtouristじゃんけんを持って行ってプレイし書いてもらう変な人間役をやっていると50マスFAした
景品はトートバックとタンブラーで迷ったが、引きこもりのため毎日使えるタンブラーを選んだ

結果はこんな感じでした


その後いろんな方と談笑しながらおいしいぽしゅしなどを頂きました
ぽしゅしです


おまけにじゃんけんは

奇遇にも帰りの新幹線がYazaten氏TM氏と同じなため一緒にホームでお話ししました
TM氏とはまた会う機会があるためとても楽しみ
帰りの新幹線ではシンカンセンスゴクカタイアイスを購入してもしゃもしゃしてました
コンテストが楽しくて自大でも開きたいと思って問題案を考えていたけど難しくて辛いなあと思っていたら奈良に帰ってました
日が変わって数十分で帰宅し僕のこどふぇすが終わりました
楽しかった、来年はパーカー着て帰るぞ、おわり

DDCC2017本戦参加記

19卒枠で参加できることになったの参加してきました
問題はここ
ddcc2017-final.contest.atcoder.jp
今さら書くのは気が向いたからです
逆にね、記憶が薄いから雑に書いても許してねみたいなね
全体の感想としてはすごく満足滅茶苦茶楽しいこれに尽きるのでみんな来年出ようね

前日

同研究科のYazaten氏とウージー氏と共に新幹線に乗り込みました
新幹線では蟻本を読むふりをしながら寝る人間になっていました
DPのページを読み直して謎を深めてたりもしました

小粋なギャグをかましながら昼飯を取りました

その後はスーパーカミオカンデについて理解を深めたり環境について考えたりしました

夜はYazaten氏の呼び掛けで集まった競プロ勢と鍋をつついて酒を飲みつつ、よろずの話題を話しけりしました
傍から見たらヤバい集団だったろうなぁってレベルで話題がシュールだった、毎日やってくれ

ここら辺からTIke氏のブログを参照すると情報の精度が高まります
ti11192916.hatenablog.com

飲み会解散後はホテルに戻ってそわそわして連続ACを更新して寝ました

当日

ウキウキで起床するも一緒に来てた二人はじっくり寝てたので一人で駅の方を散策しに行くことにしました
駅前に行くとTIke氏に遭遇、やっぱりね(?)そう言う事なんですね(?)
一緒に会場に行きました
ここら辺もTIke氏のブログを見るとね


コンテストは非常に険しかった
A問題は去年のA問題そっくりで、解法はすぐわかったんですが、実装で無限にバグらせ続けました
B問題は全然わからなくて色々試してたら通りました
C問題を眺めて終了しました


コンテスト終了後特製ビュッフェを頂きながら雑談していました
みんな問題の話をいっぱいしていて、オンサイトコンテストだなぁと思ってました
ビュッフェはトークに夢中で味がわからなかったけどお寿司が食べれたので東京へ来た全ての目的を達しました(いいえ)

対談は内容がもちろん専門的には浅いんですが、興味深くて、将棋AIに限らず競プロAIが強くなってくるんじゃないかとか、以前麻雀AIに関しては色々調べてたのでなるほどなあと言う感じで、強みはいくらでもあるしリアルな話だと思ってました

会社見学もなぜかTIke氏と同じ見学班でね、やはりね
と思って荷物を預けて集合場所に行ったら誰もいなくてね、TLEですねこれはね
悲しいなあと思いながら同じようにおどおどしてる人を捕まえてスタッフに聞いたらおいて行かれた班が完成してるからそこに合流してくれとの事、ふええ
合流すると6人いて、名前を聞いたことがあるなぁと思ったctyl氏に話しかけ、一緒に見学した


以前行った広島のDPCの時の見学より時間は短くてあっさりしていたが、こっちの方がおしゃれで面白い部分もちょろっとあったかなと思った
生活がほぼ会社だけで完結しているのは羨ましいけど実際やると複雑かもしれない

見学後は懇親会がありTIke氏と感動の再開
また色んな人に話しかけに行ったりローストビーフやケーキをむさぼっていた


最高である
最高
最の高

その後ノリと勢いで体を犠牲に†ボウリング†をしに行った


あらゆることを競プロ用語に例えようとしていて会話が凄かった

その後品川で解散しolphe氏と新幹線で帰宅した
始めて新幹線の切符を買ったため、切符の買い方を教えてもらっている大学院生がそこにはいた


おわり
雑ア

競技プログラミングを初めて半年が経った

競技プログラミングを大学院に進学した直後に始めました
そこから何をやっていたか軽くまとめておこうと思います
ゆらふな氏のブログが参考になったので僕もと言う事で良いループに混ざれたら何よりかなと
pakapa104.hatenablog.com

2017/4

AtCoderのコンテストにノリで出てみる
参加は実際は2回目で学部時代に一度出た事があったが、まじめにやろうと思ったのはここからなので
AtCoder Beginner Contest 058 - AtCoder Beginner Contest 058 | AtCoder
参加したのはこれ
2完で順位は324位、レートもロクにつかなかった

ゆらふな氏の上記ブログを読んでいたのでABC埋めから始めた
#1日1ABCと言うタグを使ってモチベーションを保っていたけどするまでもなく、ACの表示が見えるだけでうれしかった
#1日1abc hashtag on Twitter
わからない問題はツイートしたら競プロ勢がヒントをくれたし、そうしているうちに競プロ勢がいっぱいフォローしてくれた

ゆらふな氏本人からICPCに出ないか誘われたが、僕が出ても足手まといになるとしか思えず保留した
出れるならうれしいとは思った

また、大学でYazaten氏と知り合いアルゴリズム講座を何度かやってもらった
アルゴリズムはどれも画期的で感動的で涙が出そうだった
特にimos法がかっこよすぎて鳥肌が立った
ワーシャルフロイドは何が起きてるかわかるまでホワイトボードで試して説明してくれた
たまにゆらふな氏も見に来てワイワイやってた

また、みんなを誘って一緒にAtCoderのコンテストに出たりしていた

2017/5

C問題が難しくなり始めて解けなくなってきた
たまに解けるけど無理なものはバンバン飛ばしていった
大学でできた友達とバーチャルコンテストを開いて解いたりもした
一緒にやってくれる人も楽しいと言ってくれて嬉しかった


ABCのAとBが埋まった

多分このころからICPCに出る意欲が高まっていた


緑には難なくなれた
ABさえサクサク書ければどうという事はなさそうである

蟻本を購入したので寝る前に1節とかそんなペースで読もうとしていたが全然続かなかった
内容が難しい、僕の読解力が足りない
いずれにせよ、辛い書籍ではあるし、学習は辛い事でもあると思った

2017/6

ARCに出るようになる
ABはサクサク解けるようになったのでC問題にじっくり時間を使いたいと考えた
レートは気にせず、下がってもいいのでとにかくTLでみんなが解法をツイートする前に解きたかった
時間内に解けなくても開設を見るなりして必ず通すようにしていた

難しいと感じた問題は記憶しておいて、時間があるときにノートを取り出して考えたりしていた
シャワー中とか選択物干してるときとか皿あらってるときに解法がわかって叫んだりする頻度が増えた
どうしてもわからない問題は解説を観て通していた

ゆらふな氏とYazaten氏とICPCに出ることを決めてチーム練習をしはじめた
二人が過去のコンテストのバーチャルなどを開いてくれたので模索しつつ出来ることをやる感じでやっていた

鬱を自覚したりもした

2017/7

ICPC国内模擬予選に出た
ratea.hatenablog.com
DPCにも出た
広島旅行みたいな感じだったし気楽で楽しかった
またICPC国内予選にも出た
ratea.hatenablog.com

100日連続ACを達成


連続ACはかなりモチベーション維持に繋がったので価値があった

たまにAOJを解いたりSRMやこどふぉにも出たが苦手というか時間が様々で参加が困難だった
なのでAtCoderだけはきっちり毎週出るようにしていた

2017/8

だらだら連続ACだけを続けていた
300ACを達成したが、簡単な問題を毎日解くだけだったのであんまりいいとは言えなかった

ARCのAが埋まった


そろそろ解ける問題がなくなってきていた
解説を読んで時間をかけてじっくり1問を通すようなことが増えた

2017/9

touristのAGCで水色に到達した
f:id:ratetion:20171005014232j:plain

Yazaten氏とACPCday3に出た
ratea.hatenablog.com
久しぶりのチーム戦だった、二人でやるのは特に初めてで、割とうまく機能してて楽しかった記憶がある

JAG合宿にも参加した
ratea.hatenablog.com
初対面の人とチームを組んでコンテストに出る経験とか、TLの人と実際に知り合えたりとてもいいイベントだった
自分の課題も見つかったので競プロ方面においても価値があった

2017/10

YouTubeで競プロの問題を解く生放送をやってみた
結構みんながコメントくれて嬉しい
考察も逃げずに向かえるので価値があると思う
出来る人はやってほしい

KUPCに参加した
ratea.hatenablog.com
ソロで5時間コンテストは初めてでかなり疲れた
しかし考察をじっくりできるので短時間じゃ解けなかった問題が解けたりして嬉しかった
またJAG合宿と同じく、いろんな方と話しが出来て、みんな本当に競プロが好きなんだなと認識した

連続ACが180日になった、一応これで半年が経った
f:id:ratetion:20171005014114j:plain
レートはあまり変わらずこんな感じ
f:id:ratetion:20171005014153j:plain

まとめ

  • 周りの人のおかげで楽しく続けられている
  • 興味があればまずやってみて欲しい
  • とりあえずABC過去問を解こう
  • まだまだこれからなので頑張る

ポエム

いつもTwitterでポエム書いてるからそっちを見てくれ~~~

以上ありがとうございました

KUPC 2017 京都大学オンサイト参加記

京大が好きなので参加しました(?)
Kyoto University Programming Contest 2017 - Kyoto University Programming Contest 2017 | AtCoder

参加まで

TL等で見かけるし誘ってもらっていたりしたので即決で参加した
申し込みが遅かったので申し訳なかった
コメントに575をかましておいたので一読ください

前日に天下一プログラマーコンテストがあり0完で太陽をキンキンに冷やして精神が逝かれてしまったのでD問題を解くまで寝ないような配信をした
www.youtube.com
結局ACまでに3時間程かかり、寝たのは4時になってしまった
ゆらふな氏、しょラー氏、Yazaten氏と一緒に行く約束をしていたので9時には起きるようにして寝た

京大まで

結果異様な眠さで起床AC
駅で合流して京大最寄り駅へ、近くのラーメン屋で昼を済ませる
f:id:ratetion:20171002020957j:plain
INF回チャーシューが食べれて幸せだったけど腹LE寸前だった

会場へ着くとJAG合宿その他でお会いした方が結構おられ、あいさつしつつ準備をした
ネットがつながりにくかったのでスタッフの方が頑張ってくれて快適な環境でコンテストに参加できた
結果自己紹介がWi-Fi接続タイムになっていてバジリスクタイムを彷彿としてしまったが、感情を抑え込んだ(何故?)

コンテスト

実は時系列で書きます

A問題

貪欲マシーンを使ってウィーンした、AC

B問題

木を登るときに倍か倍+1になってるなとわかったが、それだと数が増えていく一方だったので逆算しようと思った
そのまま実装したらAC

C問題

開いた瞬間辛いと思った
とりあえずハッシュの値を求めてみようと思って何故か10^1000を10^10と勘違いしてlong long intで持てると思って実装
当たり前のようにオーバーフロー:kinniku:
まあハッシュ値を求めたところで僕はそれをどうやって直せばいいか思いつかなかった

ここら辺で順位を確認するとCを飛ばしてD,Eに進んでる人がちょいちょいいて、なるほどと思いながらDとEを開く

D問題

とにかくテストケースを試してみた
なんだか2文字で全部行けそうな気がしたので、2文字敷き詰めを考える
特に2*2に着目して、これを敷き詰めたらどうなるか考えてみた
〇〇 〇〇 〇〇 〇×
〇〇 〇× ×× ×〇

全部でこれだけあるが、左1は周りを×で囲む必要が出来るためまず不可能
左2も周りに×と〇の配置が確定していき3つ置かざるを得なくなる
右1も同じようにして詰む
右2は同じものを並べていけばどんな大きさにも対応できることが分かった
これから2文字で常に敷き詰めれることが言えると思ったので、細かい検証をして、数えて場合分けして投げたらACして拍子抜けした
まじかいや、ほんまかいや
2完で残り4時間半地蔵とかにならなくてよかったなぁって安堵のため息をついた

E問題

鍵を記録しようと思ったが、開けた段階でどのカギを使ったか決める必要がないなと思って、使った鍵の種類だけ記憶することを考えた
記憶するのが困難だと分かった
次に全部箱を開けたとして、開けられない箱の分だけ引いてみる事を考えた
これもなんか難しそう管理がダメ
飛ばしてCに戻ることに

C問題(2回目)

さっきはオーバーフローしてしまったので、各項に注目した
サンプルがどのような動きをするか考えると、右のほうに行くほど大きいが、一つ左に進むときに、右の項を1減らして左の項にa足せばいいことが分かった
これを利用してなるべく左端に数字を集めるようにすればいいのではと思った
しかし調整が難しいので、雑に寄せれるだけ寄せた後で慣らすイメージでforループを2回回したらAC
なかなか気持ちよかった

E問題(2回目)

こういう問題で思考が詰まったときはどうすればいいかなって思って考えた
眠くなってきた、4完出来てしまった
もうゴールしていいんじゃないか?
と思ったけど考察すれば解けると信じて考えると、そういえばこの問題だけサンプル図示してないじゃないかと気付いた
サンプルを図示するとどうなるかと言えば、グラフっぽくなった
そしてグラフを見ると、辺と頂点の数の差があればすべての箱が開けられないと言えるなどわかってきた
どうも合ってそうなので実装したかったが、実装力が足りなかった
辛いなぁと思いつつ、もっと簡単に実装できるかもしれないから別解を探す旅に出た
彼に会うことは二度となかった

タイムアップ
解説を聞いて、F以降は異次元だと思ってしまった
まあ4完出来たのでよかったが、何より問題がすごくおもしろかったなと思った
賢い人はもっとうまく解くけど、僕のように考察をしまくれば何も知らずとも解ける問題があったりして、地蔵になるような事が無かった
問題も面白いし、多分AC出来なくても楽しかったんだろうなと思った

懇親会

焼き肉


適当に目の前の席に座ったら運営のあしぃ氏が運営の話や、競プロの話をわんさかしてくれた
まだ僕は始めたてだし、あまりオンサイトとかに参加することもなかったのですごくいい話が聞けたと思った

どの机でも競プロの話が飛び交っていて、当たり前なんだけどこんなに楽しんでてええなぁと思ってた
める氏と肉を頼みまくって腹LEした

帰路ではりか氏、T.M氏、odan氏らと駅まで歩いて向かい持ち前のクソトークとコミュ障を披露した(???)

まとめ

  • 楽しかった
  • 問題の質が良く、作問者に感動していた
  • 知り合いが増えてきて競プロやってる実感が沸いた、もくもく
  • 考察はとにかくサンプルを書く等すると捗る

運営のみなさま、参加者各位ありがとうございました
おわLE

JAG夏合宿2017 参加記

参加させていただきました
ICPC国内予選終わったちょっと後くらいにYazaten氏からお誘いいただき参加
こっちはコンテストの事だけ書こうと思ったけどややこしいので時系列順に書きたい事を全部書きます
読みたい部分だけ飛んで読んでみてください

参加まで

精神が弱いため参加申し込みをしたは良いが、実際に行くのが怖かった
交通手段確立も面倒だし荷造も荷物多くなるのも嫌だしうがーって感じですべてを後回しにしていた
Twitterボードゲームをやろうって話してたので初対面の人とでも楽しいであろうゲームをピックしておいた、それだけが楽しみだった
Yazaten氏が連絡をくれてバスを提案し予約してくれた
アイエエエ

day0

荷造りをして不安に駆られながら家を出た、すぐ引き返して上着を着て脱いでカバンに入れて別の上着を着た
意味は無いけどよくわからない
バス停に着いてボーっとしてるとYazaten氏と合流、マスク忘れたなぁみたいなツイートをしたらマスクをくれた
アイエエエ
バスに乗ったけどもう引き返せないとか言ってしまったし重症だと思った

day1

東京着

バスでは寝れるけどすぐ起きるような状態を繰り返していたが、あまり記憶がない
気が付くと東京についていたらしい、降りると新宿だった
自分の事でいっぱいで何も考えてなかったので二人でどうしようか話して、氏が提案してくれたカフェがあく時間までバス待合所で時間を潰すことに
空いてる椅子に座って連続ACのためにスマホコーディングをしていた
解いた問題はこれ
A: Multiple Array - AtCoder Grand Contest 009 | AtCoder
解法はササっと思いつけたのでよかった
実装も簡単目だったけど2回WAのちAC
Submission #1610551 - AtCoder Grand Contest 009 | AtCoder

カフェに向かう途中でメガホンを持って「ギャグあります」と叫び続けている人がいた、芸人か何かっぽい


はい(義務)
カフェではクロワッサンが層を多重になしていておいしかった(?)

目的地が無いのでYazaten氏の勧めでつじ半という海鮮丼の店に並ぶ
開店1時間前とかから人がいっぱい並んできてすごくすごかった(?)
f:id:ratetion:20170925221558j:plain
とてもおいしかった(KONAMI
後で鯛だしを入れてもらえ、そこに刺身をつけて食べるというのがお勧めらしく、これがとてもよかった、よい、よい

snukeさんの問題セット

受付でしょラー氏に"""初めまして"""と挨拶をしていただきました
JAGセットだけチームで参加することにしていたので、イイ感じに実力順でチームを組んでもらい、白瀬氏と百千万億 萬氏のチームに入れてもらった
Japan Alumni Group Summer Camp 2017 Day 1 - AtCoder

始まったら僕はA、白瀬氏がB、萬氏が全体を読んで司令塔的に動いてくれて凄かった
Aは一見簡単そうだけど解ける自信がないため概要を聞いてもらったら、Jが簡単らしいので実装を請け負った
緊張して変なコードを生産してしまったがなんとかAC

Hの詳細を聞き考察をした
各8方向への移動をし続けるときにそれぞれ何ステップかかるかを考えて表にまとめておいた
右上に進むときだけ有利になって他は上下と斜めで変化がないことが分かった
後は最初動き出すときだけはどの方向も未使用なのでステップ数が減る

これを伝えるともっとうまく分類出来て楽に実装できそうとの事
表だけパスしてAの考察に戻る

ここら辺で萬氏がEのFAを取ったらしい、すごい

1文字目を使用しきるまでは1-2-1-2-1-2-.....とループするはずなのはわかったが、2文字目は2文字だけで回しきれるのか証明が出来なかった
サンプルも微妙に検証しずらいが、どうも各文字数ごとで回せていそうと言う事に落ち着いた
実装が固まりそうとの事で白瀬氏に実装を頼んでKの考察をした

KはbitDPをしたいと思ったけど実装したことないのでわからず、10^5は持てないと言われた
だとすると貪欲がしたくなるのだが、ほんまか?
考えても貪欲をやっていいようには見えなかった

A実装が辛そうだったのと、まだマシな実装を思いついたので実装を代わる
実装を終えてサンプルがあったので提出すると4WA
変なことしちゃったかなーと思ったので印刷を投げてPCを代わった

デバッグをしていると萬氏によりD,Fが解かれていた、っょぃ

自分のソースで怪しいポイントを数か所見つけ(多い)修正すると1WA、うーん
まさかこの1WAが2文字と3文字の間のコーナーケースなんじゃないかと思って証明できないか考え始めた
白瀬氏と色々検証してみたがどうもわからない
この時グラフに落とし込むとかそういう発想が出来るとよかったんだろうなぁ
萬氏が僕のソースにオーバーフローを見つけて修正提出、AC
机に頭を付け謝罪した、頭の悪いコードだった

白瀬氏がKを実装していたがサンプルが合わず終了
チームとしては5完だったが僕はほぼ邪魔になってしまった

部屋の端でゆらふな氏とimulan氏、yana氏が喋ってたので合流して晩御飯を食べに行った
ご飯の席でixmel氏とT.M氏と合流して挨拶してクソトークを展開するなどした
YazatenjouエピソードでYazaten氏のいないところで盛り上がった
ratea.hatenablog.com

その後すぬけ大先生の圧倒的解説
なんとなくわからないけど解けそうみたいな問題をズバズバ説明されてすごかった
楽しそうに解説していて楽しかった

解説後aotenjouのみなさんに"勇気を出して"挨拶しに行った
TIke氏とボドゲの約束をしていたので風呂入ってすぐやることにして、Treeone氏にも挨拶して巻き込む(?)

ボードゲーム

談話室にボードゲームを持って向かった
持ってきたゲームは3種類

クー 日本語版


コードネーム 日本語版


犯人は踊る(2015年第三版)

クーをaotenjou+treeone氏+談話室で合流したフェリン氏とやった
ちょうど6人で出来るので都合がよかった
概要は先にTIke氏が書いてくれたのでそっちもぜひ読んで(誘導)
ti11192916.hatenablog.com
読みとか駆け引きが強いゲームなのでお互いのことをよく知る前に殴り合おうという提案を受けてこれを選んだが大成功だと思った
ルール説明をしているとみんな「こうなったときはどうするの?」って僕が言い忘れたルール突っ込んでくれて説明しやすく、なめらかにゲームに入ることができた
戦略とかの理解も早くてみんな強い、普通に負けました


やってる間にDiv氏とimulan氏がやってきたので8人になり、みんなでできるコードネームを選んだ
スパイマスターはminami氏とTIkeが担当、序盤は難しそうでお互い攻めあぐねてたが、後半かなりうまい誘導をしていていい勝負だった

12時までしかスペースが使えないので急いで片付けて解散した、またやりてえなあ!
フェリン氏も2作持ってきてくれてたのでせっかくならそっちもやりたかった
続きはwebで

day2

起床ACして昨日のボードゲームメンバーのうち起きてそうな人で集まって朝食へ向かった
メロンソーダが好きなのでメロンソーダを堪能していた
ご飯とパンをもらうスペースが別なので両方もらってしまいお腹 Limit Exceededしている人がいた

こどふぉセット

Login - Codeforces
どふぉどふぉ
チームは前日と同じようにマッチングしてもらってokaduki氏とyang33氏とチームrateduki33で出ました
fakse_rateというチーム名案も出て面白かった

前と後ろと中間から読み始めることになったので僕は前から読んだ
A問題はニュアンスがわからず円なのか球なのかのある地点で円形の邪魔な何かがあってそれを避けて通る
数学のプロがいれば投げても?って感じだったけど自信が無いのでyang33氏に聞いてもらう
入力を見る限り球らしい、そういう判定方法があったか
飛ばしましょうと言われたのでBを読む
これも自信が無くて英語力の低さを実感した
okaduki氏がヘルプに入ってくれてそのまま二人で考察、DPで解けそうと結論を出してくれたのですが、簡単なDPしか書いた事が無かったので実装を断ってしまった、ごめんなさい

Hが多く解かれているので読むも、また意味が分からない
端っこまで飛べるものだと勘違いして迷宮入りしていた

Lが通ったらしく、Gを通そうとしていたみたいで考察を聞いた
三分探索をイイ感じにやる方針で実装していたみたいで、解けそうだと思った
WAが出て考え直したら2次関数チックにはならないことが分かってしゃくとりっぽくやるのではと思っていたら二人の間で考察が進んでてついていけなくなってしまった
アッパーバウンドとか聞いたことある何かを使ってACしていた

その後okaduki氏がBを実装、yang33氏とHとIを考察
Hは誤読していたままだったので、誤読が正しいと仮定して僕が実装することに
Iは入力から計算できないケースは無いのか、答えが一意に定まるかどうか色々考えて証明しようとしていたが出来ず

okaduki氏が紙デバッグに移ってくれたのでHを実装、もちろんWAだった
出来る事が無くなってしまったのでokaduki氏を見守っていたらタイムアップ

とても辛かった、英語で損こうむるのはもったいないなぁと思った
またDPを自信をもって実装できるようにならないといけないと実感した

ボードゲーム

前日と別の談話コーナーでボーっとしていたらすぬけ大先生がボードゲームを一緒にしてくれた
枝豆を押し付けあうゲームだった、いいセンスだった
とんでもない運を発揮してワンターンで勝ってしまった
またじっくりやりたいと思ったし機会があってくれ
最後のボードゲームのタイトルを聞いた

万豚記

Yazaten氏ゆらふな氏nvip氏btk氏でオリセン前のラーメン屋に行った


角煮担々麺をチョイスした、角煮がごつくて顎が疲れたがとてもおいしかった
nvip氏とYazaten氏がそれぞれ別の辛いラーメンを頼んでいたのでスープをちょっとずつもらったらその後1時間くらい泣きそうだった

こどふぇす

JAGの方がWi-Fiを提供してくれたので談話室で参加した
ABを10分で解いてCを無限にWAを出して2完で終わってしまった
終わった後いつもTLでやってるようなことが目の前で起きてて面白かった
ixmel氏がDまで通してキメててかっこいいと思ってたら僕のコードを観てくれて指摘してくれたりした
僕はちゃんと証明とかせず見切りでやってたのがよくわかって情けないと思った


悔しくて部屋に戻ってもなかなか寝れず、問題を開いて考えながら寝た

day3

起床AC
部屋の掃除とシーツをたたんで着替えて準備して談話室でボーっとしてたら自チームとaotenjouとQU勢とフェリン氏が来たのでみんなで朝食にした
前日のおかげか腹LEしていなかった
minami氏とYazaten氏がプロな話題(?)で盛り上がってたのが印象的だった

JAGセット

Japan Alumni Group Summer Camp 2017 Day 3 - Japan Alumni Group Summer Camp 2017 Day 3 | AtCoder
Yazaten氏とゆらふな氏とsparsely_populated_regionsで出た
簡単そうなものを見つけて解く方針になった
始まったら僕はどれが簡単かわからなそうだったのでYazaten氏に聞いてEとCとあたりを読んでた
ゆらふな氏がABを通していた、早い
Cが解けそうだったので方針を聞いてもらうと、実装が辛そうなのでYazaten氏が請け負ってくれた

ゆらふな氏とFを考察した
僕がちゃんと読めてないせいで問題の把握が遅くなった
ずっと英語に苦しんでいるなコイツ
二部グラフの話を聞いてどうもそれは成り立ちそうだと分かった
BFSをしたい気持ちになったので、できそうか考えて、思ったことを言ってたら大体を証明して解法にしてくれてた
声が大きく目立ってたらしい、終了後にT.M氏から楽しそうでしたね、とのこと
二部グラフマン

Yazaten氏がバグらせていたのでゆらふな氏に説明したら、僕が考えたのよりずっと簡単な解放が出たのでそれで実装し直してもらう
とても申し訳ない気持ちなった

Fをゆらふな氏が実装に入ってくれたのでE考察に入った
×を限定してうまいことやるとか、×を貪欲にやるとか考えたけどどうもダメだった

FがACしたらしい、ほぼゆらふな氏のおかげだったが、一部解法に関われた感があって嬉しかった
全員でEを考察、どうも僕にはわからなさそうだという事が分かった(いいえ)
DPにうまい応用方法があるなんて知らなかったよ
二人にゆだねお茶くみ係をしていました(いいえ)

結果は4完で、もしYazatenjouだったら悲惨だったねなど話していた

解説を真面目に聞いていたら、後半は全くわからなかったがコーディングしてる人とかが多くて解説してくれてる人が僕のほう観てたまに「どうすか?」みたいなこと言ってくれてツライだね

築地

JAGの合宿自体は解説後解散したので、チームで築地に寿司を食べることにした
駅までixmel氏もと一緒に行っていたので、そこで次はKUPCですねみたいな話をして電車ですぐに登録をしておいた
楽しみである

築地に着くとYazaten氏の一押しのお店へ
店長のお勧めが時間差で握ってもらえて一貫ずつ目の前に置かれていく
毎回それが何の魚なのか貝なのかどんなものなのか説明までしてくれる
兎に角うにと大トロがおいしかった
犯罪的だった


銭湯

ゆらふな氏と別れYazaten氏と二人で銭湯に行くことにした
乗り間違えたりして紆余曲折の末、昭和風味が漂う素敵な銭湯へたどり着いた


体を洗って湯船につかろうとすると、、、熱い
50度はあるんじゃないかってレベルで熱い、嘘だろ、、、
火傷してるんじゃないかと思った
湯が出ているところから一番遠いところに何とか浸かれた、それでも熱すぎる
横で体洗ってたおっちゃんに笑われて、東京は江戸っ子精神がどうので、風呂は熱いもんなんだと聞かされた
軽くこちらの事も話したりして観光の情報とか色々勧めてくれて面白いおっちゃんだった、あったけぇ、風呂は熱い
足は真っ赤で水をかぶり続ける妖怪か何かになっていた

やざてんコンビニゲーム!!!


帰りのバスまで暇だったので勢いで(疲れで変なテンションになっている)開催した
大当たりは醤油、桃の缶詰、ビール、クリスタルカイザー



これ美味しそうですよね、今度個人的に買う

バスに乗ってぐっすり寝ながら帰りました

まとめ

鬱だったけど参加してよかった、似たような人がいたらぜひ参加して欲しい
課題がいっぱい見つかった
強い人と組むと地蔵になるけど出来ることを精一杯やった
楽しかった
JAGスタッフの皆さんありがとうございました
アジア地区に向けて、来年こどふぇすワンチャンに向けて、とにかく悔しくなくなるように等々
出来ることを頑張りたいと思いました
雑な記事になりましたが、いつも通りなので良しとします

ACPC2017Day3参加記

AIZU ONLINE JUDGE

起床ACした、もう勝ったも同然

Yazaten氏(@Yazaten)とらてあ宅で二人で出ました
チーム名は某氏のaotenjouを意識してyazatenjouで出ました
ABCD4完16位でした


Aを僕が、DをYazaten氏が、その後は随時って方針で
これ結構よかった説

A.A-Z-
文字列の大小比較をして現在のマス<=次のマスならインクリメントしといた
こんな簡単でええんかホンマか?って思って不安だったけど投げたらAC、まあはい

B.えびちゃんと数列 - Ebi-chan and Integer Sequences -
三角形みたいなの書いて反転分を2倍して同じ数字を加算して求めようとしてた
三角形が微調整が必要とか頭を抱えていた
Yazaten氏がDを通してくれたので相談すると、なんか別の方針を投げてくれてそれなら解けそうだと思う
とても辛いが、何とか等差数列で表せることが分かった
しかし愚直に求めるとTLEが見えるので考えて、適当に等差数列の和をググって式を作る
僕は辛いので途中まで考えて、コーナーケースとか投げてYazaten氏にお任せ

C.たったひとつの部分列 - Unique Subsequence -
簡単そうって思ったけどわかんない
全探索をするより良い方法が思いつかなくて、辛い
多分全探索のループ回数が10^5-1までの和とか、おわおわり
うーんうーんって悩んでたらYazaten城がB問題をWAしており、問題概要を伝えた
しばらく虚空を見つめ霞を食べた
唐突にYazaten城から解法が降ってきた
f:id:ratetion:20170921015932p:plain
前から取ったインデックスと後ろから取ったインデックス比較すればいいとの事、聞いた瞬間ACした、もちろん嘘だ
実装を任せてくれるとの事で、フォローもらいつつ実装、スタックを久々に使ってツライだね
なんとかなったのでAC

Bに戻って2人でツライした
コーナーケース探して、式を見直して、mod確認とかして、場合分けし直して
こんなケースはどう?って投げまくってたらmod取れてないケースがあった
場合分けした時の数値がそのままだった
modを取ったらAC

残り時間は45分で、後半の3問を眺めてどれもどうとか話してた
G問題が無茶苦茶楽しそうだったので考察でも練り続けたい
お疲れさまでした