AtCoder Beginner Contest 167 (ABC167) ふりかえり
5月10日に開催された、ABC167のふりかえりです。今回は危なかったけど、茶色パフォーマンス安定してきました。
※かなりごちゃごちゃしたコードになっているので、真似はおすすめしません。
A - Registration
普通に一文字ずつ比べた。
#include<bits/stdc++.h> using namespace std; int main(){ string S, T; cin >> S; cin >> T; for(int i = 0; i < S.size(); i++){ if(S.at(i) != T.at(i)){ cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0; }
B - Easy Linear Programming
うっかり “WA” を出してしまいました。原因がわからず、何回もミスするのが怖かったので下記のクソみたいな実装をしました。
B問題で "WA" 出してしまったときの、胸がキュンとする感じというか、冷や汗が出る感じ、健康に悪いです。
#include<bits/stdc++.h> using namespace std; int main(){ long long A, B, C, K, i, cnt = 0; cin >> A >> B >> C >> K; for (long long i = 0; i < K; i++){ if (i + 1 <= A){ cnt++; }else if(i + 1 > A + B){ cnt--; } } cout << cnt << endl; return 0; }
C - Skill Up
N と M の大きさをちゃんと確認していなくて本番ではスルーしちゃいました。bit 全探索で普通に解けました。今回最も後悔している問題です。
#include<bits/stdc++.h> using namespace std; int main(){ int N, M, X, i, j, bit, p_min = 1200001; cin >> N >> M >> X; vector<vector<int>> A(N, vector<int>(M, 0)); vector<int> C(N); //入力 for(i = 0; i < N; i++){ cin >> C.at(i); for(j = 0; j < M; j++){ cin >> A.at(i).at(j); } } //bit全探索 for(bit = 0; bit < (1 << N); bit++){ int p_sum = 0, flag = 0; vector<int> S; vector<int> A_sum(M); for (int i = 0; i < N; i++) { if (bit & (1 << i)) { S.push_back(i); } } for (i = 0; i < S.size(); i++) { for(j = 0; j < M; j++){ A_sum.at(j) += A.at(S.at(i)).at(j); } p_sum += C.at(S.at(i)); } for(i = 0; i < M; i++){ if(A_sum.at(i) < X) { flag = 1; } } if(p_sum < p_min && flag == 0) p_min = p_sum; } //結果の表示 if (p_min == 1200001){ cout << -1 << endl; return 0; } cout << p_min << endl; return 0; }
D - Teleporter
C問題からD問題へ逃げてきました。
テレポートの回数が 10^18 なので、普通に辿っていると間に合いません。循環しているところをうまく省略するのがミソです。
最初に一巡したときにいる町を算出し（下記コードの配列 H で管理）、最初の町からその町にたどり着くまでのループ回数 j 、一巡するまでのループ回数 i - j を求めます。
で、最初の町から (K - j) % (j - i) + j 回ループして終了。
最初、j > K の場合を考えていなくて"WA"になったのでかなり焦りました。ギリギリで気づいて "AC"。
#include<bits/stdc++.h> using namespace std; int main(){ long long N, K, i, j, cnt = 0, a, b, _K; cin >> N >> K; vector<long long> A(N), H(N, 0); for(i = 0; i < N; i++){ cin >> A.at(i); A.at(i)--; } i = 0; a = 0; while(H.at(a) == 0){ H.at(a) = 1; a = A.at(a); i++; } j = 0; b = 0; while(b != a){ b = A.at(b); j++; } a = 0; if(K - j < 0){ _K = K; }else{ _K = ((K - j) % (i - j)) + j; } for(long long k = 0; k < _K; k++){ a = A.at(a); } cout << a + 1 << endl; return 0; }
E - Colorful Blocks and F - Bracket Sequencing
たどり着きませんでした。
まとめと反省
- AB-D と解いてパフォーマンスは 798
- レート 194 → 282
- 最初の方で "AC" しても焦らない
- 問題はちゃんと読みましょう
【競プロメモ】Union-find Tree (暫定)
Point
- 各グループを木で表現する
- 互いに素な集合系を扱う
- 分割などには向いていない
うれしいこと
集合に新たな要素を加えたり集合同士をまとめるのが楽
最初に用意しておくもの
親を記述する配列（ i の親は par[i]）が必要になる。最初の初期化で全ての要素が違うグループにいる状態をつくる。このコードでは par[i] = -1 のとき、i が根になるとする。
vector<int> par; par.resize(N, -1);
木をつくる手順：
- 初期化（全ての要素が違うグループにいる状態をつくる）
- 外部の情報に応じて要素や木を結合していく
どんな動作がある？
根を調べる
par[i] で親を辿り続けた先に根がある。下のコードだとマイナスの値が出た時は根であるという判定になっているが色々な流派があるっぽい。自分の値（par[i] = i）にしておくなどなど。
int Root(int x) { if (par[x] < 0) return x; else return root(par[x]); }
要素同士が同じグループに属しているかを調べる
Root で根を調べ、それぞれの根が同じなら同じグループに属している。
bool Cmp(int x, int y) { return Root(x) == Root(y); }
要素や木を結合する
bool Merge(int x, int y) { x = Root(x); y = Root(y); if (x == y) return false; par[y] = x; return true; }
計算時間短縮のために行われる工夫
上記の関数を使って、Union-find Tree を作れるが、これだと計算時間があまり早くないです。改善点は ”木が長くなってしまうことで根を辿る際に時間がかかってしまう" ところにあります。具体的に行われていることは以下の二つです。
- 経路圧縮をする
- 木をつなげるとき、短い木の根の親を、長い木の根に設定する
経路圧縮をする
木が縦に長くなってしまうのは、親を辿っている間に、辿った要素を根につなぎ変えることで O(1) で根を算出することができるようになります。
int Root(int x) { if (par[x] < 0) return x; //else return Root(par[x]); else return par[x] = Root(par[x]); }
木の結合のさせ方を工夫する
長い木を短い木に結合させてしまうと、結合させた木はさらに長くなってしまいます。そのため、木をつなげるときに短い木の根の親を長い木の根に設定します。
bool Merge(int x, int y) { x = Root(x); y = Root(y); if (x == y) return false; if (rank[x] > rank[y]) { par[y] = x; } else { par[x] = y; if (rank[x] == rank[y]) { rank[y]++; } } return true; }
また、要素の数で決める場合もあります。初期化の際に根の値を -1 にしておくと、グループに属する要素の数を保持しておくことができます。
bool Merge(int x, int y) { x = Root(x); y = Root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; }
int size(int x) { return -par[Root(x)]; }
参考ページ（ほぼ丸パクリさせていただいたサイト。本当にお世話になっております。）
AtCoder ABC 157 D - Friend Suggestions (400 点) - けんちょんの競プロ精進記録
Union find(素集合データ構造)
Union-Find Tree を理解する！素集合系を扱うデータ構造 | アルゴリズムロジック
店名も場所も思い出せない、昔訪れたラーメン屋の大将
今週のお題「会いたい人」
会いたい人……家族や友人、好きな有名人、まだ顔を合わせたことの無い会社の同僚達など、誰について話せば良いのか迷ってしまいます。みなさんはどうでしょうか。私は今回、ある田舎で訪れたラーメン屋の大将について、昔の記憶を最大限に引き出して書き記していこうかと思います。
当時まだ小学校の2~3年生くらいでした。親がまだ若かったということもあり、アウトドアが好きなうちの家族は週末に3時間くらいかけて、よく釣りに行っていました。スマートフォンやカーナビではなく地図を使い、迷いながら移動をしていたのを覚えています。その日もウロウロしながら帰路についており、田舎の国道沿にぽつんと営業している一件のラーメン屋さんを見つけました。ラーメン大好き少年だった私の嘆願もあり、少し遅めのお昼ご飯をこのお店で食べることになりました。
田舎ならではの広い駐車場に車を停め、少し古びた店内に入ります。店内は来来亭のような感じでカウンター席と座敷に分けられていました。座席の壁際には本棚が沢山あり、そこに大量の漫画が並べられていたのを覚えています。来店した時間帯のせいかもしれませんが、店は大将1人で切り盛りをしており、お客さんはほとんどいませんでした。
この店の大将は少し無愛想な、癖のあるラーメン屋のオヤジといった印象でした。大人の私が来店してたら、特に関わることも無くラーメンを啜って帰っていたのでしょう。
しかし、そのような印象に反して、ここの大将はラーメンを持ってくるときやお会計のときによく話しかけてきました。
当時マルコメくんのような頭をしており、THE・元気な子供だったので、大人に話しかけられることは多かったのですが、大抵、笑顔で優しい声で話しかけてきます（今やると不審者認定されそう）。
一方で、この大将はとても無骨な感じで淡々と喋ってきたのが記憶に残っています。とにかく一言で、「おう、坊主、何歳だ？」「うまかったか？」とか聞かれた気がする。
お世辞にもコミュニケーションが上手な人には見えなかったので、子供ながらに「なぜこんなに気に入られているんだろう」
と疑問を抱いていました。大きくなってから考えて直してみると、店内の本棚にある「特攻の拓(ぶっこみのたく)」に反応して「とっこうのたくがおいてる！とっこうのたくがおいてる！！」と騒ぎまくっていたのがきっかけだと思います。
特攻の拓は横浜の暴走族を題材にした漫画です。鰐淵さんや一条武丸のコラ画像をみたことがある人はいるのではないでしょうか。内容に加え、連載時期が私の親世代であり、小学校3年生の子供がこれを知っているのはかなりのインパクトでしょう。年齢にかかわらず、自分の好きなものを他の人が知っているといい印象を持ちますよね。
親が話す昔話のエピソードで上記の話がよく出てくるので自分の中でも大切な思い出になっています。いかんせん小さくて記憶が曖昧なので、この辺りの記憶を鮮明に思い出したいというのが、この人に会いたい理由です。最後に無言でガツンとみかんを持ってきてくれたときの情景しか鮮明に思い出せません。物心ついてから行こうと画策していたのですが、親は詳しい場所を覚えておらず、自分も店名を覚えていないため、どうしようもありませんでした。昔のアニメキャラクターの名前で、何ともいえないポップさと渋さを醸し出していた気がするのですが、ネット検索では一向にヒットしません。
もう15年以上も前の話なので、潰れてしまっている可能性は高く、大将が存命しているのかも分からないのですが、仮に店を見つけた時のことをよく考えます。
同じように夏の季節に釣りに行き、帰路の途中で来店し、ラーメンが出てくるまで特攻の拓を読み、大将の姿を遠目に見ながら少し背脂の多い醤油ラーメンを啜る。店から出た後はコンビニでガツンとみかんでも買って、車内のクーラーをガンガンにしながら帰る。
そんなことがしたい今日この頃。
【宣誓】コロナ世代の新卒がAtcoderで競プロをはじめてみた
こんにちは、おふとぅん (@ofutun_desu) です。
突然ですが、今年の4月から Atcoder を始めました。
経緯と今後の目標について自分のために記しておこうと思います。
コロナに影響され脳死で競プロを始める
みなさんご存知の通り、某感染症の影響で多くの会社は従業員に在宅勤務を命じています。今年の春から社会人となった私も同様で、今は宿泊施設に詰め込まれ、そこでリモートでの研修を行なっています。外出の自粛をしなければならない状況で、飲み会やアウトドア系の遊びは大部分ができなくなってしまいました。このような室内で多くの時間を過ごすような状況になっているのが競プロを始める要因の一つになっています。
加えて、突如変わった社会情勢の影響で多くの会社が倒産の危機に見舞われています。ある程度の規模の会社に入れば潰れることはないだろうとタカを括っていた私ですが、突然職を失うことについて他人事と思えなくなりました（幸い、今在籍している会社は大丈夫ですが）。
こんなことから、会社に入った後も個人としての価値を上げ続けなければならないと考え、競技プログラミングに目をつけました。元々情報系だったこともあり、以前から漠然とコーディング力を上げたいと思っていました。また、AtCoder のレートを用いた就職活動をできる点も大きいです。この考えはとても安直であり、コーディング力だけで快適に生きていけるほど、IT企業は甘くないのでしょうが、今後のキャリアなどがはっきりしていない中で、直接的な恩恵がとてもわかりやすく示されていると飛びついちゃいますよね。
始める前のスキルや知識など
大学院では情報系を専攻していました。学部は機械系です。研究や授業で使用する程度ですが、C と Python と MATLAB あたりはある程度使えました。最近フロントエンド系をイジイジし始めました。応用情報技術者をギリギリ取得しています。
1ヶ月でやったことと現状報告
4月に始めると同時に、C++を勉強し始めました。とりあえず、3日間くらいで APG4b をおわらせ、その後は毎週 Beginners Contest に参加しながら、過去の Beginners Contest を空いている時間で解いていました。これまでのパフォーマンスとレートの推移は下の画像のようになっています。rated のコンテストは4つで、現状、まだ灰色のままです。
パフォーマンスに関しては、問題慣れしていないのでバラついていますが、茶色や緑のパフォーマンスもちょいちょい出ているので個人的には及第点だと思っています。5回のコンテストのうち3回（162~164）はABCを解いたところで終わりました。162ではCを解くのに1時間ほどかかってしまいましたが、163 と 164 は 20 分くらいで解くことができました。165はホテルのWifiが機能しなくなるという悲劇でABまでしか提出できず、撃沈。163 が unrated され、unrated 疑惑のかかっていた 165 が rated になったことがレート的にはかなり痛手でした。
C問題がACされた時間によってかなり順位が変わっていることからも、C問題とD問題の間に壁がありそうな気がします。似たようなレベルの問題を早解きできるようになるよりかは、D問題を解けるようになる方が、レートアップの確実性が増すと思ったので、D問題をいくつか練習し、166に挑戦しました。結果的にD問題まで通すことができ、初の緑パフォーマンスを記録しました。
詳しい問題埋め状況はこんな感じです。他のサイトの勉強期などをみるとAやBの簡単な問題から埋めている人が多いですが、自分は途中で飽きちゃったので、同じようなペースでCD問題にも取り組むようにしています。わからない問題については少し考えたら調べた方がいいと思っています（とか言いつつ何時間も考え込んでしまっていたりしますが）。
今後の目標とまとめ
まだ最底辺の灰色コーダーですが、少しずつ問題が解けるようになってきているのでとでも面白いです。プログラミングを習っても、「何書けばええねん」となっていた自分としては、何も考えずにコーディングの練習をできる環境は結構ありがたい。AtCoder は難しい問題も多くやりがいがあります（最近 paiza をやってみて思った感想）。Atcoder の経営者であり競技プログラマの chokudai さん曰く、「青色以上は一部上場企業でも一人もいないことが結構ある」というレベルらしいので、当面はこの辺りを目標に勉強していく予定。
話は変わるけれど、青色の位置付けがこんな感じなのに Beginners Contest で青色コーダーのレート帯がレート変動の対象になっているのが個人的に結構ツボです。明らかに Beginner じゃないやろっ、的な。
これからはたまに問題の振り返り記事を上げていこうかと思っているので、上級者の皆様、暖かい目で成長を見守ってください。
欲を言うと黄色（ここからは化け物、競プロの問題を解く機械だと思っていればいい）まで行きたいけれど、挫折しそうなのでやめておきます。
それでは。
さぞかしくだらない春休みを過ごしているであろうお前たちへ。
こんばんは、おふとぅん (@ofutun_desu) です。
修士論文を書き上げ、発表も無事終わり、ついでに国際学会で発表を行い、僕に残された春休みは3月のみとなりました。前半は海外旅行を満喫しており、良い滑り出しだったのですが、後半は会社からのお達しもあり、ほぼ、自宅待機となってしまいました。だれも責めることはできませんが、タイミングの悪いこと極まりないですね。
で、現状ですが、突然時間が空いてしまったもので、何をすれば良いのか本当にわからず、朝から晩まで Youtube を漁るような生活を続けています (結構格闘技が好きなので、朝倉未来選手のチャンネルにどっぷりハマっています)。
加えて「みんはや」というアプリにハマっています。
Q. みんはやとは？
A. みんなの早押しクイズの略称です。
おそらく、''みんなの早押しクイズ'' を略せ、といわれたら9割の日本人は ''みんはや'' と訳すのではないだろうか。
2秒で考えたような名前のアプリですが、ここ3日間、こいつに大量の時間を取られています。つまり、面白いということです。
quiznockや東海オンエアのメンバーがプレイしている動画がアップロードされています。なので既に人気です。たぶん。
ゲームの内容はシンプルで、4人もしくは2人で対戦を行うランダムマッチ、自分たちで問題や部屋を作れるフリーマッチがあります。
ランダムマッチにはレートが存在し、
C- → C → C+ → B- → B …
というふうにランクアップしていきます。これがモチベーションになってレートが上がらなくなるまで続けてしまった、というのが今回の全容です。
性格が悪いのですが、C ランク辺りの雑魚で俺 TUEEEEE してるときの爽快感は癖になります。
(相席食堂の長州力さんの回って面白いですよね)
中高生で習った内容も多く出題され、いわゆる ''エモみ'' を感じることもできます。恐らくエモみとともに、自分の頭から一般教養がどれだけ抜け落ちているのかも実感できるでしょう。
ちなみに、もう飽きました。
レートが A くらいになると俺 TUEEEEE が出来なくなり、爽快感が無くなりました。あと、合間合間に出てくる広告の女の子がとても可愛いかったのですが、忽然と姿を消してしまい、ちょっといいなと思った人に彼氏がいたときくらいの寂しさを感じています。
夜の蚊が「まじうぜえっ」ていうだけのお話
痒い、うるさい、眠れない。
今年も夏がやってきて、それに付随して蚊もやってきた。
私、おふとぅんはもう既に睡眠妨害をくらっている次第だ。
何故蚊が血を吸うのかというと、どうやらメスの蚊が産卵をするときの栄養源として欲されているようだ。意外なことに普段は花の蜜などを吸っているらしい。
(…産卵のときも花の蜜吸ってろよ)
血を吸う理由は分かったとして、どうして痒くするのだろうか。
どうやら、蚊が吸血するときに出す唾液にアレルギー反応を起こしているらしい。
その唾液にも一応目的があって、
一つ目は痛みを和らげる麻酔効果がある、というところだ。蚊の針は小さいがそれでも針なので、刺激を与えて気づかれないように、ということらしい。
二つ目は人間の血の凝固を防ぐためのものらしい。これは、人間の体内ではなく蚊自信が針や体内で血が固まってしまわないように用いられるそうな。
あー、一応目的はあるんだな、と。
二つ目の理由は置いておいて、一つ目の理由は腑に落ちない。痒くなければこんなもの、いくらでもくれてやっていいのに、と思ってしまう。
おまえら自覚しているのか？痒いから叩き潰されるんだぞ。正直、こちらからすると痛い方がまだマシである。
そもそも、蚊の脆弱な針に貫かれたくらいで痛いのだろうか。
あと、なぜ耳元ばかりを狙って飛ぶんだ。こっちが目を覚まさなければ、こっそり血を吸えるのに。少なくともお前達には利益しかないはずだが、なぜ耳元でその鬱陶しい羽音を聞かせてくるのか。
こんなことを思いながら、僕はそろそろ引っぱたいてやろうと攻撃態勢に入り、重い腰をあげ、つけたくもない電気をつけたと。
しかしながらヤツの姿はそこにはない。
ああああああああぁぁぁん、目が覚めた。
寝れない。
雨の日の楽しみ方を考えていたら、雨の日の何を楽しめば良いのか分からなくなってしまいました。
今週のお題「雨の日の楽しみ方」
『 雨の "日" の楽しみ方 』については多くの選択肢があると思う。たとえば、室内で行えることの可否に、天気という要素はほとんど関わってこない。読書をするもテレビを見るも、あるいはコーヒー片手に音楽に聴き入るのも良いだろう。
しかしながら、これらのことは晴れの日も行うことが出来る。要するに『 雨の日だからする 』のではなく『 晴れの日ではないからする 』という表現が僕としてはしっくりとくる。雨である必要はないのだ。
では、『 雨の "日しかできない" 楽しみ方 』といえばどういうものがあるのだろうか。例えば、雨の日しか出来ないオシャレをする。可愛い長靴や可愛い傘を身に纏う。
うん、確かに雨の日しか出来ない。しかしながら、自分自身、雨の中でさえ美しくあろうとする美意識は持ち合わせておらず、そもそも雨でなくとも美しくなく……。
とまあ、こういった感じで、雨の日しか実現できず、かつ楽しめることをさがすのに難航している次第である。
ふむふむ、どうしたものかと…
もしかすると、雨をあまり楽しめていないのではないかとも考えた。
が、それもまたしっくり来ない。
雨によって自分の行動を制限されてしまうことを加味すると、好きになれない。しかしながら、雨の、雨自身の雰囲気はなんとも嫌いになれないものがある。
『 雨の "日" を楽しむ 』
『 雨の "日しかできない" ことを楽しむ 』
…
例えば、雨という存在自身を楽しむのが良いのではないだろうか。
もし、何の付加価値も無いただの雨そのものに魅力を見いだせたのなら、外に出られなくとも、オシャレに興味がなくとも、雨の日を恒等的に楽しめるのではないだろうか。
これは結構自分の中でしっくりとくる。もし僕が雨の日を楽しんでいるとすれば、結局のところ、雨自身を楽しんでるのだろう。
ここまでくると次に、
雨の何を楽しんでいるのだろうかというところが、言語化できない。
そう、これらを言葉に落とし込むためには、おそらく美的センスが必要なのだが、前述のオシャレのところでも記したように、そんなセンスを持ち合わせていない。
と、いうことで、今回は美的センスばりばりの Instagramer が撮影した雨の写真いくつかペタペタして、いわゆる "いんすぴれーしょん" というものを得ようと目論んでいる。
目論んでいる...
( 何だかんだで、そこそこ文章書いた気がするのでそろそろ終わろうかなと )
これから本題に入るような雰囲気を醸し出しておきながら申し訳ないが、このあたりで締めさせて頂きたい。 まあ、ここまで書いたら、この記事は全部終わったようなものだ。
もしこの記事を最後まで読んでいる人が居るのであれば、結婚しよう。それぞれの『雨自身の美しさ』とやらを勝手に見つけてくれ。
無論、写真を選ぶのは美的センスの無い僕なわけだが、その辺は知らんぷりをして頂けると幸いだ。
