りにゅうしょく

競技プログラミング 日常

Codeforces Round #617 (Div. 3) バチャ

URL:https://codeforces.com/contest/1296
ABCDの4完!4ペナ出してるのが痛すぎるけど、順位表を見る限り他の人も結構ペナを出していた……。

A. Array with Odd Sum

数列から適当にi番目とj番目の数字を選んでA_jA_iに置き換える、という操作を好きな回数できる。適切に操作することで数列の和を奇数にすることが可能か?という問題。
なんか問題文難しくない?操作についてと何を求めるのかを誤読して1ペナ。奇数の個数が奇数か、奇数が1個以上かつ偶数が1個以上ある場合YES、そうでなければNO。

B. Food Buying

x円分の物を購入すると⌊\frac{x}{10}⌋円のキャッシュバックがもらえる。適切に物を買ったとき、払える金額の合計の最大値はいくらか、という問題。
x⌊\frac{x}{10}⌋+x%10に置き換えてシミュレートしていく。このとき⌊\frac{x}{10}⌋だけ別に足し合わせておいて、あとから元のxの値と足せば答えが出る。

C. Yet Another Walking Robot

最初(0, 0)にロボットがいて、L,R,U,Dからなる文字列で上下左右の動きを命令されている。この文字列の部分文字列のうち、切り取っても切り取り前とロボットの座標が変わらない部分のうち最も短いものを切り取るという問題。
zero sum rangesと同じ考え方で、既に出てきた座標に移動した場合、それは切り取っても問題ない動きということになる。一番短いやつを切り取らなきゃいけないので、mapで座標(a, b)が出てきたときの文字列の最新の位置を保持していく。

D. Fight with Monsters

自分が攻撃→ライバルが攻撃を繰り返して、1匹ずつモンスターを倒していく。自分の攻撃力・ライバルの攻撃力・ライバルの攻撃の順番を飛ばすことができる魔法の回数・モンスターたちの体力が与えられるので、自分の手番で最大何匹のモンスターが倒せるかを求める。
まず与えられるモンスターの体力は全部(A+B)で余りを取る。もし余りが0の場合はH_i=A+Bとして、ソートする。自分の手番で一撃で倒せる範囲の体力(1~A)は0回の魔法で倒せる。残り体力がA以上のモンスターについては、体力が少ない順に何回魔法を使えば倒せるかを求める。
体力Hのモンスターを倒すには切り上げの関係で\frac{H+A-1}{A}回攻撃する必要がある。順番として、魔法0回でAダメージ与えることができて、以降は魔法1回ごとに追加でAダメージを与えられるから、魔法を使う回数を求めるときは分子からAを引く。

E1以降は余裕ができたらでいいやの気持ち(そんな日は来ない)
おやすみ~~~~

KIEEEEE

f:id:nokiyade:20201222230036p:plain
AtCoderで水色になりたいと思っていたスギノキです。どうしてこんなこと(highest-147)になってしまったのでしょうか。

だらだらと解説を見ながら問題を解いていた

これはAtCoderの過去問を埋めている時の私にありがちなのですが、大体初見で実装の方針が思い浮かぶ問題は解けて、そうでない問題は何時間かけても解けないことしかありません。実装中の些細な添え字ミス防止としては役に立っているものの、問題を解いていてもそこから自分がきちんと考え方を吸収できているかというと微妙で、理屈を理解したつもりになっていても後から全然わかってなかったのかも……と再確認することが多いです。

灰・茶diffを落とす

直近3回のABCで私は灰diff1問と茶diff2問を通すことができませんでした。Super Ryumaが解けないのは広い心で見てギリギリセーフとしても、ソートして累積和取る問題やらオーバーフローやらに気づけないのは普段何も考えずにノロノロと競プロをやったりやらなかったりしているからで、もう灰色からやり直した方がいいんだろうな……一生緑に上がれなさそうだけど……と考えたりします。

同レートの成長速度についていけてない

2回前のFとかセグ木でxorとるだけ!wって言っても緑がこんなにセグ木を履修しているとは思いませんでした。同レートの人のコードを見ると全然私の知らない書き方をしていたりして知識の差を感じることがとても多いです。私は元々数学的思考とかそういう面で競プロerどころか現代日本の平均以下で、グラフ問題はまだしも数え上げや確率の問題で圧倒的敗北を感じます。とくに、(全部まとめての数)-(重複分やいらない分を引く)みたいな問題で全く立式できなかったりするのですが、これは問題をこなしている数が少ないからなのか高校数学をちゃんとやったほうがいいのかもう何もわからないぜとなっています。

真面目に反省したけどシンプルにサボってた

「食物語」というソシャゲがあります。中国初の女性向け中華料理イケメン擬人化ゲームであるしょくもは、怪しすぎる日本語翻訳・豪華すぎる声優という二つのトンチキさがとても面白く、競技プログラミングをおろそかにしてしまいました。以前も「幻奏喫茶アンシャンテ」という乙女ゲームをフルコンしたいがために他のすべてが手につかなくなりStreakを切ってしまったことがあります。ただでさえ競技プログラミングが弱いのにそれにもましてイケメンに弱すぎるというのが敗因の一つだと思います。

今後の展望

  • Div.3を全てバチャする(残り22個)

Div.3バチャの成績は比較的よく、Codeforces Anytimeで見ているとそこそこ安定して水以上パフォを取れていてメンタルにいいので埋めたいです。

  • ABCの茶・緑diffを中心に再度自力ACしなおす

あんまりやりたくないけどやらないと一生茶diffを落とし続けていくと思うのでやります。

  • 数え上げ・DPを中心に問題を解いていく

あんまりやりたくないけどやらないと一生水パフォが取れないと思うのでやります。

  • イケメンで競プロが強くて性格が穏やかで私のことを大好きな彼氏ほし~~~~~~~~~~~~~~~~~~~~~~~~(心の叫び)

Codeforces Round #692 (Div. 2, based on Technocup 2021 Elimination Round 3) 出たよ

2完、レートは-50くらい

A. In-game Chat

後ろの括弧の数が前の文字列より少なければNoだったのに、誤読してて==で書いてしまった
落ち着いて問題文を読む

B. Fair Numbers

30分くらい悩んで、まったくいい解法が思い浮かばなかったので未証明愚直を投げたら通った
→2,3,4,5,6,7,8,9の最小公倍数が2520なので、N~N+2520までを見れば必ず桁に出現するすべての数で割り切れる数が出てくるため余裕で間に合うらしい
何か前にも鳩ノ巣原理の問題でつまづいた覚えがあるので身に着けたい

C. Peaceful Rooks

むずかしい フレンド誰も解けてない
明日起きてから考える

おやすみ~~~~~~~!

Codeforces Round #690 (Div. 3) detayo~~

システスまだだけど多分ABCDの4完

A. Favorite Sequence

dequeを使って左右から取り出していく

B. Last Year's Substring

"2020"を分割する組み合わせは、
"2020"+""・"202"+"0"・"20"+"20"・"202"+"0"・""+"2020"だけなので、その通りに場合分け

C. Unique Number

bit全探索で、i番目のbitが立っている時iを足す……ってやって、合計値がxになるもののうち、桁数(bitが立っている数)が最小のものを出力

D. Add to Neighbour and Remove

最大でもN-1回の操作でできる。
累積和を取って、累積和に出てくる数字それぞれについて、数列を全部その数字にすることが可能か見る。最初に10^8全部見てて1ペナ……。

E1. Close Tuples (easy version)

じゅぴろさんに教えてもらった。
最小の数を1つ決めると、1種類の数字から3つ取る場合・2種類の数字から3つ取る場合・3種類の数字から3つ取る場合が考えられる(元々数列のどの位置にあったかは関係ない)。最小の数を1~N-2まで見て、すべての場合を足し合わせていく。

E2は起きてから考えます。オヤスミ……。

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の後に出たけどあんまり疲労感がなかった。昼寝のおかげかも?