「私に天使が舞い降りた!」という作品に今更ながらどハマりしてしまった話
この記事は、 みす56代 Advent Calendar 2022の1日目の記事です。
わたてんを知ってますか?私は知っています。
TLのオタクの方々は当然、わたてんを知ってますよね。 知らない????早く観てください。
なんで今さらわたてんを推してんねんって思う人もいるでしょう、わたてんTVシリーズの放送はもう3年前ですからね。
映画「私に天使が舞い降りた!プレシャス・フレンズ」が最高だった
わたてんのTVシリーズは見たよ!って人でも、こっちを見てない人は多いんじゃないでしょうか。なんなら劇場版わたてんがあったことすら把握してない人るはずです。
でもね、この映画が本当に良かったんですよ。1時間ちょっとの短い作品なんですが、これでもかってほどおねロリと百合のオンパレードだったわけです。あまりにも高濃度のおねロリと百合にあてられて劇場で死んだ人もいるんじゃないですか?
これ劇場版の予告なんですが、もう最高の予感がしませんか?そう、最高だったんですねぇ……
上映終わったあと頬の筋肉が筋肉痛になる程度にはニヤニヤしてたよ。
ノアちゃんがひなたちゃんを振り向かせようとめちゃ頑張る姿、よりちゃんとかのんちゃんの無意識ないちゃいちゃと、はなちゃんがちゃんとみゃー姉のこと好きな姿とか……
それにさ、花ちゃんのおばあちゃんの○○話を、みゃー姉と花ちゃんに投影するのズルだよ、未来感じるんでしたよね??
わたてんの映画を見てニヤニヤ・オタク誕生
— たまかけ (@tamacake39) 2022年10月14日
顧客が求めてたものがここにあったという感じでした。本当に良かった。
(唯一残念なのは、映画の上映中永遠に周囲の席からおっさんの笑い声が聞こえてきたこと)
映画があんまりにも良かったもんだから、それまで原作全然買ってなかったけど、家帰ったときには全巻揃ってた
わたてんへの愛を叫びたい
2019年のアニメシリーズの放送当時もリアルタイムでわたてんを見てたわけなんですが、どういうわけか当時はそこまでハマったわけでは無いんですよね。たしかこの頃僕がハマってた作品といえば「やがて君になる」とか 「となりの吸血鬼さん」とか(結局いつも百合アニメ)でしたね…… まあそんなことはどうでも良くて
映画終わったあと1ヶ月くらい、マジで毎日わたてんを読んでニヤニヤしてるオタクになってたんですよね。人に見せられる顔をしてなかったことは確か。キモかったなぁ~~あのニヤニヤ
毎日わたてん読んで、わたてんのことを考える異常者になってる
— たまかけ (@tamacake39) 2022年10月23日
それにわたてんのことを考えすぎて、一生わたてんの漫画を模写する人にもなってた
ニヤニヤしながらイラスト描いてるオタクって犯罪?(はい)
だからさ、ちょっとだけわたてんについて語らせてくれ
みゃー姉とひなたの姉妹百合が好き
わたてんって、みゃー姉と花ちゃんの百合物語だと勘違いしてる人がいますよね、実はみゃー姉とひなたの姉妹百合が本質なんですよ(諸説)
姉妹百合って知ってますか?姉妹の百合のことなんですけど。
みゃー姉に甘えるひなたと、それを真正面から受け止めるみゃー姉の関係が、まあね……好きなんですよ……
こんなにストレートに愛を伝えられる姉妹って、もう見てるだけで幸せだし、ニヤニヤしちゃうし。世界平和はここにあるわけ。
作品中ではひなた→みゃー姉のLOVEが先行してるように感じるかもしれないけど、別にそんなことはなくて。 みゃー姉もひなたのことを一番に信用してるってのが、この姉妹の一番尊いところなんだぁ……
わかるなぁ……わかるよ……絶対にみゃー姉はお嫁に行かせたくないよな……
みゃー姉のことは頼んだよ……ひなた……
みゃー姉とひなたの姉妹百合は ついに 母親を置き去りにした……! お母さん……
ひなノアが好き
ひなノアが好きすぎてノートパソコンにひなノアのスッテカー貼ってしまった。オタクくんさぁ……
実は僕はね、姉妹百合も好きだけど、女児百合も大好きなんだ……
ノアちゃんは誰よりも「自分を可愛く見せる術」に長けてるんだけど、でもひなたちゃんを前にするとポンコツになってしまうっていう、このベタすぎるこのLOVEの形がめちゃ良い。良い。
もう苦しい、こんなイケメン彼氏なひなたと乙女なノアにニヤニヤ=オタクが止まらないよ……許してくれ許してくれ……キモい僕を許してくれ……
これでいてひなたもノアちゃんのことが好きなんだよなぁ……
ひなたにとって「みゃー姉と同じくらい好き」がどれほどの愛か考えたら、このせりふって……最高じゃない??
このシーン3回死んだ
よりかのという疑似姉妹が好き
わたてんを影から支える(じゅうぶん表から支えてるだろって反論は許します)、小依ちゃんと夏音ちゃんの百合。この2人の関係性はびっくりするほど純粋で、でも一番深い絆で……
なんてったって、(実質)姉妹百合であり、女児百合であるところが本当に良いんですよ。
産まれた時からずっといっしょ。これからもずっといっしょ。
こんなに素敵な百合を僕はね今まで一度も見たことが無いですよ。
この信頼感はやっぱりこの2人の関係性だから為せる技なんですよ。
小依ちゃんはめちゃドジっ子で子供っぽいのに、夏音ちゃんのことをずっと気遣ってて、やっぱりここにも世界平和があるわ。
閲覧注意
わたてんの世界でひなたたちと同級生になる妄想をしてる
— たまかけ (@tamacake39) 2022年11月26日
ひなたのことラブなワイくんは、ひなたの好意がみゃー姉以外に向かないことに安心して好きでい続けられる
もしひなたがみゃー姉のこと以外を好きになろうもんならノアちゃんがそれを許さないだろうから……
— たまかけ (@tamacake39) 2022年11月26日
おわりに
怪文書大変失礼しました。著作権的にマズいのでこの記事そのうち消えるかもな
実は本質はもう一つ、花みゃー姉があるんですけど、それは本編とアニメを見てくれ……
明日はガチプロえんじにゃー文月まぐくんの記事です。
あとあと、MISW 56代カレンダーまじで全然埋まってないからもっとみんな気軽に書こうよ
ではノシ
学生マイクロマウス大会の感想(懺悔)
これはWMMC Advent Calendar 2021の5日目の記事です.
学生マイクロマウス大会の感想(懺悔)
昨日(12月18日)、初めてのマイクロマウス大会、第36回全日本学生マイクロマウス大会に参加して来ました.
結果だけ先にいうと、とりあえず僕のステッパー機体は辛くも完走(1分55秒)したものの、スラローム走行がうまく動かずに、なかなか悲しいどう考えても僕の調整不足という結果となってしまいました.
今日の日記も兼ねて、大会の様子とかを書いていけたらいいなぁと思ったんですが、会場があまりにもばたばたしすぎて写真を撮れなかった今日がアドカレということを完全に忘れていたので、写真が全然ありません!ごめんなさい!ということでよくわからない感じになってしまった学生大会の感想文を書いていきます。
たまかけステッパー機「NYN号」について
NYN号はWMMCの標準機体をXFA機を参考に改造した機体です.標準機体からの相違点として、ホイールに既製品を、底板をCFRPを採用することで、機体の剛性、精度を向上させています。またセンサー基盤は3Dプリンタ製のセンサーマウントを使用することで、光軸合わせを容易にしています。 また、リポを固定するためのマジックテープをXFA機と同じ付け方にすることで、リポの互換性を図っています。これで大会にリポを忘れても安心だね! なめらかな配線と電圧計の7セグがキュートです
大会の走行について
第36回全日本学生マイクロマウス大会 - YouTube 走っているところは上のリンクから見られます。1時間14分00秒くらいです。
第一走・第二走
とりあえずスラローム探索をしようと試みます。これは事前から分かっていたことなのですが、連続しない旋回や櫛では問題なく動作するスラロームが、階段ではめちゃくちゃズレてしまうという問題がありました。今回の迷路は階段をメインにゴリゴリ誤差を試させるというような迷路であったため、スタートしてすぐ現れる階段に対して、当然爆死します。
第三走
完走しなければただ迷路にマウスを置きに来ただけになってしまうので、とりあえず旋回を超信地旋回のモードで探索することにします。これが今回の記録である1分55秒という記録になります。
審査員の先生に、「初めてなのに第2の策を用意しているのは優秀ですね」と言われましたが、ごめんなさい……準備不足なだけなんです……と心の中でごめんなさいをしたのもこのタイミングです。
暫定一位(右下)だった(あとから無限に抜かされる)
第四走・第五走
第四走では本来は超信地旋回モードで最短をやるべきなのですが、モード選択に超信地旋回モードを用意していなかったんですね! たまかけ「どうせスラローム探索くらいできるっしょww」とか言ってモード選択から超信地旋回モードを削除した過去の僕を殴り殺してきます。
まあとりあえず完走はできたので、仕方がないので直線加速スラローム最短モードを走らせます。よくわからないけどスラローム探索モードよりも先に行ってくれました。よくわかんなかったけどよくわかんなかったねー
まとめ
完走した感想ですが、はい、どう考えても僕の調整不足ですね。 直線加速モードwwwとか歩数マップ生成するプログラムヤバスギwwwとか言う前に、スラロームのパラメーターをまともに走るように調整しておくべきでした……
というか、既知のバグ・問題点が無限にあったにも関わらず、実装をまともに始めたのが一週間前ってマジですか?や、言い訳させてください……と思ったんですが、別に何もありませんでした。ただ日々を虚無に過ごしていただけでしたね……
流石に全日本はビッグサイトで虚無探索をするわけにはいかないので、これから僕は三ヶ月間バグつぶしの鬼になります。対戦よろしくおねがいします。
おまけ - 本厚木遠征の思い出
本厚木駅にはミスドがあるよ。素晴らしいね、これだけで本厚木に来た価値があるってもんでしょ。
これは本厚木駅の駅ビル7階で食べた中華 はたはたさんに餃子おごってもらった、ごちそうさまでした
帰り道はノリで引退発表がされたVSE車
新宿駅に葬儀鉄が無限人湧いていてびっくりしましたね。
C#の入門をしたい
この記事は、 MISW 56th Advent Calendar 2021の1日目の記事です。
C#の入門をしたい
はじめましての方ははじめまして、そうでは無い方もはじめまして。どうも、56代何もしない研プロ研のたまかけと申します。
さて今回ですけれども、アドベントカレンダーを立てたはいいものの 何を書けばいいんだ…… となってしまって、それに12月2日、この記事が公開された翌日ですね、に微積のテストが迫っていたもので、軽めに書ける記事をやっていこうと思います。
この記事は、自分のようなC/C++のの基礎文法がわかるよという人が、C#を始めるにあたってちょっと躓いたなというところをまとめてみる、という感じで書いていこうと思います。
C#の入門をしなきゃいけないらしい
なんやかんやでC#の入門をする必要が出てきてしまったので、早速入門していきます。私が新しい言語の入門をするとき、とりあえずその言語を使ってAtCoderの問題が解ければとりあえずの入門はできるだろと考えているので、今回はAtCoder Beginner Contest 218のA問題からE問題をC#を使って解いて行きます。
AtCoderの問題解けた程度で言語の入門した気になってんじゃねーぞとの声が盛大に聞こえてきますが、そんなことは誰も気にしない。
まああとはC#といえばオブジェクト指向のなんとやらがアレでアレらしいので、そこらへんも触っていきます。
環境構築
本来なら早速問題を解いて行きたいところなのですが、やっぱりプログラミング言語の入門にあたって環境構築というものは避けて通れません。むしろ環境構築が一番むずかしい
ここではAtCoder環境で使えるC# (.NET Core 3.1.201) の環境を作っていきましょう。
環境はWSL上に作っていきます。
.NET Coreを使用した開発について
.NET Coreで開発するためには、最低限、.NET Core SDKをインストールすればよい。
↑の記事を参考にしましてWSL上に簡単なC#の実行環境を導入、それでは本編やっていきましょう。
ほんへ
A問題
整数Nと文字列Sが与えられるので、SのN文字目がoかxで判定する問題。
▶コード
using System; namespace main { class Program { static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); string s = Console.ReadLine(); if (s[n - 1] == 'o') { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } }
めちゃめちゃ簡単な問題なのに自動生成のコードが長すぎて泣いちゃった。 早速よくわからない概念、using、namespace、classとかが出てきましたね。 いそいそと検索をかけると・・・
名前空間 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C クラス - C# によるプログラミング入門 | ++C++; // 未確認飛行 C
namespaceを使ってclassを種類ごとに分けて管理する、またclassを使って機能をまとめて管理することができるんですねぇ~~なるほど
namespaceは省略もできるっぽいので、今回の記事では省略する方向で行きましょう。
あと標準入力が
int n = int.Parse(Console.ReadLine());
stringで受け取ってそれぞれの型に変換する感じ、pythonっぽいですね
classとstructは違うんか??
気になるのはclassとstructの違い。 C++ではclassとstructはほとんど違いの無いものとして扱うことができましたが、C#ではそうもいかないようです。C++では双方ともにstack領域にメモリを確保していましたが、classはメモリがheap領域に、structはメモリがstack領域に積まれるようです。
C#で大規模なデータを高速で処理したいときは、structを使ってデータをstack領域に積むことで値型として扱い高速にアクセスする、とかいうことができるらしいです。ちょっと頭の片隅に入れておきたいですね。
無知なもので詳しいことをあんまり語れないので、詳しく知りたい人は
C# のメモリ管理 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C
を参照してみてください。
B問題
問題は26個の数列Pが与えられて、一般的なアルファベットのi番目の文字がPi番目になった世界でのアルファベットの順番を出力する、という問題。 普通にchar型の配列に指定された順番でアルファベットを詰めていけば解けそうですね。
▶コード
using System; using System.Linq; class Program { static void Main(string[] args) { int[] S = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray(); char[] ans = new char[26]; for (int i = 0; i < 26; i++) { ans[i] = (char)('a' + S[i] - 1); } for (int i = 0; i < 26; i++) { Console.Write(ans[i]); } Console.WriteLine(); } }
配列を宣言するときにC++とかには無い文法、newが出てきました。C++では変数の宣言と同時にインスタンスが作成されていましたが、C#ではそうでは無いようです。
例えばint misw[];
としたとき、確保されるのはstack領域のみであり、misw = int[334];
として初めてheap領域に実際の値を格納するメモリを確保します。
これC++のように変数の宣言と同時にインスタンスを作成するようにしなかったのはなんでなんでしょうかね……?
ところでB問題では普通の配列を使いましたが動的配列、Listを使う際は
List<int> S = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToList();
と、配列とほとんど同じ要領で書くことができるようです。
C問題
▶コード・長い読む価値なし
文字列の配列が2つ与えられるので、2つの文字列配列の#
で表された部分に関して回転、平行移動によって重ね合わせられるか、という問題。
アルゴリズム的に難しいことは特になくて、上をごりごり実装していく。
using System; using System.Linq; using System.Collections.Generic; class Program { public static List<string> Trim(List<string> s) { int u = 0, d = s.Count - 1, l = 0, r = s.Count - 1; int n = s.Count; bool flag = false; for (; u < n; u++) { flag = false; for (int i = 0; i < n; i++) if (s[u][i] == '#') flag = true; if (flag) break; } for (; d >= 0; d--) { flag = false; for (int i = 0; i < n; i++) if (s[d][i] == '#') flag = true; if (flag) break; } for (; l < n; l++) { flag = false; for (int i = 0; i < n; i++) if (s[i][l] == '#') flag = true; if (flag) break; } for (; r >= 0; r--) { flag = false; for (int i = 0; i < n; i++) if (s[i][r] == '#') flag = true; if (flag) break; } List<string> res = new List<string>(); for (int i = 0; i < d - u + 1; i++) { res.Add(s[u + i].Substring(l, r - l + 1)); } return res; } public static List<string> Rotate(List<string> s) { int h = s.Count, w = s[0].Length; List<string> res = new List<string>(); for (int i = 0; i < w; i++) { char[] tmp = new char[h]; for (int j = 0; j < h; j++) { tmp[h - j - 1] = s[j][i]; } res.Add(new string(tmp)); } return res; } static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); List<string> S = new List<string>(); for (int i = 0; i < n; i++) { S.Add(Console.ReadLine()); } List<string> T = new List<string>(); for (int i = 0; i < n; i++) { T.Add(Console.ReadLine()); } S = Program.Trim(S); T = Program.Trim(T); bool flag = false; for (int i = 0; i < 4; i++) { if (S.SequenceEqual(T)) { flag = true; } S = Program.Rotate(S); } if (flag) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }
C#のstring型は要素が変更不可なので、下の画像のように要素変更することができないんですね。 {{
string phrase = "hanshin" char[] phraseAsChars = phrase.ToCharArray(); phraseAsChars[2] = '4';
みたいに、一旦char型の配列に直す必要があります。ここは競プロをする上で非常にめんどくさpointですね。
まあ文字列をこまこま処理するなんてことは競プロ以外ではほとんどやらないでしょうから、(やるにしても単語、文単位の置き換えくらいなもの?)これで困ることはあまりないでしょう。
staticとはなんぞや??
staticは、クラス自身が変数やメソッドを持てるようにする機能のことのようです。
ではC問題のコードの中でTrim関数、Rotate関数を宣言する際に付いているstaticを除いて実行してみるとどうなるでしょう。
Program.cs(85,13): error CS0120: An object reference is required for the non-static field, method, or property 'Program.Trim(List<string>)' [/home/tamacake39/ppcpp/main/main.csproj]
とエラーが発生して実効することができません。
調べてみると
こういうことらしい
クラス内のメンバーはクラスのインスタンスを生成して初めて使用可能(メモリ展開される)となります。しかし上記例のStaticMethodはstaticなメソッドなので、インスタンス化せず使用できます。(メモリが最初から確保されている) ところが、上記例のようにそのメソッド内にインスタンス化しなければ使えない変数objが含まれていると、メソッドを呼び出した際に、使用不可能な(メモリ上に存在しない)変数objにアクセスすることになり、正常な処理ができなくなります。
なるほど。main関数のようなstaticメソッドからインスタンスメソッドを呼び出そうとすると存在しないメモリへアクセスしてしまうことになるんですね。
ではどうコードを書けばよかったのかというと、staticを除いていた場合は例えば
Program Trimer = new Program(); S = Trimer.Trim(S); T = Trimer.Trim(T);
とインスタンス化してあげる必要があります。 しかし上でいうTrimインスタンスはデータに対して定まった一つのデータを返すいわば「関数」のため、そもそも複数のインスタンスが存在する必要がありません。 そこで唯一存在するstaticメソッドとして宣言することで効率よくデータを処理することができるわけですね。 (※ここ少し勘違いが入っている可能性があります。間違いがあったら指摘お願いします。)
D問題
たくさん点が与えられるので、そのうち4つを選んで長方形を作れるかという問題。 長方形は対角線の2点が分かれば決定できるので、連想配列などを使って2点選んだときにもう2点が存在するかを判定すればOK
▶コード
using System; using System.Linq; using System.Collections.Generic; class Program { static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); Dictionary<Tuple<int, int>, bool> map = new Dictionary<Tuple<int, int>, bool>(); List<Tuple<int, int>> input = new List<Tuple<int, int>>(); for (int i = 0; i < n; i++) { var values = Console.ReadLine().Split().Select(int.Parse).ToArray(); input.Add(new Tuple<int, int>(values[0], values[1])); map[new Tuple<int, int>(values[0], values[1])] = true; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (input[i].Item1 == input[j].Item1 || input[i].Item2 == input[j].Item2) continue; if (map.ContainsKey(new Tuple<int, int>(input[i].Item1, input[j].Item2)) && map.ContainsKey(new Tuple<int, int>(input[j].Item1, input[i].Item2))) { ans++; } } } Console.WriteLine(ans / 2); } }
連想配列と一概に言えど、何個かあるらしい。違いはわからないけれど、要素の検索に関して、ListがO(n)であるのに対して、DictionaryとHashSetがO(1)(?!?!これマジ?!?!)、SortedDictionaryとSortedSetがO(log n)なことを覚えておけば良さそう。
あと上のコード内でmapからtupleの要素を検索する際に
map.ContainsKey(new Tuple<int, int>(input[j].Item1, input[i].Item2)))
としているのですが、これは毎回newをする必要があるのでしょうか。コンストラクタの無用な作成はプログラムの低速化の元だと聞いたので、解決策があればぜひ教えていただきたいです。
E問題
典型最小全域木の問題 親の顔より見たUnionFindを使って解いていきましょう。
▶コード・長い読む価値なし
当然C#のdsuライブラリは持っていないので、ACLを参考に書いていきます。 基本的なところはC++と変わらないので特に難しいことは無いです。(むしろ闇の言語C++の方が意味不明……)
using System; using System.Linq; using System.Collections.Generic; class Program { static void Main(string[] args) { var nm = Console.ReadLine().Split().Select(int.Parse).ToArray(); int n = nm[0], m = nm[1]; List<Tuple<int, int, int>> cab = new List<Tuple<int, int, int>>(); for (int i = 0; i < m; i++) { var input = Console.ReadLine().Split().Select(int.Parse).ToArray(); cab.Add(new Tuple<int, int, int>(input[2], input[0] - 1, input[1] - 1)); } cab.Sort(); long ans = 0; dsu uf = new dsu(n); for (int i = 0; i < m; i++) { if (!uf.merge(cab[i].Item2, cab[i].Item3)) { ans += cab[i].Item1 > 0 ? cab[i].Item1 : 0; } } Console.WriteLine(ans); } } class dsu { public dsu() { } public dsu(int n) { _n = n; parent_or_size = new List<int>(); for (int i = 0; i < n; i++) parent_or_size.Add(-1); } public bool merge(int a, int b) { int x = leader(a), y = leader(b); if (x == y) return false; if (-parent_or_size[x] < -parent_or_size[y]) Swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return true; } public bool same(int a, int b) { return leader(a) == leader(b); } public int leader(int a) { if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } public int size(int a) { return -parent_or_size[leader(a)]; } void Swap<T>(T a, T b) { var t = a; a = b; b = t; } private int _n; private List<int> parent_or_size; }
ところでC#には標準でSwap関数が用意されてないのは驚きました。別に無くても何も困らないけど……
classを作成してその中にメソッドを定義しているわけですが、各メソッドの前にはpublicとprivateが記述されています。これはアクセスを制御するための機能で、これを用いると別のクラスから各メソッドに対するアクセスを自由に許可したり禁止したりすることができます。
これがあると何が嬉しいのかというと、外部から使って欲しいメソッドと使われたくないメソッドを明確に分けることで、メソッドが想定されていない使い方をされることによる予期せぬ動作を防止できたり、プログラムが複雑になっても使われたい機能を明確にすることができます。 非常にバグらせにくくコードを書くことができる便利な機能ですね。
感想
C#……難しい……これを初心者向け言語として紹介してる人はどういう考えなんでしょうか…… まあ確かにunityやwindowsのGUIアプリには欠かせない言語ですから、遅かれ早かれ入門しないといけない言語というのは確かですね。 あと、JavaやC#はインタープリターを介して実行するから遅いので競プロには向かないという定説があるようですが、今回入門した限りではあまりその遅さを感じなかったのは意外でした。
なんというかC#、至るところで型のことを意識させてくれるので、C++でクソコードばかり錬成している自分に突き刺さりました。C++では暗黙の型変換をしまくってしまうのですが、意識的にキャストする必要があるC#ではバグらせにくい?のでしょうか。
蛇足
これから25日間続く(はず)アドベントカレンダー、後続の記事もぜひよろしくおねがいします! 明日は森くんの「ク ソ 記 事 ! ! ! !」だそうです。森のことですからクソ記事といいながらなかなかクオリティの高い記事を書いてくるはずです。ワクワクですね。
B. Counting of Trees
書くことが特に無いので、精進記録を書くことにしました。
一番最近やった問題でちょっと詰まったところがあったので、それを書きます。
N要素からなる整数列D1,...,DNが与えられて、それを使って何通りの木を作れるかという問題。Diには頂点1からの距離が与えられる。
まず端的に言うと自分は「Diには頂点1からの距離が与えられる。」を見逃していて、D1=0の確認をしなかった。(じゃあどこからの距離が与えられてたんだって話ですが…)
正直そこさえ気をつければあとは難しくない。
1.距離iの頂点の個数をMiとしてまとめる。
2.距離0の点が一つだけであるものと、距離0から一番大きい距離までの間の距離が1ずつ増えていないものを弾く。
3.各距離の頂点に対しての組み合わせの個数を求める。
で求めることができる。
組み合わせの求め方は、
7
0 3 2 1 2 2 1
を例にとって考えると、距離0の点を選ぶ方法は一通り、距離1の点を選ぶ方法は2つの頂点をつなげる先を1つの頂点から選ぶので1通り、距離2の点を選ぶ方法は3つの頂点をつなげる先を2つの頂点から選ぶので2^3より8通り、同様に距離3の頂点のつなげ方は3^1より3通り。
以上をかけ合わせて24通りとなる。
よって距離1から最大の距離まで、Mi-1^Miをかけ合わせたものになる。