りにゅうしょく

競技プログラミング 日常

2020年に購入した二次元のあれこれ

※競プロ関係ない記事です

amazonへのリンクはアフィリエイトとかつけてないのでクリックしても大丈夫です(私が得したりしないです)

 

・潜熱

潜熱(1) (ビッグコミックス) | 野田彩子 | 青年マンガ | Kindleストア | Amazon

1巻だけ買ったけど主人公の性格が好きではない。ヤクザおじさん×女子大生だけど、表紙にはおじさんの顔が載ってないし、主人公の心の動きを味わう漫画なのかも?

 

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~ | 秋葉拓哉, 岩田陽一, 北川宜稔 |本 | 通販 | Amazon

実は今年買った。枕として使っている(訳:全然やってません。生きる価値なし)

 

ポケットモンスター ソード

Amazon | ポケットモンスター ソード -Switch | ゲーム

ネズさんが好き。全体的に男性陣のキャラデザがエッチだと思います(主観)

 

・マイ・ブロークン・マリコ

マイ・ブロークン・マリコ (BRIDGE COMICS) | 平庫 ワカ | マンガ | Kindleストア | Amazon

読むと非常に心がしんどくなるけど良作。絵が死ぬほど好き。百合好きなら読むと楽しめそう。表題作ではない方の作品もよかった。

 

ラノベのなかの現代日本

ラノベのなかの現代日本 ポップ/ぼっち/ノスタルジア (講談社現代新書) | 波戸岡景太 | 日本の小説・文芸 | Kindleストア | Amazon

ノスタルジア・家制度のくだりで啄木やら寺山修司やらに触れておいて落としどころの具体例は変猫。無理やりすぎる。他の部分は面白かった。

 

・お気に召すまま?―世界でいちばん大嫌い特別編

お気に召すまま?―世界でいちばん大嫌い特別編 (花とゆめCOMICSスペシャル) | 日高 万里 |本 | 通販 | Amazon

白泉社のアプリで「世界で一番大嫌い」を一気読みした後にこれだけ電子書籍化されてなかったので買ったけど、中身はマジでないし本庄(男)のことが本気で好きな人だけ買えばいいと思う……。

 

・うらみちお兄さん(1~最新刊)

うらみちお兄さん: 1 (comic POOL) | 久世 岳 | マンガ | Kindleストア | Amazon

面食いなのでいけてるお兄さんが好き!あと二次元のイケメン喫煙者は最高なのでうらみちお兄さんも好きです。

 

・絶対BLになる世界 VS 絶対BLになりたくない男

絶対BLになる世界 VS 絶対BLになりたくない男(1)【電子限定特典付】 (FC Jam) | 紺吉 | マンガ | Kindleストア | Amazon

短編ギャグ。めちゃくちゃ面白いので買ってよかった。

 

・隣の席の変な先輩(1~最新刊)

隣の席の変な先輩(1) (BABY G-Side) | うすくち | ティーンズラブ | Kindleストア | Amazon

タイトルが「隣の家の少女」みたいでイヤな感じだけどただのTL漫画。致してないのにスケベだった。ムキムキ卑屈サイコインキャのイケメンが刺さる女は読むべき。

 

・Sante!!

Amazon.co.jp: Sante!!('17年花組・東京・千秋楽)を観る | Prime Video

 宝塚に興味を持ち、この公演で沢田研二の「あなたに今夜はワインをふりかけ」を歌っていると聞いてレンタルしたけどカットされてた。ショック死

 

・スキップとローファー(1~最新刊)

スキップとローファー(1) (アフタヌーンコミックス) | 高松美咲 | 青年マンガ | Kindleストア | Amazon

ほっこりする少女漫画で、頭を使いたくないときでも読めるし癒される。恋愛要素がそんなに強くないので無心にイケメンを拝みたいときには不向き。

 

女の園の星

女の園の星(1)【電子限定特典付】 (FEEL COMICS swing) | 和山やま | 女性マンガ | Kindleストア | Amazon

買ってよかった最高の漫画。動物のお医者さんとかすきなオタクに刺さりそう。絵が好きだしゆるい笑いがずっと展開されてるのがかなりツボに入った。

 

・ラブ・ミー・ぽんぽこ(1~2)

ラブ・ミー・ぽんぽこ! 1 (花とゆめコミックス) | 赤瓦もどむ | 少女マンガ | Kindleストア | Amazon

作者さんが好きなので買った。全編ギャグ風味だけど、いつかは絶対もっとどろどろの三角関係になるんだろうなと考えるとつらい気持ちに……。

 

・彼のいる生活

彼のいる生活【電子限定かきおろし付】 (ビボピーコミックス) | 宮田トヲル | ボーイズラブマンガ | Kindleストア | Amazon

商業BLを読んだことがなかったので試しに買ってみた一作。そのとき、むやみにセックスしない・男同士の恋愛を躊躇う展開が必ず含まれているという条件で探してこれにたどりついた。絵もきれいで面白かったけど、私は少女漫画のほうが好きだと再確認……。

 

魔人探偵脳噛ネウロ(1~13)

魔人探偵脳噛ネウロ モノクロ版 1 (ジャンプコミックスDIGITAL) | 松井優征 | 少年マンガ | Kindleストア | Amazon

「人外と恋愛したいな~~~~」と思って買ったけどなんかちがった。でも面白かったので途中まで買った。絵がびみょう。

 

ジェンダーレス男子に愛されています。(1)

ジェンダーレス男子に愛されています。(1)【電子限定特典付】 (FEEL COMICS swing) | ためこう | 女性マンガ | Kindleストア | Amazon

頭空っぽにして読める。どのコマも顔がいい上に主人公の女の性格が卑屈じゃないのでイライラしない。でも2巻はアイドルデビューするらしいのが嫌で買ってない……。

 

・異国館ダンディ(1~8)

異国館ダンディ(1) (花とゆめ)|加藤知子|本| Amazon

 電子書籍化されてないのでママノキが全巻買ってきてくれた。絵柄がザ・昔の少女漫画!でかなりよき。男はクソかっこいいけど終わり方は唐突に連載終了したんですか?と問い詰めたくなるレベルに雑。

 

・幻奏喫茶アンシャンテ

Amazon | 幻奏喫茶アンシャンテ - Switch | ゲーム

人生で買った中で一番好きな乙女ゲームアンシャンテみたいな作品がオトメイトから出ると思わなかった……。とにかく人外との様々な恋愛を味わいたい女向け。糖度は低めで、あとパッケージほどほのぼの系ではない。

 

・囚われのパルマ refrain

CAPCOM:囚われのパルマ Refrain 公式サイト

良作。前作二つよりもダークサイド要素がちょっと強めだけど、BADENDないし安い(850円)ので乙女ゲーム初心者にごり押ししたい。

 

・彼女が僕に微笑めば

彼女が僕に微笑めば [文苑堂] | DLsite 成年コミック - R18

某二次創作で有名な作家さんの単発作品。乳がデカくて優しくてなんでも包み込んでくれる女の子が好きなので買った。相変わらずめっちゃえっちだった。

 

・ドルンベルクの首斬り人

ドルンベルクの首斬り人 [JUNK or SKY] | DLsite がるまに

絵柄で敬遠する人もいるかもしれないけど、めっちゃ面白い(エロ要素は期待しない方がいいです)。主人公の性格とかが色々すごい。これで110円なの意味が分からないので絶対に買ったほうがいい。

 

 ・サイコアパタイト

サイコアパタイト [offoffo] | DLsite がるまに

ある時から突然(?)女性上位ばっかり出すようになったoffoffoさんだけど、それでも好きなのでお布施のつもりで買った。しんどいけどハピエンなので耐えた。

 

・ヒトツノ森

ヒトツノ森 [ミナプラス] | DLsite がるまに

詰んでるので時間を見つけてやりたいところ……。

 

買ったものを把握できてないので思い出し次第追記します。全然オタ活できなかったので来年はもっとしたいな……。

 

Codeforces Round #634 (Div. 3) バチャ参加記

https://codeforces.com/contest/1335
A, B, C, Dの4完でした。

A. Candies and Two Sisters

N個のキャンディを、a>bになるようにaとbに分配するときの組み合わせの数。\frac{(N+1)}{2}-1が答えになる。

B. Construct the String

Aは答えに関係ない。条件を満たす文字列を作るとき、最初のB文字はabcde……みたいにばらばらにする。以降、B≤i≤N文字目は、i-B文字目と等しいものをつなげていけば、どの連続するB文字を取ってもちょうどB文字バラバラになって、Bより大きい連続部分列Aでも条件を満たせる。

C. Two Teams Composing

a_iの数字の出現回数をmapで管理して、そのvalueの最大値が2チーム目のメンバーの最大数候補になる。mapのsize>valueの最大値のときはvalueの最大値が答え、そうでないときはmapのsizeとvalueの最大値-1のうち、小さいほうが答えになる(valueの最大値から1引くのは、2チーム目に含まれる数字を全部2チーム目に使った場合1チーム目に入れることができないから)。

D. Anti-Sudoku

嫌な見た目(??)をしてる。
数独の仕組み的に、縦・横・3*3のハコ全部が異なるところから1つずつ適当に選んで、選んだ数字を+1すれば通る(9の場合は1にする)。

E1以降もupsolveしたら追記していきたいと思います。ねむい!

Codeforces Round #683(Div. 2) 参加記

https://codeforces.com/contest/1447
A、B、Cの3完でした。Dは難しそうなふんいき……。

A. Add Candies

サンプルがちょっと不親切というかひっかけ?だけど、1, 2, 3, ..., N個キャンディがあるときは、i番目にiの袋を選んでそれ以外にiずつ足せば、必ずN回ですべての袋が等しくなる(1つの袋に1+2+3+...+N個入る)

B. Numbers Box

位置は関係なく、負の数の個数が偶数の場合は、うまくこねくり回すことで全部正の数にできる。負の数の個数が奇数かつ0が1つもない場合は必ずどれか1つが奇数になってしまうので、1番絶対値が小さい値を負の数にする。

C Knapsack

⌈\frac{W}{2}⌉ ≤ w ≤ Ww_iがあったらそれを出力して終わり。ない場合、⌈\frac{W}{2}⌉未満の数字だけ添え字と一緒にpairの配列としてとっておいてソート。i番目までの合計が⌈\frac{W}{2}⌉未満の場合、i+1番目の数字は必ず⌈\frac{W}{2}⌉未満なので、i+1番目を足してもWを超えることはない。前から足していって⌈\frac{W}{2}⌉以上になった時点で出力。

ABCの後に出たけどあんまり疲労感がなかった。昼寝のおかげかも?

Codeforces Round #677 (Div. 3) 出たよ~~~

https://codeforces.com/contest/1433
結果:ABCD4完、微冷え

A.Boring Apartments

1~10000まで部屋があるアパートで、1→11→111→1111→2→22→……と、ゾロ目のところにだけピンポンダッシュする。部屋ナンバーNの人が出たとき、今までピンポンダッシュした部屋のナンバーの桁数の和を求めるというやつ。
部屋ナンバーの末尾をA、桁数をBとすると(A-1)×10+(1~Bの和)ってなる。

B.Yet Another Bookshelf

N冊の本を収められる本棚があり、0のときは空で1のときは本が入っている。1回の操作で、本を右か左の空いている部分に移動させることができる。本を収納している部分を全て連続させたい場合、何回の操作が必要か、というやつ。
前から順に見て行って、最初の本が出てきてから空白を数える。次の本が出てきたら今までの空白を足して空白カウントを0にする。

C.Dominant Piranha

N匹のピラニアがいて、i番目のピラニアの大きさはA_i。一度の操作につき、左か右のピラニアが自分より小さい場合に、そのピラニアを食べることができる。共食いしたときに最後まで残るのは何番目のピラニアか、というやつ。
全てのピラニアの大きさが等しいとき、-1。そうでないときは、一番大きいピラニアの内左右いずれかの大きさがそれより小さいもの。

D. Districts Connection

N個の都市があり、i番目の都市には番号A_iが割り振られている。都市間にN-1本の道を作ることにする。割り振られている番号が同じ都市同士を直接繋がずに、すべての都市間の行き来を可能にすることはできるか。できる場合はその組み合わせを出力する、というやつ。
全ての都市の番号が同じとき、-1。そうでないときは、1番目の都市と番号が違う都市は全部1番目につなぐ→まだ使ってない都市について、また番号の違う都市に適当につなぐ……を繰り返したら通ったけど、なんで通ったのか微妙にわからない……。

E. Two Round Dances

まず問題文が読めなくて困る
n個ボールあるからn/2個ずつに分けて輪っかをつくるんだけど、輪っかの作り方は何通り?(byじゅぴろさん)(ありがとうございます!!)
	a(n) = (2*n + 1)!/(n + 1)らしいです。(OEISに投げた、ここのnはN/2)
これが大量に通されているのでへこむ

こどふぉ、出る前は出たくね~~って思うけど冷えてもあまり深刻に受け止められない分ちゃんと出て学びを得ていった方がいいなと思いました

競プロキャンプ2020関西 参加記

※この記事では競技プログラミングについて何も書いていません


競プロキャンプ2020@京都 - connpass
9/26~27に↑に参加しました!とっても楽しかったです!
既に記憶がうろ覚えなので頑張って呼び起こしています 文章は支離滅裂なのでフィーリングで読んでください

1日目

12時に京都駅集合だけどみんな早く来ていて焦る 11時40分ごろにつくと既にたくさん人がいた サンドイッチを食べてたらかわらさん・まつかわさん・モジャンボさんが来る モジャンボさんがジャンボでびっくり……!!
京都駅から宇治に移動してレクへ
自己紹介中はいずらいとさんの隣に座ってました 髪の毛が超さらさらで無限にびっくり
「数探しゲーム」ではRyukiさん、かわらさんと同じチームでしたが全く役に立てず…… 何問目かでかわらさんがFAを取っていてすげ~すげ~~となりました
次に落語を聞いてから「チーム対抗聖徳太子ゲーム」をやりました(1つお題を決めて、そのお題に沿った単語をチーム全員で一斉に叫び、回答者はそれを聞き取る……みたいなゲームです) 私のいたチームではお題を「お菓子」にして、じゃがりこジャガビー・ポッキーなどなどに加えて「タラタラしてんじゃねーよ」を入れました まつかわさんに力の限り叫んでもらったところ、全チームがタラタラryしか聞き取れていなかったので作戦勝ちです(?)(まつかわさんに怒鳴られたらムッチャ怖そう、それはそう)

レク施設を出たあとは、駅でのいみちゃん・じゅぴろ・Hyadoくん(全員Topcoderに出てた)と合流
じゅぴろがのいみちゃんを指さして「こいつめちゃくちゃ邪悪だわ」と叫んでいたので不安になる
宿泊施設にはタクシーで向かいました タクシー待ちの間にkichiさんとのいみちゃんが対面 のいみちゃんに名乗るのをためらうkichiさんを見てめっちゃ笑うなどしました(最悪)

宿泊施設に着いて、雨が小降りになってからBBQを始めたんですが、この時点でかなり時間が押していました 各々の荷物を分解してBBQの材料を分ける段階でもかなり時間がかかってしまい、お酒を飲みながらお腹すいた~と叫んでいました(準備もちゃんと手伝ってました!)(弁明)
酔っぱらってきて運営お手伝いのkakiraちゃんさんに「カワイイ~~~~~~~~」って絡んだら年上で死ぬほどビックリしました 本当にすみませんでした
そこそこお酒が回っていたものの、「ratedなのに出ないとかあるか?」というじゅぴろ大師匠の圧に負けて、肉数枚とお菓子ちょっとを食べた時点でBBQを離脱することに……(´;ω;`)(誤解のないように言うとじゅぴろさんは他の参加者にはそんなハラスメントはしてません)
しかも施設の風呂が21:30までだったので、BBQを20時過ぎに抜けた後10分で風呂に入り、髪の毛も乾かさずACLBCに出ることに 女子部屋は私のみなのにかなり広かったため、ありがたくじゅぴ・かわらと占領させてもらいました(途中でまつかわさんやのいみちゃんも来た)

スギノキ「イケメンにすっぴん見せたくなかったな……」
のいみちゃん「いいからコンテストに集中してください(正論)」

コンテストは3完微増なので冷えはしなくてよかったです。

終了後はじゅぴ・ノキ・かわら・まつかわ・のいみ・Hyado・沙耶花(・きたむーくん)で「インサイダー」というボドゲをやりました 
後からふるやんさん・いずらいとさん・(武雄さんとかもいらっしゃった気がする?)など、さらにたくさんの人が来て、まつかわさんが出題者になってくれて「ウミガメのスープ」をやりました 文系なので(?)結構解けてたのしかったです(?!)
そのあとは雑談してるうちにかわらさんが床で寝落ち、じゅぴのいみノキも床で寝落ち……という感じで、死体が床にごろごろと転がる

2日目

朝起きる・ご飯食べる
スギノキ「のいみちゃん一人だけ最後まで寝てたね」
のいみちゃん「寝てる間にスギノキさんに1、2回蹴られました」
緑なのに ころされる ごめんなさい

BBQの片付け&部屋を出た後、2時間の自由時間に
歩いて20分のところに展望台があるそうなんですが、疲れていたので私には無理だなとなる
じゅぴろ「バチャやるか」
マ~~~~~~~~ジで言ってる?突発的にCodeForces#498(Div.3)のバチャが立つ(緑が私だけで、橙・青等がたくさんいるにも関わらず、Div.3を選んでくれたのはめちゃめちゃ配慮してもらったと感じているので本当にありがとうございます……)
最初は5人くらい?でバチャするか~みたいなノリだったのに、気づいたら10人以上集まっていて、やっぱりみんな競プロ好きなんだな~とおもいました
いざやってみるとBが解けなくてえーってなる Bは通したけどCは間に合わず (Div3にしては)ちょっと難しかったらしいです 精進不足…… 
バチャが始まってすぐに、幹事の方から「ゴミ捨てを手伝ってくれる人が2人欲しい」と言われたんですが、のいみちゃんとじゅぴろが「ハンデあげるか~」といって快くそちらへ向かったのを見てかなり社会性を感じました(すごい)

自由時間の後は喜撰茶屋でお昼ご飯を食べる ここでdokinさんなど2日目だけ参加の人と合流
なんか修学旅行?の学生にめっちゃガン見されて笑われてたらしいです、気づかなくてよかったぜ(??)
ここで閉会式なども行って、一度解散のような形になりました

スギノキ「平等院鳳凰堂見たいね」
かわら「別に 10円玉に書いてあるやん
じゅぴろ「全く同じことをHyadoも言ってたよ
社会性の見分け方です 参考にしてください!
結局、かわらさんの財布には10円玉がなかったので平等院鳳凰堂に行きました(?) 誰が作ったんだっけ?藤原のなんとか?とか言ってたらふるやんさんが「藤原頼通だよ」と教えてくれて知性の差を感じました……ウ

Hyadoくんはチームで出たい5時間バチャがあるため?、平等院はテキトーに見て、カフェ的なところに入る
じゅぴ・ノキ・のいみ・かわら・まつかわ・沙耶花・Hyado・ふるやん・dokin・しんちゃんでのんびりだべりました
議題:関西人全員うるさい問題・関東では冗談のハードルが鬼高いという噂・かわらさんは別に静かではなくない?(byのいみちゃん)・ラブライブ!の女は絶対百合じゃないだろという提案(byスギノキ)
私が高専在学時に問題を起こしてた先生を明石高専のしんちゃんくんも知っていて親近感がわきました(明石から期間限定で奈良に来ていた先生だったため)

帰りは京阪組とJR組に分かれて、のいみちゃん・じゅぴろと京橋でラーメンを食べました ふっぴーさんは邪悪って聞いたけどほんとですか?(?)

総括

・いずらいとさん、ふるやんさんなど話したことがない方と話せて非常によかった
・キャンプで食べれなかった分の肉はじゅぴろにたかっていいらしいです!やったー!
・幹事のみなさん、参加者の方、本当にありがとうございました

お布団を温めた初チーム戦(WUPC2020&HUPC2020 1日目)感想

WUPC2020

https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/
早稲田生による有志コン、WUPC2020にれたすさん(@fairly_lettuce)、mo3tthiさん(@mo3tthi)とチーム「melomelody」で参加しました。
チーム戦が初めてなうえに二人とも初めて話す人(mo3tthiさんはFF外)で、しかも私だけメッチャレートが低い(れたすさんは水、mo3tthiさんは青)だったのでビビってましたが、お二人ともすごく気さくな方でした。
結論から言うととにかく足を引っ張りまくってしまったんですが、とても勉強になりました。早稲田の方たち、そして組んでくれたお二人ありがとうございました……。
最初は私がAやる→れたすさんがBやる→その間にmo3tthiさんがC以降を読んで解けそうな問題を探す、という方針を立ててもらいます。Aを出したらCE。なんで?!(using Graph = vector>;を消したら直りました、C++17で提出しなかったことが原因かも)
れたすさんがBを実装している間に後ろから問題文を読み進めていきます。Mはやることは分かりやすい気がする(?)木グラフの問題だったんですが、ぱっとイイ感じの実装方針は全く思い浮かばず、一回どっかからBFSなりしてどうしたらいいんだろう?とか考えてました。次に見たLは自分の手に負える見た目ではなかったのですぐに諦めました。KはLより問題文の意味は理解できたけど、解き方が全く思い浮かばなくてこれも飛ばします。mo3tthiさんがIまで読んでくださってたのでここで合流します。

以下、かなり記憶があやふやなので時系列が間違ってるかも
mo3tthiさん「Fはいけそうです、よければスギノキさんどうですか(菩薩)」
スギノキ「じゃあF見てみます、後ろ三問だとMが難しくなさそうに見えました」←ほんまか???
Fを見てみると、2のべき乗をイイ感じにイイ感じすればACできそうなのはそうなんですが、細かいところは全然わかりません。ここでmo3tthiさんが大まかな方針を説明してくれるんですが、私がテンパりまくっていて、死……。結局、Cを解き終わったmo3tthiさんが実装してくれます(ほんとにすみません)。あとから3人で解説見て、「2のべき乗全部見ても全然間に合うんだな~~~」とへこむなどしました。
私がFを見て布団を温めている間に、Mは1回移動するごとに変動する距離はたかだか1だから何とかなるはず、と言ってれたすさんが頑張ってくれます。

mo3tthiさん「GはDPなんですが、スギノキさんはDP得意ですか」
スギノキ「えっとえっと緑コーダー並みって感じです」←ほんまか???????
「休憩とか考えないで普通にDPした場合」の結果を利用してあれこれできないかな、と思ったんですが、私が思いついたのは「普通にDPした場合のやつに上書きして、i分目から休憩した場合~」みたいなわけのわからん考え方だったので普通に却下です。次に、mo3tthiさんが「休憩回数を決め打ちしてdpするのはどうですか」と言ってくれて、そこから実装してくれますが通らず……。
スギノキはとくに何の役にも立てないまま5時間が経過しました。
ここで、DPを雰囲気でしかやってきてないなという気づきと反省が生まれます。DPぽいなと思ったときは実装しながら添え字ガチャ!(素振り)てなことをしているので、私には緑並みどころかDPパワーは全くないのでした。DPバチャなどできる範囲で苦手意識を克服する努力はしていたつもりだったんですが、いざやってみると全く身についていないなと感じました。

HUPC2020 Day1

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2020Day1/info
ntkさん(@ntk_ta01)、SEELさん(@Seadogg012)という、レートが近く個人的に気になっている二人とチーム「grin」で参加することができました。3人ともレートが緑中盤くらいという感じです。一応現在のレート順にかんがみて(?)SEELさんがA→スギノキがB→ntkさんがCという方針を立てました。

SEELさんがAを通してくれたあとも、私はBが全然解けていませんでした。
スギノキ「全くわからないです」
ntkさん「この記事どうでしょう」
↓つるさんの「imos 法を線形代数で理解・一般化して,フィボナッチ数列でも足せるようする」記事
https://theory-and-me.hatenablog.com/entry/2020/08/23/182712
スギノキ「全く、分からないです……(勉強不足のため)」
しかしimos法でやれるっぽいことは分かりました。ここで「区間に等差数列を足す imos法」でググります。
アルメリアさんの記事「等差数列の重ね合わせを求める」章
https://betrue12.hateblo.jp/entry/2019/10/19/163736
完全に答えが載っています!やった~~~~~~~!!!!!!!!!!!!!!!ここでなぜか実装をバグらせますが(は?)ntkさんが直してくれてACしました。

次にCについて全員で考えてみます。
ntkさんの、Nが小さい場合とそうでない場合で分けてみるのはどうか、というのを聞いて確かに~~~ってなり、とりあえず小さい場合のbit全探索を書きます。小さい場合は通りました。
大きい場合については審議するうちに「N>18くらいから、答えが一意に定まることはなくなるよね」という話になり、そこから「前20桁くらいだけ見ればよくない??」と、答えに大きく前進します……!
小さい場合と似たような感じのコード(余った桁はアスタリスクで埋める)を書きましたがTLE。ここで実装をSEELさんに代わってもらいましたが、結局TLEは取れずじまいでした。あとから考えると、私の書いていたコードはN=40の場合1000000*60000くらい計算することになるのでぜ~~~~~~~~~~んぜん間に合ってないんですが、その時は分からなくて首をかしげていました……。

結果は2完でしたが、近いレートの人たちとあれこれ話しながら問題について考えることができた(かつ、3時間なので集中力のない私でも最後まで考え切れた)のでとても楽しいコンテストでした。同じ大学に競プロやってる人がいないので、ICPCとかには全然出られないんですが、こういう有志コンで積極的にチーム組んでいきたいな~って思いました。あともっと強くなってさわれる問題を増やしたいな……となりました。完。

Codeforces Round #668 (Div. 2) 出たよ~~~~

約2か月半ぶりのこどふぉ、Div.2に参加しました。結果は2完(A,B)で緑落ちです。超絶自業自得……。Dまでは他の人に教えてもらったのでブログに残そうと思います。
コンテストURL:https://codeforces.com/contest/1405

A. Permutation Forgery

問題概要

1Nまでの整数で、要素の重複なく構成された長さNの数列に対応して、以下のN-1の長さの数列F(p)を作ります。
F(p)=sort(p_1+p_2,p_2+p_3,…,p_{n−1}+p_n)
F(p)が等しく、かつP_i \neq P'_iである長さNの数列をひとつ出力してください。

考え・反省

F(p)が等しくなるためには、ペアになる要素が元の数列と同じである必要があります。たとえばN=3だったら1個目+2個目、2個目+3個目がペアになって長さ2の数列になります。合体後の順番はソートされるので、数列をreverseするだけで通ります。
↑数列を反転させれば通るのに、サンプルを見てものすごく悩んでしまって嘘解法を投げました(懺悔)

B. Array Cancellation

問題概要

A_1+A_2+...+A_n=0となるような、長さNの数列が与えられます。この中から一度の操作につきi番目とj番目の要素を選び、i番目の要素に1を足し、j番目の要素から1を引きます。i < j であった場合にはコストがかからず、そうでない場合には1回の操作で1コストかかります。
数列の要素を全て0にするために必要な最小のコストを求めてください。

考え・反省

「今まで出てきた正の数の和」を持っておき、もし負の数が出てきたらそこから引いていきます。これを最後まで繰り返すと、数列の和が0になることから、「残った負数の和」と「残った正数の和」は等しいので、その絶対値を出力します。
A_1+A_2+...+A_n=0という条件を見逃していて、無限に不可能なパターンについて考えていました。涙。

C. Balanced Bitstring

問題概要

0,1,?だけで構成された長さNの文字列が与えられます。?には0,1の好きな方を選んで置換します。この文字列の中から連続したK個(Kは偶数)を取り出した際、どの部分でも01の個数が等しくなるようにすることはできますか?

考え・反省

modごとに見るということを全く思いつきませんでした(反省)。
mod Kで等しくなる部分の文字がすべて同じで、かつ最初のK個が条件を満たしていればYES、そうでなければNOです。
たとえばS=11001100K=4のとき、最初のK個は「1100」で、1個右にずらした部分からK個取ると「1001」です。最初のK個が条件を満たしていてくれれば、抜き出す部分を1個右にずらした際に新しく部分文字列に入った文字(右端)と、左端にあった捨てる文字が等しいことで、1と0の数の均衡を保てます。
もし最初のK個の中に?が含まれていた場合は未確定にしておいて、途中で01が出てきたら確定させます(そして確定後の文字列が条件を満たすか確認します)。

D. Tree Tag

問題概要

AliceとBobはN頂点の木グラフ🌲の上で鬼ごっこをします。最初はAliceが頂点A、Bobが頂点Bにいて、Alice→Bobの順番で移動します。一回の移動でAliceは最大dA、Bobは最大dBの距離を移動できます(ここでの距離とは頂点間の辺の数を指します)。この移動を10^{100}回する間に、AliceがBobと同じ座標に辿り着けたらAliceの勝ち、そうでなければBobの勝ちです。鬼ごっこの勝者を出力してください。

考え

10^{100}回移動できる=いちいち二人の動作を追ってたら絶対に間に合わないので、何かしらの条件があるはず。移動回数が多い分Aliceが有利な気がする(?!)ので、「どうやったらBobが勝てるか」で少し考えてみます。

  • 初期配置で、Aliceとの距離がdA以上離れてないとダメ(最初の1手でAliceに追いつかれてしまうため)
  • 木の直径がある程度大きくないとダメ(Aliceがどの頂点にも1手で移動できる状態になると詰むため)

→「ある程度」がどのくらいか?を考えます。ちょうどグラフの真ん中らへんに立てば、木の直径が2*dA以下だとAliceはどこにでも行けてしまうので、それより大きい必要があります。

  • dB > 2*dA

→これ教えてもらうまで理解できませんでした……。
まず、頂点の数よりも移動可能回数のほうがずっと多いので、Bobは逃げ回るときに「Aliceのいる方向」へ逃げないといけない状況が生じます。その際、Bobの移動可能距離がAliceの「1手で移動可能な範囲」よりも大きければ、つかまってしまうゾーンを「飛び越えて」逃げ回ることができます。逆に、それよりBobの移動距離が小さい場合はどこかでAliceが1手で移動できる範囲に入らざるを得ず、捕まってしまいます。



競プロなんもわからん!解散!