いつも頭に問題を

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

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問題が無茶苦茶楽しそうだったので考察でも練り続けたい
お疲れさまでした


Codeforces Round #431 (Div. 2)

Dashboard - Codeforces Round #431 (Div. 2) - Codeforces

出ました、ミクさん回と言う事で各問題のタイトルがミクさんの曲でした

A.Odds and Ends
ハイ名曲
数列を奇数で始まり奇数で終わる奇数個の部分列に分割してくれって問題
よくよく考えたら分割しなくても1個成り立てばよいことがわかるので奇数で始まり奇数で終わる奇数個の数列が与えられたらYesを出力したらいいっぽい
時間はかかってしまったし読解が難しかった


B.Tell Your World
ハイ名曲
座標がいっぱい与えられるけど、それの全ての接線を2本平行なものだけ引けるか判定しようって感じ
時間かけて考えたら、与えられる座標は必ずx座標が1ずつ増えるので、隣接2点の差を取ればそれが各隣接2点の傾きだとわかる
ので傾きの種類を数えたら2-3種類であれば条件を満たすと思ってコーディングした
提出したら通ったがハックされていた、辛い
後でコーナーケースに気付く
多分こんな奴
f:id:ratetion:20170902002530p:plain
傾きの種類は3種類だけどどう頑張っても3本平行な線を引かないとダメなパターン
これ以外にもあったら教えて下さい、多分これでおちたんだと思う
これが分かったからと言ってどうすればよいかわからずタイムアップ

C.From Y to Y
ハイ名曲
正直わからんかった、問題文が
文字列を最初は1文字ずつ分割されてるものとして、結合をしていく
その時に同じ文字を含むある条件でコストがかかるっぽい
このコストの式の文字cが意味が分からんかった
考えて頭抱えてるときにBが落とされそれどころじゃなくなってしまって完全に戦意喪失してしまっていた、ぐぬぬ


前回と同じ程度の順位を取ったのでレートがどうなるんだろう、なんか過大評価されてる感じがしなくもない

AtCoder Grand Contest 019(AGC019)

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder
touristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtourist!!!
出てました、いまさら感ありますがせっかくのtourist回なので
前回のABC/ARC解説配信で次回は歴史的な回になるとか言われたのでまあ予想通り(?)でした

結果は2完、CとDがまるで分らず、辛かったのは考察を練れば解けるのか、アルゴリズムを知らないと解けないのかわからないこと
それなのに考え続けるしかないこと

A.Ice Tea Store
Nリットルのアイスティーを買う
0.25L,0.5L,1L,2Lずつでしか売られてなくてそれぞれ値段が違う
”ちょうど”Nリットル買いたいとき必要な最低金額を出力

最初はDPかと思って焦ってしまった
買い方パターンは実際は少なくて
0.25をNになるまで買う
0.5をNになるまで買う
1をNになるまで買う
2をNになるまで買う or N-1まで買って残り1L分だけ上の3つのどれかで埋める
なので7通り
全て求める式を書いてminとってオラァって投げたら通りました


B.Reverse and Compare
英小文字からなる文字列がある
区間を選んで1回だけその区間を反転させる事ができる
何通りの文字列が出来上がるか答える

どうしていいかわからなかったのでとりあえずサンプルをノートで実際にやってみた
反転する箇所を選ぶ通りはn*(n-1)*0.5通りあることが分かったため文字が被らなければそれが答えであると分かった
また回文を反転させると同じものが取り出せるので、全通りから回文の個数を引いて出力すればいいのでは?と思ってコードを書いた
コードを書く前に試せばよかったがサンプル3が当然合わない、親切流石tourist
サンプル3をノートで試していると「abca」のような文字列があったときに
1-4で反転したものと2-3で反転したものが同じであることが分かった
つまり同じ文字で囲まれた区間は反転すると同じものが取れる、これは回文でも同じように出来るっぽい、証明は自信がない

例えば「abcadeafga」のような文字列だった場合
f:id:ratetion:20170901040554p:plain
こんな感じで同じ文字の間が出現する
のでこの場合は全通りから6を引けば答えになる
これを全探索したらTLEした、馬鹿である

各文字の出現回数を全て求めて、n個だとすると(n-1)+(n-2)+...+2+1をそれぞれ足し合わせて全通りから引いたらAC
500点問題だったのでそこそこ嬉しかった
Submission #1541862 - AtCoder Grand Contest 019 | AtCoder
ノート
f:id:ratetion:20170901040908j:plain
こんな感じでほとんど回文についてとサンプルについて考えてた、気づけば早かったらしい

この問題は是が非でもサンプルに「tourist」を入れるべきだった、許さない

f:id:ratetion:20170901041819p:plain

C.Fountain Walk
900点問題だしここまでかなぁって思ったけどとりあえず開いた
グリッドの街があって各通りに多くて1個噴水がある
スタート地点からゴールまで歩くんだけど噴水があったらその周りを通る
最短距離を出力

噴水は1/4歩く場合は近道になって、1/2歩く場合は遠回りしていることがわかる
また1/2は、条件から各通りに噴水が1個と分かっていることを考えるとせいぜい1回通るか通らないかだと思った
ただ1/2を2度通っても1/4いっぱい通ったほうが得とか、そんな状況はあり得るかわからなかった
方針としては通れるだけ1/4を通ってなるべく1/2を避けるルートを選び、通った個数だけ直線での距離から変更を加えてやればいいと思った
通りの本数がでかいので単純に経路探索は無いだろうという感じ
うん、わからない
終わってから解説読んでもさっぱりじゃった、そうじゃった、、、
いつかチャレンジしなおします



水色になりました
8月中に水色を目標にしてたので嬉しいです、運がよかった
f:id:ratetion:20170901041549p:plain
AtCoder

Educational Codeforces Round 25(ECR25)

出ました
Educational Codeforces Round 25 - Codeforces

こどふぉは前から出てみたいと思っていたので適当にググって参加方法を参照して登録して参加した
以前SRMにも出たので同じ感じで(結果がしょっぱかったので参加記書くか迷って書かなかった)

A.Binary Protocol
1の個数がその桁の数字を表すので数えて出力したらAC
問題文の理解ができなくて最初普通に二進数を十進数に直すコードを書いてそりゃ合うわけないわなって言ってた
なんでだ

B.Five-In-a-Row
5目ならべ、次の1手で勝てるかどうかを判定する
とても愚直に全探索を実装した
これに時間がかかったしバグ生えたしまだまだだなと思い知らされた
実装力が足りなさすぎる

C.Multi-judge Solving
通せませんでした
問題を誤読しているのかもしれない

nは問題数
kはすでに解いた問題の最高難易度
以降aはそれぞれ問題の難易度
で、解ける問題はそれまでに解いた問題の最高難易度*2以下の問題
解けない問題はいくつありますか?

だと思ってたらテストケース6が通らず
で、解けない問題をカウントして解いたことにして進めたらテストケース7が通らず

#include "bits/stdc++.h"
using namespace std;

int main(){
	long long int n,k;
	cin>>n>>k;
	
	long long int cans=k;
	vector<long long int> a(n);
	int ans=0;
	
	for(long long int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	
	for(long long int i=0;i<n;i++){
		if(cans*2<a[i]){
			ans++;
		}
		cans=max(cans,a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

そんなところでタイムアップだった
次回以降も出ていきたいし英語問題にも慣れていこうと思う
明日はTwitterでいいねしていただいた数だけAOJ自明埋めていきます

ぜひいいねして私を追い込んでください

ACM-ICPC 2017 国内予選 参加記

Yurahuna氏、Yazaten氏と共に参加しました「sparsely_populated_regions」というチーム名で参加しました
飲んできたので覚えてないとかを言い訳に雑に書きます

会場に集まったら各チーム準備をしていた
開始したらまず画面にB,C問題を表示して下の方でテンプレを写す部分を担当する予定だったが、開始直前でプリンターの動作が怪しいとかでA,Bを表示してYazaten氏がテンプレを担当に、私はAを読むことに変更した
時間がない中でうまく回ったのですごいと思った

A問題は読んだら二分探索をしそうだと思ってしまったが、メンバーに説明する段階でそれはないと言われ、説明中に全探索で行けることも気づいたので後は実装するだけだった
二人はもう少しで何とかなりそうって感じだったので実装をした
コードはささっと書けたがcinを忘れるとかやらかしてサンプルをバグらせていた、緊張し過ぎである、開始前には反復横跳び等をしていた人物もいた

軽くYazaten氏がフォローしてくれてAC
どうすればいいか二人を見てみるとYurahuna氏がBを書ける、Yazaten氏がC解けそうだったのでDを印刷して読むことに

D問題は読んだ感じ自分では無理だと思った、無理だと分かった事を褒めよう(?)
誤読をしないように丁寧に読み直してサンプルをすべて図示した
そこで多分bitDP(書けない)を使うんじゃないかと思ったがこれを伝えて固定観念を与えてしまって違った時が痛すぎると思ってノートに書いた文字を消した
制約が妙だったのでしっかりメモしておいた
f:id:ratetion:20170714231559j:plain
そこら辺でYurahuna氏がBをAC、Dを聞きに来てくれた
丁寧に読んでいたので説明がスムーズに出来たようでよかった
再確認とかをしていたらYazaten氏がCをAC、Dを聞きに来てくれたので二人にDを任せてE,Fを読みに行った

Eは構文解析で、論理回路っぽい問題だった
論理回路をしっかり理解してなかったのでやばいと思ったが、説明自体はそれほどでもないので軽く読む程度にしておいた

Fはなんだかひたすら考察をしそうだと思ったので、サンプルを図示した上で、紙を実際に折って確かめ、全分岐を3回分まで図示した
なにか法則っぽいものが見えたが難しい
f:id:ratetion:20170714231618j:plain

二人がDを通してくれた、この時点で100分経過程度だったと思う
割とDを通してるチームが多く、もう1問無いと危険かもしれないという空気が流れていた
Yazaten氏にEを説明、Fの方が解けそうにも見えたので聞いてくれないかと言ったがEが解けそうらしいので信じることにした
二人が分担して実装と考察をしていたのでそれのフォローに入った
こんな方針でやろうと思ってるけど違和感あるかとYurahuna氏が問うてくれたのでそれに関しては平気っぽそうだと思った
テストケースを書いたり確認したりひたすらしていたら、Yazaten氏が実装をかなり進めていてよさそうな雰囲気だったがタイムアップになった

4完じゃ怪しいと思っていたので微妙に悔しいような感覚だった
結果は4完の35位でした
最初の3問を素早く通せたのがよかったっぽい
しかし自分はAでくだらないミスをしてしまったし、WAを吐いていればかなり順位が落ちていたっぽいので反省しかない

それでは2次会へ行ってきます
今日はお疲れさまでした

ICPC模擬国内予選2017参加記

2017/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group

本番に出るチームで参加しました
結果は4完でした
チーム名はsparsely_populated_regions(限界集落)(575)
チームメンバーの開始直前のツイートです



時系列で書いた方が面白いかもしれないのでそのように
内容は忘備録程度なのでいつも通り雑に書きます

二人がライブラリを印刷していたが、自分はまだ全域木とかしか無いしそのような実装は時間がかかりすぎて任せるしかないので、基本的だけど書き方に自信がない物だけ用意しようと思った
印刷場所が遠いので手書きにした


事前に私がA,ゆらふな氏がB,やざてん氏がCと決めていたのでまずA問題を読んだ
みんな読み終わった段階で私だけ理解できてなかったのでもう一回読んだらすぐ解法が浮かんだ

A:問題がn個与えられる、それぞれの難易度が1~mで与えられる
各難易度から1問ずつ出題し、合計でm問出題する
しかし各問題には推薦度が決められておりそれが最大になるようにする
配列でmaxを持っておしまい
だったけど添え字をミスったのでサンプルが通らなかった
二人が声をかけてくれてゆらふな氏が指摘してくれてAC

ゆらふな氏が読んでたBのヘルプに入る
問題文の解釈がややこしくて二人で相談しているうちにやざてん氏がCを通してくれていた
後で問題の概要を聞いたけどどうも混乱しそうだった

やざてん氏の手が空いたのでゆらふな氏にDを頼んでBをやざてん氏に読んでもらった
先に問題の概要を説明しようとしたが、問題を理解してないのに説明しても意味がないと後で思ったしその時本人が止めてくれた
この隙にBのサンプルを図示しようとした
読んでもらったらすぐ実装できそうとのことで実装を頼んで、図示が終わり次第Dを読み始めた

Dもまた問題文がややこしいけどなんとなくわかったなぁと思っていたらゆらふな氏がサンプルの動作を実際に説明してくれたのでわかりやすかった
なんとなく二分探索しそうだなぁと思ってたらゆらふな氏が同じことを言っていた
クリアできないケースについては整理でき説明できたのでよかった
しかし本当に二分探索でいいと言い切れず、二人がDPを使ってはどうかと言い始めたあたりで話について行くのがやっとだったので離れて別の問題を読むことにした

Eを開いたら数学っぽくて今まで解いたことのないジャンルだと感じたので読まずに飛ばした

Fはマトリョーシカ風に立方体を入れ子にしてなるべく一番外の立方体の体積の合計を小さくする問題だった
条件は直感的でわかりやすいし伝えやすい、後は何か具体的なアルゴリズムを知っていれば解ける系なんじゃないかと感じたのでやざてん氏に相談したら解けそうとの事で考察を任せ、サンプルを図示し始めた
二人とも多分Dから離れゆらふな氏はEの考察をしていたと思う
この図示が難しくて妙に時間がかかったがミスするよりはいいと思った

図示の合間にやざてん氏がFで使うらしいライブラリの写経を少し手伝った
キーボードがHHKBかmacbookのJISを用意していたがHHKBの十字キーがわからずmacbookを使って書いていた
緊張してミスタイプが多かったので確認してすごく遅い写経になってしまった

やざてん氏の考察が終わったので写経を代わってもらって終わり次第実装に入ってもらった
私は図示の続きと確認をして納得がいったので後半の問題で優しそうなのがないか探していた
f:id:ratetion:20170702232910j:plain

やざてん氏がバグを吐いていたのでヘルプに入った
バグが起こってそうな部分を雰囲気だけで伝えてみたが、どんな実装なのかあんまりわからなかったので下手なことをいうより考えてもらった方がいいと思ったので端的に伝えて答え合わせとかの準備をしていた
答え合わせが多少スムーズになったので悪くはなかったと思った
時間かけてバグを取ってAC、ここで4完、残り30分弱だったと思う

ゆらふな氏がEが解けるとの事で使うライブラリの写経を投げてきたのでどこを写すか整理してやざてん氏に投げていた
写経速くてやべえと思った、やべえ
写経が終わったらゆらふな氏が実装に入ってくれたので写経部分のミスをひたすら探すお仕事をした
2個ほど見つけられたのでまあやることがあってよかったなぁと思った
実装間に合わずタイムアップ
ABCFの4完でした

自分はほとんどキーボードに触れず考察と図示サポートをしていたので、問題や解法をうまく伝える能力がもっと必要だなと感じた
また添え字ミスとか露骨なミスを減らさないといけないなぁと思った

3日連続でSRM,ARC,模擬国内と出たので充実した3日間だった
おわり

AtCoder Regular Contest 077(ARC077)

AtCoder Regular Contest 077 - AtCoder Regular Contest 077 | AtCoder
出ました、出ました
自宅で4人でオンサイトごっこしながら出ました
結果は1完の終了後にDも通しました

C.pushpush
数字がn個与えられる、これを

1,数字を後ろにくっつける
2,逆向きに並び替える

という操作を繰り返していく
最初は文字列にして処理してやろうかと思ったけど、よく考えたら
1,2,3,4,5,6と与えられた場合
6,4,2,1,3,5
という風になる
出力順を見れば後ろから1個飛ばしで出力したのち前から1個飛ばしで出力している
これをループさせてAC
終わった後で友達がTLEを吐いていたので聞いてみると先頭に追加していたが、その部分ですべての要素を1ずつずらす処理が入るためだった
dequeueを思い出したので勧めたらACしていたのでよかった
思考放棄かとも思うが速いので

D.11
n+1の数列が与えられる、その要素はn以下の数をすべて使っているので1つだけ2回登場する数がある
これらの部分列の個数を1~n+1までそれぞれ求めて出力
しばらく考察をした
同じ数を見つけてそれの左にある数字の個数と右にある数字の個数をそれぞれ数えて組み合わせを全体から引けばいいと思った
組み合わせだと思ったのでとりあえずABCの問題を探した
C: 経路 - AtCoder Beginner Contest 034 | AtCoder
フェルマーの小定理を使わないと1e9+7で割ったあまりをうまく求められないことを覚えていたので(今後当たり前になるらしいのでテンプレ化予定で)
なんとなく理解しそれとなく実装しておいた

で、実装するとかなり惜しい答えが出たが合わない
あちこち見直し頭を抱えてたらタイムアップ
終わったらY氏が華麗に解説してくれた

例えば
1234567489を考える
4が同じ数なので左の4の左に数字が3つ、間が開いて右の4の右に数字が2つ
2数からなる部分列でダブるのは14,24,34,48,49となる
この場合は私の実装でもうまくいく
しかし3数以上を考えるときダブるのは124,134,234,489まではいいが、4の外を両方使ったを使った148,149,248,249,348,349が数えられてない
なので正しくは左から選ぶ通り、右から選ぶ通りではなく、左右の合計から選ぶ通りを引けばよかった

実装したら通らなかったのでTwitterに投げたら、c++では負の値の余りを計算すると正にはならないらしく、負のまま出力されていたらしい
1e9+7を足したうえで余りをとるように変更したらAC
ありがとうございました

学ぶことが多くていい回だったなぁと思いました

AtCoder Regular Contest 076(ARC076)

AtCoder Regular Contest 076 - AtCoder Regular Contest 076 | AtCoder
出てました
そっちかよって感じですが今日のも後で書きます

C.Reconciled?
犬と猿の数が与えられるから、交互に並べる通りを数えてください
犬猿は区別します
犬と猿の数の差が2以上だと並べられない(犬か猿が隣り合ってしまう)のでそれを場合分けで跳ねて、さらに差が0か1かで場合分けをした
それぞれ計算して終わり

D.Built?
これにとても苦戦して5時間かかりました、最近のARCは長いなあ(?)
街の座標がx,yで与えられる、これらの街に道をひいてすべての街を行き来できるようにしたい
この時道のコストがa,bとc,dの街の間でmin(|a−c|,|b−d|) 円かかる
最低で何円必要か

最初に問題を見て最小全域木だと思った
最近Y氏が教えてくれた奴だ、やったぜ
しかし制約を見て無理だと分かった
しかし色々考えた結果最小全域木が蟻本に載ってるってことはそれ以上のアルゴリズムはないってことだ(?????)
まあほかにいい方法が思いつかなかったので図をいっぱい書いて考察を練ってた
x,yそれぞれソートしてみたら引くべき道が絞れてきて、(n-1)*2本でいいことが分かった
これに対して最小全域木を作れば行けると確信し始めて実装を書き始めたらタイムアップになった
TLを眺めてるとどうも正解っぽくて悔しいやらうれしいやら

という事で実装していたら5時間かかってしまった
Submission #1379815 - AtCoder Regular Contest 076 | AtCoder
忘備録だから書いたつもりだけどうまく書けないし多分忘れることもない問題になってしまった

ABC056 C.Go Home

C: Go Home - AtCoder Beginner Contest 056 | AtCoder
解きました
一回諦めて時間空いてたシリーズ
カンガルーがi時間経過時にiの距離ぴったりジャンプできる
入力された値の位置に行けるまでにかかる時間の最小を求める
最初見た時どうしていいかわからなかった
最近考え直していて気付いたのだが、1-nまでの数字を選んで足し合わせると、総和までのすべての数が作れる
で、当然1から足していってnを超えたらnまでの数は全て作成可能である
計算量は10^9で10^5ループ程度だったので普通にAC
細かいことを言えば10^9は44721ループだったのだが何か求め方とかあるんですかねぇ
Submission #1333576 - AtCoder Beginner Contest 056 | AtCoder