なんかアレのアレをアレするとこ

プログラミングに関することが書けたらいいのになぁ

1年生でも(多分)解ける!ABCのD問題(ABC231編)

はじめに

おはこんばんにちは 紙幣と申します。

 

この記事は Kogakuin Univ Advent Calendar 2021 24日目の記事です。

adventar.org

競プロ要素が皆無だったので最終日目前にしてテコ入れのために記事を書いてます。他にもやること沢山あるんだけど。助けてくれ。

 

さて、実は去年のKogCoderではLT会と称して各々発表会するみたいなことをやってたんですが、そん中で私は1年生向けにABCのD問を(工学院大学情報学部の)1年生が知ってる知識だけで解説する、ということをやってました。具体的にはプログラミングの授業で扱われるC言語、その中でも序盤に習う入出力、配列、if文、for文、while文、あたりがわかってれば工夫次第で解けちゃうようなD問題をなるたけわかりやすく解説しようって感じのやつです。で、記事のネタも無いし今回はそれを記事って形にして外部公開でやっちゃおうって感じです。これを読んでる競プロを始めるのが怖い*11年生もこの機会にぜひ挑戦してみてね。

なお、上記の通りガチ初心者向けという前提で書いていくため競プロ慣れてる人だと解説が冗長に感じられるかと思います。ご了承ください。

 

そもそもAtCoderとかABCってなあに

ここでAtCoder自体の解説入れて1年生に優しい素振り見せようかと思ったけど書くのダルくて萎えた、一昨年のyudegakiさんのこちらの記事をご覧ください。

yudegaki.hatenablog.com

わかりやすい記事だなあ!

でABCってなあにって言いますと、AtCoder Beginner Contestの略でして、AtCoderのサイトで行われてる初心者向け競プロコンテストのことです。最初は2問解けたらいいな~くらいの気持ちで挑んでみてね。

 

D問題ってなあに

最近のABCでは毎回A~Hの8問用意されてます。D問はその4問目ってことですね。基本的にAが一番簡単で後ろにいくほど段々難しくなっていきます。8問中4問目なのでそれなりに歯ごたえがある難易度です。

ちなみに、これは去年やってた企画(?)が元になってるという話は先程しましたが、当時はA~Fの6問構成でした。当時のD問は現在のE問に該当するそうです。現在のD問は当時のD問よりちょい簡単めくらいだとか。それにあたって今回の記事もD問じゃなくE問に変えるべきか悩みましたが、当時の企画では基本的にD問の中でも簡単めの問題を扱ってたので、それならDのままでも変わらんかってことでD問でいかせていただきます。あとむずい問題扱うと解説長くなって書くのダルいし

 

D - Neighbors

さて、ようやっと本題です。問題を解いていきましょう。今回扱う問題はパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)より、D - Neighborsです。

atcoder.jp

ちなみに、当然ながら以下はこの問題の解説なのでネタバレ無しで自力で挑んでみたい方は挑戦してから以下の文を読むようにしてくださいね。

 

さて、問題文や制約はこの通りです。

問題文

 から N の番号がついた N 人を横一列に並べる方法のうち、以下の形式の M 個の条件全てを満たすものが存在するか判定してください。

  • 条件:人 A_iと人 B_iは隣り合っている

制約

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1\leq A_i < B_i \leq N
  • (A_i,B_i) は相異なる

出典: D - Neighbors

これだけだとわかりづらいですね。そういうときは入出力例を見てみましょう(引用するのダルくなってきたので自分でページ開いて見てみてください)。入出力例を見るとなんとなくわかったと思います。例1は言われた組み合わせを全て満たした上で横一列に並べられるのでYes、例2では人4が3人と隣り合うことになっていますが横1列に並ぶときには2人までしか隣り合えないのでNo、ということですね。

……ってことは同じ人が3回以上出てきたらNoにすればいいだけじゃん!簡単!!

…………ということではありません。例えば以下のようなケースもNoです。

4 3

 

1 2

2 3

1 3

同じ人が2回までしか出てきていませんが、1の隣に2、2の隣に3、3の隣に1、とループ状になってしまっています。これでは1列に並ばせることはできませんね(競プロあるある、テストケースに出てこない箇所のトラップに引っかかる)。

けど他にNoのケースは考えられませんね。つまり

  • 3人以上の相手と隣り合う人がいる
  • ループ状に並ぶ必要がある人達がいる

この2つのどちらかに当てはまればNo、どちらにも当てはまらなければYesです。ではどうすればこれを見分けられますか?というところが本題になってくるわけです。

 

さて、ここで見方をちょっとだけ変えてみましょう。ここまで問題文通りに「人を並べる」ことを考えてきましたが、人を点に置き換えてみます。すると以下のような図がイメージできます。

f:id:shihei_k:20211218154150j:plain

点1,2,3,4

次に隣り合うという条件を点を線でつなぐことに置き換えてみましょう。すると例1,2及び先程挙げたループ状になってしまうケースはそれぞれこのように図示できます。

f:id:shihei_k:20211218154249j:plain

入出力例1

f:id:shihei_k:20211218154513j:plain

入出力例2

f:id:shihei_k:20211218154533j:plain

ループ状になっちゃうケース


つまり「条件で提示された線を全て用いた上で全部の点を一筆書きで1回ずつ通ることはできるか」という問題にできます。並び替えという面倒な操作を無視できますね。こうして見ると数学的に解けそうな気になってきますね。Noの場合の条件はそれぞれ以下のように書き直せます。

  • 3つ以上の点と結ばれた点がある
  • 複数の線が組み合わさってループ状になっている

では改めてこれをプログラムで実現するにはどうすべきでしょうか。

 

まず、与えられた情報をどのような形で変数に保管するかについても色々なケースが考えられます。条件をそのまま記録する、つまり先程の図形における「線」の情報を保持しておくことも考えられますが、これだと例えば3つ以上の点と結ばれた点がないか確認する場合に全ての線を調査して調査したい点が出てきた回数を調べる必要があります。これでは点が増えたとき面倒そうですね。

ということでそれぞれの点に繋がってる点の情報を記録するのがよさそう……?

f:id:shihei_k:20211218154643j:plain

これでもできなくはありません。しかしこれでも面倒なことが1つあります。それはループの検証です。例えば以上の図からループが無いか確認するためには点2から点1へ辿り、点1から点4へ辿り、……と繰り返さねばなりません。この図では複数の点に渡る長い線が1本しかないのでいいですが点や線の数が増えると検証がどんどんめんどくさいことになっていきます(とはいえ頑張って実装すればいけなくはないけどね、今回の問題だとNの値も小さめだし*2 )。

と、ここであることに気が付きませんか。それぞれの点の「状態」という観点で見てみましょう。以下のA,B,Cの3種類に分類できませんか。

 

A.線の途中になっている点(=2つの点と結ばれている点)

f:id:shihei_k:20211218154710j:plain

これらの点はもうこれ以上他の点と繋げません。

 

B.まだどの点とも繋がっていない点

f:id:shihei_k:20211218154723j:plain

これらの点はA以外の相手であればどの点とでも繋がれます。

C.線の端っこになっている点(=1つの点と結ばれている点)

f:id:shihei_k:20211218154738j:plain

これらの点は当然Aの点と繋がれない他、その線の反対側に位置する点とも繋げてはいけません(例えば2は5と繋がるとループ状になってしまいNG)。

 

……おわかりいただけたでしょうか。「どの点と繋がっているか」の情報が必要なのはCだけです。それも途中に通った点は関係なく、もう一端の相手がわかればよいのです。その他の点に関しては自分がAかBかがわかれば十分です。つまり、必要な情報に絞ると以下のように示せます。

f:id:shihei_k:20211218154803j:plain

自分の点の分類を記録した上でCのときはペアとなる相手の情報を記録するだけです。これであれば以下のように最初全ての点をBとしてそこから線を1本ずつ増やして更新していくだけで検証できます*3

f:id:shihei_k:20211218154842j:plain

f:id:shihei_k:20211218154856j:plain

f:id:shihei_k:20211218154921j:plain

判別方法もわかって終わりが見えてきましたね。ではこの点を繋ぐ更新の処理について考えてみましょう。例えば以下の図について、5と8を新たに結ぶ場合を考えるとこうなります。

f:id:shihei_k:20211218154953j:plain

f:id:shihei_k:20211218155003j:plain

まず5と8は当然Aになりますね。問題は2と6です。直接結んだわけではないのにデータが書き換わっています。ここをどう実装すれば……。

……とまあ大半の方は察しているかと思いますが、この2と6、それぞれ元々5と8の相手として情報が記録されていました。それを使えば簡単に実装できそうですね。しかも書き換えた後の値も6と2、つまり元々8と5に記録されていた値を書き込むだけなので尚のこと簡単に実装できそうです。

 

次に先程の図から更に6と7を結ぶケースを考えてみると以下のようになります。

f:id:shihei_k:20211218155018j:plain

6がAになるのは先程と同様です。問題は7です。7は状態BだったのがCになりました。これをどうやって実装しましょうか。

ここで2を見てみましょう。2の相手は7になっています。状態Bの点と繋いだときはその点自体の値に書き換えなければならないようです。条件分岐がめんどくさそう……と思った方もいるかもしれません。しかしこれが実は実装を楽にするチャンスでもあります。先ほどと同じ実装でこの処理を実現したいなと考えたとき、点7に「相手は7」という情報が入っていたら都合よく実装できそうですね。

……あれ?別にそうしても問題なくね?

でもってそう考えたらBとCの区別要らなくない?

そう、状態Cのときに相手が自分自身になることはありません。つまり状態Bのときは自分自身の値を入れておくだけでBとCの見分けがつけられる上に同一の処理で実装ができるようになります。そうすると今まで状態A,B,Cと分けてきましたがAとそれ以外の2つに分けるだけで十分になります。更に言えばAのときは存在しない点の値、例えば-1等の値を入れておけば「繋がっている相手」の情報だけでA,B,Cの状態が管理できます。つまり以下の図のようになります。

f:id:shihei_k:20211218155054j:plain

ここまで来れれば後は本当に実装するだけです。実装するとこのようになります*4

https://atcoder.jp/contests/abc231/submissions/27963119

なおこの提出はC++で行われていますが最初のinclude周りと入出力以外はCとほとんど同じなので読めるかと思います。入出力に関してはcinをscanf、coutをprintfに置き換えて読んでみてください。

 

おわり

というわけでド初心者向けの解説をやってきました。このブログ内でちゃんとしたプログラミングの話するの初めてでは……?

競プロは色んな知識を要求されそうで難しそう……って敬遠していた人もいるかもしれませんが、初歩的な知識しかなくても発想次第で解ける問題もあるんだよってことがわかってもらえたかなと思います(もちろん知識が必要な場面もあるけど)。これをきっかけに競プロの面白さをわかってもらえたら幸いです。それでは。

*1:ばっかお前……俺がついてるだろ(音ゲーマーにしか伝わらないネタ)

*2:プログラミングの世界では10^5なんて小さい方です

*3:このようにデータを順に更新していく手法を動的計画法(DP)と呼びます。競プロではかなり重要な考え方です。DPについて詳しく知りたい人はこちらの記事がわかりやすくてオススメです→動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita

*4:この提出プログラムはめちゃくちゃコメント書いてますが解説用に書き込んだだけなので普段はこんなにコメント書いてません。悪しからず。

言葉遊びには気を付けようの巻

おはこんばんちは 紙幣と申します。

 

この記事は Kogakuin Univ Advent Calendar 2021 6日目の記事です。

adventar.org

 

皆さんいかがお過ごしでしょうか。僕は色々だめです。タスク爆発してるせいもあって精神状態がかなり終わり散らかしています。年の頭には 自主的にプログラムとか書きたいな~ とか考えてた気もするけどプログラムの製作してないどころかAtCoderとかも全然参加してません。誰か助けてくれ。

 

本題

皆さんは言葉遊びをご存知でしょうか。言葉で遊ぶアレです。大昔からやられてたりやられてなかったりするやつですね。そん中でも俳句やら川柳やらというものは存じ上げていらっしゃいますでしょうか。まあ存じ上げているとは思うんですが575のやつです。最近わたくしはあれに身を滅ぼされかけています(正確には俳句どころか川柳と言ってもいいのか怪しいものだけど)。

具体的にどういうことやねんっちゅうと言葉を聞いたり発したりするたびに575かどうかを検証することに脳のリソースが割かれます。例えば記事冒頭に書いた文章を見てみましょう。

 

年の頭には 自主的にプログラムとか書きたいな~ とか考えてた気もするけどプログラムの製作してないどころかAtCoderとかも全然参加してません。誰か助けてくれ。

 

自主的に プログラムとか 書きたいな !?!?!?!?!?!??!?!?!?!?!?!?!?!?!?!??

 

はい。そういうことです。こんなしょーもないことに思考が持ってかれます。これの厄介なところは実際に575じゃなくてもそれっぽいものを見かけると575かの検証を始めてしまうところです。具体的には57、なんなら5を見かけただけで身構えてしまいます。ここで再び冒頭の文章から適当に引用してみましょう。

 

皆さんは言葉遊びをご存知でしょうか。言葉で遊ぶアレです。

 

皆さんは ←おっ!?!?

言葉遊びをこれは!?!?!?!?

ご存知でしょうか  違ったぁぁあああああ

 

色んな文字列を見るたびに思考回路がこんなんなってます。誰か助けてくれ。

 

こんな調子で発見してしまった575一覧(一部抜粋)

よく見たら なんかちっちゃく 書いてある

とりあえず こんな感じで どうですか

すみません 大変遅く なりました

久々に ガッツリ肉が 食いたいな

情報を ちょっとぼかして 載せました

ラズパイで 遊んでいたら 単位来た

要求が タイムアウトに なりました

DLと 利用規約は こちらから

筋肉を 動かしたくて 仕方ない*1

一度見た 相手の顔は 忘れない*2

野郎ども 準備はいいか 出航だ*3

ムックルに ニックネームを つけますか?*4

 

これ自分ひとりが発症してるならまだしも周囲の人間もこの症状を発症してるんですよね(というより自分も周囲の人から感染したんですが)。その結果何が起こるかというと会話に参加している誰かがポロッと575を発言しようものなら周囲の人に指摘されます。指摘が入ると当然会話の流れがストップするため指摘されないように自分が今からしようとする発言に575が含まれていないか確認してから発言をする羽目になります。社会性が欠片も存在しない世界がここにあります。地獄。助けてくれ。

 

発展

これだけでもかなりよろしくないのですが、最近この異常者集団の中で更に厄介な文化が形成されてしまいました。それは、

誰かが57を発したら「最上川」と付け足して強引に575にする

これです。いよいよ何言っとるんやって感じですね。具体的な例を挙げましょう。

 

A「ラーメンか寿司が食いてぇ」

B「最上川

 

(Bが課題をやっている場面に出くわして)

A「締め切りは?」

B「昨日ですけど?」

C「最上川

 

こういうことです。コミュニケーションのおしまいみたいな会話ですね。こんな環境にいるとほんまに精神ぶっ壊れます。助けてくれ。

 

こんな調子で生まれてしまった最上川一覧(一部抜粋)

本当に めんどくせぇな 最上川

茨城は なんにもないよ 最上川

扇風機 買い替えなきゃな 最上川

誤字脱字 多すぎるだろ 最上川

ご自由に お持ちください 最上川

すみません 寝過ごしました 最上川

緊張で 手が震えてる 最上川

Python脳死で書ける 最上川

シロナさん マジで強すぎ 最上川

ウマ娘 プリティーダービー 最上川

コイキング さかなポケモン*5 最上川

ベネフィック コンジャンクション*6 最上川

 

言葉狩りもいいとこですね。人間として真っ当な会話ができなくなります。

 

対策

一番の対策は意識しないことです。しかし一度知ってしまった以上意識しないことは不可能です。つまりこれを読んでしまったあなたもいずれ異常者の仲間入りを果たすこととなるでしょう。残念でした。

 

おわり

以上です。いかがでしたか?この世にはこんな奴らもいるんだなってことを知ってもらえたのならば幸いです。助けてくれ。それではさようなら。

 

 

 

 

 

 

 

 

 

 

この世には こんな奴らも いるんだな !?!?!?!?!?!??!?!?!?!?!?!?!?

 

 

 

 

 

 

 

 

 

 

 

 

 

以上です いかがでしたか 最上川 !?!?!?!?!???!?!?!?!?!?!!!?!?!?!?!??!?!?!?!?!?!?!??!?!?!?!?!?!!?!?!?!?!?!?!?!?!??!?!?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

こんなしょーもない文化はよ滅んでくれ。さようなら。

*1:ゲーム「ウマ娘プリティーダービー」のメジロライアンのセリフより引用

*2:ゲーム「ウマ娘プリティーダービー」のシンボリルドルフのウワサ①より引用

*3:漫画 ワンピースのCMより引用

*4:ゲーム ポケットモンスターシリーズより引用

*5:ゲーム ポケットモンスターシリーズの図鑑説明より引用

*6:ゲーム「ぷよぷよテトリス」のフェーリの連鎖ボイスより引用

Flashがお亡くなりになるので最高のFlashゲームの話がしたい【丸投げクエスト】

おはこんばんちは(死語) 紙幣と申します。

 

この記事はKogakuin Univ Advent Calendar 2020 3日目の記事です。

adventar.org

 

ついにFlashのサポートが終了するまで1ヶ月を切りましたね。わたくし小中学生時代をFlashゲームと共に過ごしてきたものでして、数々の思い出のゲームが年が変わると同時に遊べなくなるのかと思うと涙が止まりません。泣きアニメの最終回観たときくらい泣いています。まあ僕泣きアニメどころかアニメ自体あんまり観ないんですけど。

さて、そんなこんなで私の青春そのものと言っても過言ではないゲームたちがもうすぐ封印されてしまうので、私の青春の記憶、ひいては私がここまでの人生を歩んできた証、別の観点で言えばそのゲームが人生の柱となってる人間がここにいるという存在証明をここに記そうというわけです。めちゃくちゃ壮大に書いてるけどまあそんくらいFlashサポート終了の筆者へのダメージが大きいということで。てなわけで思い出語りやっていきます。

 

丸投げクエス

はい、これです。丸投げクエストです。これほんとに大好きなんですよ。

正確に言えばHARUKOさん作のゲームはどれもめっちゃ好きなんですがこれはずば抜けて好きでした。ほんとに色々やってた人ですよアピールしておくと、「しりとりクエスト外伝3・勇者困った!」や「魔女っこと封印の石板」、「しりとりクエスト外伝5・電話でポン!」とか「丸投げクエスト外伝3・ジャック・ザ・アンロッカー」あたりはめっちゃ好きでしたね。あと「しりとりクエスト4」や「しりとりクイズ 44 Doors」とかとてつもなく苦労した記憶があります、ってか後者に至っては確か完クリできてません……。あと「おおまちがいさがし」でただのボケだと思ってた箇所が「しりとりクエスト外伝4・もりもり鉱山の一番長い日」で理由が明かされたときには感動しましたね。こんな語り口調だと逆ににわか臭さあるな、まあいいや。

 

話がめちゃくちゃ逸れました。丸投げクエストの話をしましょう。まずは色々リンクをぺたり。

http://www002.upp.so-net.ne.jp/h_numata/flash/pquest/pq3.html

2020年現在はここで公開されています。マジで面白いので2020年に読んでる人は今すぐこのリンクをクリックしてプレイしてください

丸投げクエスト・本日公開です | 真・うかつ絵日記

元々公開されていたページです。今もうゲーム本体の方は消えてますが。

丸投げクエストはこんなゲームだったよ | 真・うかつ絵日記

作者さんによる動画付き振り返り記事です。2021年以降の人類はこのページを見てこんな神ゲーがこの世に存在していたんだなぁと感慨に耽ってください。

 

というわけでね、めちゃくちゃ面白いんですよこのゲーム。遊べる人は遊んでもらった方が早いんですが遊べなくなった2021年以降の人類の皆さんのためにお話していきます。ほんとはスクショつけて解説しようかなと思ってたんですが権利的に大丈夫なのかとか遊ぶ人のネタバレになるのではとか色々考えた結果やめとくことにしました。

まずこれどういうゲームなのさって人に説明……したいんですがこればっかりは作者さんの言葉をお借りした方が早いですね。RPGからパーティー編成以外の要素をバッサリ取り払ったゲーム」です(丸投げクエスト・本日公開です | 真・うかつ絵日記より引用)。それ面白いのかよ!って思う方もおるかもしれんがまあ聞いてくれ。このゲームの目的は魔王の討伐。んでもってその手順は

 

30人のメンバー候補から5人を選出して

2種類ある魔王城までの道筋をどちらか選んで

持たせるアイテムを1つ選んで

 

おわり。

 

すぐさま報告書で結果が来るので読みましょう。

は?そんだけ?と思われるかもしれませんがこれがめちゃくちゃ奥深いんですよ。

 

例えば多彩なスキルを持つ子供ハンターと能力値高めの傭兵さんをパーティーに突っ込んだら傭兵さんが子供嫌いだったために顔合わせの段階で戦場に子供を連れてくんなとブチギレて帰ってしまいバッドエンド(ゲームオーバー)、如何にも強そうな戦士の兄ちゃんを連れて出発したらあろうことか方向音痴だったために道中の森で迷子になってしまいバッドエンド、などなど思いもよらぬ理由でバッドエンドになります。もちろんそういう各個人の性質によるものだけでなくRPGらしくメンバーの合計能力値が足りずバッドエンドになることもあります。また、これらのバッドエンドは他メンバーのスキルや持たせるアイテム等によって回避できることもあります。

 

なんとなくわかってきたかもしれませんがこのゲームの本質はRPGというよりパズルに近いです。ゲームをやり込むうちにだんだんいけそうな組み合わせが見えてくるんです。何度も挑戦してやっと見えてきた組み合わせでクリアしたときの気持ちよさったらないですよ。ほんまに。

 

更にこのゲーム、やり込み要素も豊富にあります。1回クリアした!終わり!じゃないんですよ。

まず各キャラクターに関して、クリア時のパーティーメンバーのアイコンに星マークが付きます。この星マークを全キャラにつける、すなわち全キャラ使用してクリアというやり込みの壁が立ちはだかります。扱いづらいからと避けてきたキャラクター達をどうすればクリアまで持っていけるかを考えるのはまた楽しいもんですよ。

更にバッドエンドもそれぞれパターン分けされており、35パターンのバッドエンドを全て回収するというやり込み要素もあります。中には狙って組まないと達成しづらいバッドエンドもあり、ものによってはクリアを狙うとき以上にパーティーメンバーの組み合わせを考える必要が出てきます。

あとこれは何か印がつくわけでもない極めて個人的なチャレンジなんですが、とあるキャラクターが持つ「スルー力」というスキル、活用する場面が極めて限られている上に発動させるための制約がかなり厳しいので、スルー力を活用した上でクリアする、というのを狙ってみるのも面白いですよ。バッドエンド回収まで終わった人は是非挑戦してみてください。

 

まあそんなこんなでやり込むうちにどんどんわかってきてどんどん楽しくなっていきます。このパーティーでクリアできるか、クリアできないならどのバッドエンドになるか、どうやって調整すればクリアできるか、狙ったバッドエンドが見れるか等が手に取るようにわかるようになってきてその度にこのゲームにのめり込んでいきます。そのうち気づけばこのゲームの虜になっています。2020年内に上記のリンクを踏んでプレイした貴方も今頃このゲームの魅力にどっぷり浸かってしまい間近に迫るFlashサポート終了が恨めしくなっているでしょう。なんて罪なゲームだこと……。

 

あ、ところでこれご存じですか。

midorism64.hatenablog.com

なんと有難いことにFlashを自動でWebAssemblyに変換してくれるツールの開発がなされているそうです。すごいね。丸投げクエストをはじめとする数々のFlashゲームに慣れ親しんできた僕はもちろん、2020年以内に丸投げクエストをプレイしてしまい年明けと同時に訪れる丸投げクエストロスに怯えている貴方も、2021年以降にこの記事を読んで丸投げクエストという神ゲーが遊べないことに涙している貴方も、近い未来に希望の光はあるわけです。感謝感激雨嵐だね。

 

ここまで雑~に喋くり散らかしただけですが長くなってきたしそろそろ〆ようかな。というわけで皆さんさようなら。

 

 

 

 

 

 

ごめんなさい、1つだけ言いたかったこと言い忘れてたので言わせていただきます。あと記事全体通してスクショ使わない方針だったけど最後に1枚だけ貼らせてください、HARUKOさんごめんなさい。

 

 

 

 

 

 

 

 

 

 

 

f:id:shihei_k:20201119143416p:plain

幻術師のリカちゃんかわいいね。

それでは。

SOUND VOLTEXの楽しい譜面4選

目次

 

はじめに

この記事はKogakuin Univ Advent Calendar 2019 20日目の記事です。

f:id:shihei_k:20191220191258p:plain

adventar.org

さて、はじめましての方ははじめまして。そうじゃない方は2度目まして。紙幣と申します。前回より自己紹介無い分前置き短くなっちゃったな、字数稼ぎにもっかい自己紹介していい?いいよありがとう。

今年度よりKogCoderに所属しました。特になんもできません。AtCoderも灰色コーダーです。何書きゃええねん。前回で唯一書けそうな記事のネタ使っちゃったし。でもなんかプログラミングに関する記事書きたいよね、例えば前回記事でも扱ったAtCoderとか......。決めました。

SOUND VOLTEXに関する記事を書きます(*╹◡╹*)

SOUND VOLTEXってなあに

KONAMI社が出しているアーケードの音楽ゲームです。

p.eagate.573.jp

SOUND VOLTEX(以下SDVXと表記)の特徴はなんといってもアナログデバイス(以下ツマミ)をエフェクトライン(以下レーザー)に沿って回すという独特の操作とFXを押したりツマミを回したりする度にエフェクトがかかるという点、そしてなにより疾走感200%な点ですね。楽しいのでやったことない方は是非ゲームセンターに行ってやってみましょう。

というわけで雑に解説済ませたしどうせ譜面語りしてもある程度やってる人じゃないと何も伝わらなさそうだしさっさと本題いっちゃいましょう。なお今回の記事にはSDVX譜面保管所様のスクショを用いています。

BELOBOG[MXM]

はい、しょっぱなレベル19です。ごめんなさい。でも楽しいんですよこれが。むずいけど。ちなみにエフェクターはEther99です。さて早速語っていきますが好きなとこめちゃくちゃあるんですけど全部書いてたらキリがないので何ヶ所か厳選して書きます。

f:id:shihei_k:20191224205906j:plain

デレレデレレデレデレレデレレデレ

これが開始1秒足らずで降ってきます。何?でもこの配置めちゃくちゃ曲に合ってるんですよね。新規性と楽しさを兼ね備えた素晴らしい配置だと思います。ちなみにですがここのフレーズはイントロとアウトロで繰り返されてるので当然この配置も繰り返し出てきます。許して

f:id:shihei_k:20191224210806j:plain

ココキコキココキ

ここすき。見たまんま回せば普通に繋がるから難易度的には大したことないけど捌いてて気持ちいい。

f:id:shihei_k:20191224211048j:plain

きれい

ここの流れるような鍵盤すき。気持ちよく叩ける。ちなみに光らない。かなしいね

f:id:shihei_k:20191224210936j:plain

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk

出たよ……

この譜面はここ抜きにしちゃ語れんわな。初見爆笑したけど僕は好きです。楽しいし。

んでまあこっからしばらくわちゃわちゃ続いてから静かなブレイク入ってサビなんですけども、

f:id:shihei_k:20191224211208j:plain

きれいパート2

ここの流れるように捌ける鍵盤楽しい(2回目)。ちなみに光りませn(ry

からの

f:id:shihei_k:20191225211308j:plain

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk

エ ー テ ル は 2 度 刺 す

また出たよ……でもまあ散々騒ぎ立てといてなんですけどここもさっきのとこもそんなむずくないんですよね、左右交互に叩いてりゃ繋がるし()

 

てなわけでめちゃくちゃ雑にBELOBOGの好きなとこ紹介でした。

ちなみにこの曲BeatStreamという機種のCHERNOBOGというボス曲の続編曲かと思われます。なんで消えてしまったん…?

ちなちなみにCHERNOBOGもSDVXに移植されてはいますがそっちはオススメしないでおきます(準無理押しめちゃくちゃあるし……)。

ちなちなちなみにBELOBOGとCHERNOBOGのジャケットに描かれているキャラクターはどちらも先程述べたBeatStreamのキャラクターで、BELOBOGの方は「にゃん」、CHERNOBOGの方は「タカハシサン」といいます。

 

 

……ん?タカハシサン?…………タカハシ……………高橋……………………………

 

 

atcoder.jp

タカハシサンと言えばAtCoderには高橋くんが頻出することで有名ですね。とんでもない行動をしたりとんでもない物忘れをしたりすることで知られていますが先程のリンク先の問題のように散々な目に遭っているときもありますね。折角だしこちらの問題を解いてみましょうか。

とは言ってもこの問題、ヒントを見れば何の苦も無く解けてしまうんですよね……。強いて気をつけることと言えば絶対値を取り忘れないようにすることくらいでしょうか。

というわけで解けました。はい。次の譜面行ってみましょうか。


†渚の小悪魔ラヴリィ~レイディオ†[MXM]

はい。18です。jubeatからの移植楽曲ですね。エフェクターは〜PH〜さん。楽しい。てなわけで早速楽しい箇所抜粋ドン。

f:id:shihei_k:20191225214410j:plain

ラヴリィ~レイディオ!

はい見ての通りハート型ツマミですね。ツマミは2本しか出せないし上部外側が欠けてるのは許したげて。

f:id:shihei_k:20191226121456j:plain

うっふ~ん♥

ここね、一見ただのツマミ出張なんですけど実際に手を動かしてみるとわかるんですが歌詞に合わせて腕をクロスさせてセクシーポーズをさせられるという仕組みになっているんですよね。巧すぎる。譜面の表現を譜面の外まで広げてくる。常識に囚われていては新しい表現なぞ生まれないということを思い知らされます。

んでこっからBメロ入ってサビなんですけどこのへんぶっ飛ばします。ごめんなさい!でも他に語りたいことがあるってだけでそこがつまらないって訳じゃないから是非やってみてね。

てなわけでCメロなんですけども

f:id:shihei_k:20191226125725j:plain

Primちゃん!あしたっtいまいまいまs

?????

f:id:shihei_k:20191226125728j:plain

ではご機嫌なナンバ バ バ 続けてSTAY TUNED!!

 ?????????

横で走ってる放置レーザーにリピートエフェクト乗っけまくって曲がメチャメチャにされてます。こればっかりは画像じゃ伝わらんので自分でプレイするか動画調べて観るなりしてください。

んでまあSDVXの醍醐味といえば最初にも述べたようにエフェクトをかけることなんですよ。SDVXだからこそ楽しめる譜面と言えますね。

余談ですが僕はこの譜面登場した当初ここがめちゃくちゃ苦手でここだけでハード落ち*1したりもしてました。

f:id:shihei_k:20191226125732j:plain

休憩地帯かと思いきや......?

一見何の変哲もない地帯……と思いきや直角をよく見てください。赤なんですよこれ。つまり左手で出張して取る必要があるんですよ。初見ビックリドッキリですよ。でもね、慣れるとめちゃくちゃ楽しいんだなこれが。

f:id:shihei_k:20191226162216j:plain

Hey! Hey! Hey! Hey! Hey! Hey!

ラスサビですね。ここはね、是非動画見て欲しい。音付きFXチップがめっちゃうるさいんですよ。でもすき。テンション上がりますね。

てなわけで渚の小悪魔の紹介でした。

 

……渚?……なぎさ………なぎさちゃん…………?

 

 

atcoder.jp

渚と言えばAtCoderにはヤンデレなぎさちゃん*2回があることで有名ですね。てなわけでこのC問解いてみましょうか。

 とは言ってもこれも入出力1のとこに書いてあるのをそのまま組めば出来てしまいます。筆者の競プロ力が低いばっかりにクソ記事になりかけててごめんね。てなわけで次の譜面いってみよう

Harmonia[MXM]

割と最近の譜面ですね。ポリブレ*3の譜面なので解禁してない人はスマン。エフェクターは鋼のビスカッチャです。

f:id:shihei_k:20191226213102j:plain

世界が のとこ

はい綺麗。ここまで綺麗に逆から出したうえで楽しい配置ある???

f:id:shihei_k:20191226212937j:plain

デ デ デ デ デ デ デ デ デ デ

ここね、盛り上がりに合わせて鍵盤増えていくのエモい。程よい難易度してるのもよい。

f:id:shihei_k:20191226212941j:plain

大胆不敵な(ダイタンフテキナ

おい、おいビスカッチャ、お前な、そうやって歌モノで歌が入ってないとこにエフェクトで歌入ってるとこのフレーズを持ってくのはやめろ。あまりにも自然なうえに最高すぎて原曲が物足りなくなってしまうので。

f:id:shihei_k:20191226212947j:plain

サビ前のとこ

ここに音付きFXチップ置いてるのエモすぎ。ビスカッチャくん、新人なのに盛り上げ方
を知り尽くしてる。なんで。

f:id:shihei_k:20191226212944j:plain

鋼のビスカッチャに心からの原義感謝を伝える地帯

サビもしっかりダブルレーザーで盛り上げる。譜面の作り方を完全に"理解(わか)"っている。

f:id:shihei_k:20191226212934j:plain

新規性の塊

すごい。良すぎ。神配置しかなくてだんだん語彙力が死んできた。まずビジュアルが美しい。そんでもって初見びっくりな配置してるけど捌き方は素直だから2回目以降は難なく捌ける。しゅごい。

f:id:shihei_k:20191226212955j:plain

ラストも盛り上げていく

そんなこんなで楽しすぎる譜面で盛り上がりまくってるテンションを緩めずその勢いのまま〆る。素晴らしい。この譜面をやったら二度と鋼のビスカッチャ先生に足を向けて寝れなくなります。

というわけでHarmoniaの紹介でした。ちなみにこの曲はpop'n musicからの移植でして、

 

......ん?pop'n music……?............

 

 

atcoder.jp

そういえばARCにある音楽ゲームという問題、明らかに譜面の内容がpop'n musicですよね。せっかくですしこちらも解いてみましょうか。

とは言ってもこちらもやってることは結構簡単です。数えるだけだし。ただx(単押し)は素直に数えてあげればいいとして問題はo(長押し)の処理ですよね。長押しは上部で数える方式と下部で数える方法がありますが普通に上部で数えてあげた方が手っ取り早いです。

入力をすべて取ってから処理をする場合はoが来た場合その1つ上を調べてoでなかった場合はカウント、という手段が取れます。入力を1行ずつ取ってその度に処理をする場合はその行がoだったかどうかを記憶させておく配列か何かを用意しておけばよいですね。

てなわけで最後にもう1譜面いってみましょうか。

怪盗Fの台本~消えたダイヤの謎~[MXM]

こちらはVになったと同時に出てきた譜面ですね。ボカロ曲の歌い手カバー版となっております。エフェクターは近年話題のNOX。僕は大好きです。てなわけでささっと紹介いってみよう

f:id:shihei_k:20191227153725j:plain

Aメロの静かな箇所すらも楽しいのがNOX譜面

はい。序盤もいいとこですね。特筆すべき箇所もないなんてことない配置ですがそれでもNOX先生は楽しく仕上げる。ちなみにここでもNOX先生はいつも通りツマミと鍵盤を重ねません。流石ブレない。

f:id:shihei_k:20191227153723j:plain

キャプション書くのだんだんだるくなってきた

特に書くこともないけどやると何故か楽しい配置パート2。

f:id:shihei_k:20191227153720j:plain

はじ めよ うか (Are you Ready?)

サビ前に気持ちいい配置を持ってきてくれるのは良エフェクターの証。最後だけ出張させてくるの、「俺難しい配置捌いてる~~~~~~!!!!」的な気分にさせてくれるのですき。この調子乗った状態でサビ突入するのが楽しいんだなこれが。

f:id:shihei_k:20191227153714j:plain

豪華なFakeに包んだ(テテトン

はいNOXくん最高。音付きFXチップの使い方が上手すぎ。これ実際やってみるとわかると思うんですけどめちゃくちゃテンション上がるんですよこれ。

f:id:shihei_k:20191227153729j:plain

メチャ長い縦トリル

この譜面の印象的な配置その1。一見左手めちゃくちゃ大変な気がしますがBPMが低いのでそこまで苦でもありません(まあそれでも実際むずいけど)。僕としては楽しいし曲に合ってるので好きです。

f:id:shihei_k:20191227153737j:plain

ブレイクの片手

他の譜面でこんな配置出されたら僕はムッとしちゃうんですけどこいつは何故か楽しいんですよね。なんでだろう、NOXくんが楽しくなるように魔法かけてるのかな。

f:id:shihei_k:20191227153732j:plain

3、2、1、Action!

いや、ここまで綺麗で自然なカウントダウンツマミ見たことある???

ヤバすぎますね。エモみがエモエモしてますね。初見ではカウントダウンと気づかなくてもおかしくない自然っぷり、気づいたときの感動、何から何まで完璧。しゅごい。

f:id:shihei_k:20191227153735j:plain

うつくしい

ここすき。ノリノリで叩ける。NOX先生はプレイヤーを気持ちよくするのが上手い。

f:id:shihei_k:20191227153739j:plain

なんだこれは

この譜面の印象的な配置その2。出張させたうえで交互押しをさせる初見ビックリ配置。ただNOXくんの凄いところはその直前に予め出張させておいてあげてるんですよ。誘導が上手すぎる。NOXくん人生2周目かと思うレベルで頭が良い。

 

はいというわけで怪盗Fの紹介でしt......

 

......怪盗............回答..................?

 

 

Submission #9098316 - AtCoder Beginner Contest 002

 

Submission #9143116 - AtCoder Beginner Contest 010

 

https://atcoder.jp/contests/arc016/submissions/9147257

 

今まで出てきた問題の僕の提出した回答はこんな感じです。

では長々書いたことですしこのへんでさようなら。

*1:EXCESSIVE RATE(通称ハードゲージ)という100%の状態からスタートしミスをするとゲージが大幅減少、0%になったらその時点でTRACK CRASH(ゲームオーバー)になるゲージを選択し、TRACK CRASHしてしまうこと

*2:恐らく元ネタは渚の小悪魔......ではなくこっち

*3:POLICY BREAKの略。期間中に特定のBEMANI機種をプレイしてその機種の楽曲をSDVXで解禁するイベント。

AtCoderにおける高橋くんのお話

目次

 

はじめに

この記事はKogakuin Univ Advent Calendar 2019 13日目の記事です。

adventar.org

さて、はじめましての方ははじめまして。そうじゃない方は......おりませんわな。だって初めてはてブに記事書くしなんならアカウントも数日前に取ったばっかだし。てなわけで記事の本題に入る前に少し自己紹介をさせていただきます。

紙幣と申します。今年度よりKogCoderに所属しました。特になんもできません。AtCoderも灰色コーダーです。何書きゃええねん。てなわけで今回の記事です。よろしくお願いします。

そもそもAtCoderってなあに

まあざっくり言うと競技プログラミング略して競プロが出来るサイトの1つですね。8日目にyudegakiさんがガッツリ語ってるので詳しくはそちらの記事をご覧ください(丸投げ)。

yudegaki.hatenablog.com

AtCoderにおける高橋くんについて

さて本題ですね。先ほどのyudegakiさんの記事でも言われてるようにAtCoderには文面が面白い問題がいくらか存在します。またAtCoderの問題には高橋くんという人物がよく登場します*1。そしてこれらが合わさった結果高橋くんはAtCoderの問題文内で奇怪なことに巻き込まれたり*2理解できない行動を起こしたり*3しがちです。今回はそんな高橋くんが登場する問題の中から「それわからんなんてことある??」とか「それ忘れたらあかんやろ......」みたいな問題をいくらか紹介したいと思います。

なお、今回の記事は問題選出の方針(と筆者の実力の低さ)の関係で比較的易しい問題ばかりとなっています。万が一上級者が読んでいたら温かい目で見守ってください。ここのコードこうするといいよ~とかあったらコメントで教えてくださるとありがたいです。僕と同じく初心者の方が読んでいたら一緒にこれらの問題で練習してつよくなりましょう。

ABC039B - エージェント高橋君

TK国のエージェントである高橋君は、とある正整数 X を青木君から受け取りました。

しかし実は青木君はAO国のスパイであり、本来渡すべき正整数を 4 乗したものを渡していました。

つまり、本来渡すべき正整数を N とすると、X=N4 です。

高橋君は非常に優秀なのでこれを見破りましたが、計算が苦手なので元の正整数、つまり N はなんだったのかがわかりません。

なので代わりにあなたが N を求めてください。

出典: B - エージェント高橋君

 いや非常に優秀なら4乗根計算してくれよ......。ちなみに僕が書いたコードはこんな感じです(自力で解きたい人のためにコード直貼りは避けてACした提出へのリンクを貼ります。使用言語はC++です。以下別の問題についても同様です)。

Submission #8924451 - AtCoder Beginner Contest 039

ABC015A - 高橋くんの研修

高橋くんは、ソフトウェア会社に勤めています。 その会社では、短い変数名はバグを生む原因だと信じられており、長い変数名を使う習慣があります。

いま高橋くんは 2 つの変数名を思いつきましたが、残念なことにその長さを見分けることが出来ません。

いろんな意味で可哀想な彼の代わりに、与えられた 2 つの小文字アルファベットのみからなる文字列のうち、文字数が長い方の文字列を求めてください。

 出典: A - 高橋くんの研修

 文字列の長さが比較できない高橋くん。文字数のカウントくらい出来てくれ。僕が書いたコードはこんな感じ。

Submission #8924760 - AtCoder Beginner Contest 015

ABC019A - 高橋くんと年齢

どんどん酷さが増していきます。

高橋くんは自分の年齢を忘れてしまいました。

ひとまず 3 人の友達を集めることに成功したので、その 3 人が予想する高橋くんの年齢の中央値を、高橋くんの年齢として代用することにしました。

高橋くんに代わって 3 つの整数 a,b,c から中央値を求めるプログラムを書いてください。

3 つの整数の中央値とは、それらを小さい順に並べて中央に位置する整数のことです。

出典: A - 高橋くんと年齢

 自分の年齢を忘れる。忘れたから友達3人合わせて年齢推定してもらってそれを代用するってのもおかしい。そもそも友達3人集めてる暇あったらその前に自分の身分証明書を探せ。僕の書いたコードはこちら。

Submission #8443186 - AtCoder Beginner Contest 019

ABC012A - 週末

高橋君は、週末が大好きです。高橋君は英語のデジタルカレンダーを使っているのですが、高橋君は英語の曜日を読むことができません。
カレンダーに表示されている曜日が与えられるので、あと何日で週末かを計算するプログラムを作成してください。
出典: A - 週末

英語の曜日を読めない。いや、読めないこと自体は百歩いや一万歩譲って許すわ。読めないもんを買うな。んでまあ僕が提出したコードはこんな感じです。

Submission #8931166 - AtCoder Regular Contest 012

ABC011A - 来月は何月?

高橋君は、来月遊びに行く約束をしました。

ですが、高橋君は頭が悪いので、来月が何月であるかが解りません。

今月が何月かが与えられるので、来月が何月であるかを出力するプログラムを作ってあげてください。

 出典: A - 来月は何月?

 ここまでくると言葉も出ませんね。もはや頭が悪いで済むレベルの話ではなくなってきています。まあんなことはともかく僕の提出をぺたり。

Submission #8931274 - AtCoder Beginner Contest 011

ABC013A - A

極めつけはこちら。

高橋君はとても英語が苦手で、アルファベットもまだ覚えきれていません。

そこで、高橋君のために、入力として与えられたアルファベットが A から数えて何番目のアルファベットかを求めるプログラムを作成してください。

幼稚園児か???????

 ......いや、ここまでならまだ幼稚園児で済むんですよ、ここまでなら。ここからが大問題なのです。いやここまででも十分問題だわ......。

ただし、高橋君は 5 より大きい数を知らないので、与えられるアルファベットは ABCDE のいずれかです。また、A 自身は A から数えて 1 番目であるとします(0 番目ではありません)。

 出典: A - A

 幼稚園児ですら10くらいまでは数えられるぞ。というかアルファベットより先に数字を覚えろ。てなわけでこのツッコミどころ満載な問題の提出コードはこちら。

Submission #8931516 - AtCoder Beginner Contest 013

おわり

いかがでしたか?(クソブログ特有の〆)

 あまり知られていない高橋くんの生態について理解してもらえたかと思います(?) もしこの記事で競プロに興味を持った方がおられましたら是非とも足を踏み入れてもらえたらなと思います(今年の4月に始めたばかりの僕が言うのもなんですが)。

ここまでお読みいただきありがとうございます。今回のAdvent Calendarにもう1つ記事を書けと脅されお願いされたのでまたそのときにでもお会いしましょう。では。

*1:AtCoder社の社長である高橋直大氏の名字から取ったと予想されている(yudegakiのブログより引用)

*2:魔法で小さくされピアノの上に乗せられる

*3:タイヤと木を組み合わせて鯛焼きを作る