ももはらの日記

日記を書きます

競プロ復帰してから約10ヶ月、黄色復帰するまでにやったこと

はじめに

こんにちは。ももはらです。 ついに黄色復帰しました！

2023/4/8 に競プロ復帰してすぐ青落ちしてから約10ヶ月経ち、2024/2/10にようやく黄色復帰することができました。
この記事では、黄色復帰するまでにどういうことをしてきたのを書こうと思います。
※思い出振り返り的な要素が強いのでどうやったら強くなるかみたいなことは書いてないです。

なぜ競プロをやめていたのか

2022/04/09 ~ 2023/04/08の間、競プロをやめていました。

理由はいくつかありますが、特に強いのは下記2つだと思います。

  1. ARC119で赤パフォをとっており、最高パフォの更新ができなくなったこと
    赤パフォ自体はめちゃくちゃ嬉しかったのですが、それ以降の成績がよくても橙パフォくらいなので、最高パフォ更新はこれから一生なさそうだなという気持ちに。。

  2. コーディング欲が満たされていたこと
    2022/4/1に転職しており、業務でコードを書くようになったので、一時期コーディング欲が満たされていました。 土日までコーディングしなくっていいかという気持ちになる日が増えました。

ので、スコアタ欲的にもコーディング欲的にも微妙になり、やめていました。

なぜ競プロ復帰したのか

マラソンに出てみたらratedの楽しさを思い出しました。

興味本位で2023/04/09のAHC019に出てみたらとても楽しくて、マラソンの知識を勉強したり、解法ツイートを追ったりしてるうちにアルゴの方もrateで出たい！という気持ちが強くなりました。 下記は最初でテンション上がって書いてた参加記です。 momoharahara.hatenadiary.com

競プロ復帰してみて

復帰後2回目のARCで青落ちしてしまったのですがレート変動するのが楽しいし、青落ちすると当然ratedのコンテストも増えるので楽しくコンテストに参加しました。ただ、やはり黄色復帰するには継続的に出ることが重要で、そのためにはモチベーション管理がかなり大切だったと実感しています。
特にモチベが上がったこととして、CodeQUEENと競プロ部設立について書こうと思います。

CodeQUEEN

5月ごろに「CodeQUEENのコンテスト概要に不備がないかどうかのレビューしてくれませんか？」という依頼が来て、CodeQUEENの存在を知りとても素晴らしいコンテストが開催されると思いました。また、かなり競プロ的にブランクがあった自分に依頼が来たことにびっくりしました。
とても楽しみな気持ちに反して、当時はすでに結婚前の挨拶旅行の予定を立てており予選とめちゃくちゃにかぶっていたので、かなり参加を迷っていたのですが、夫が「でたほうがいいよ」と背中を押してくれて、出ることにしました。

6月ごろにはCodeQUEENのスポンサーの話をいただきました。来年も再来年も開催してもらえるように自社に話を出し、スポンサーすることを許可してもらうために頑張っていました。理解のある弊社のおかげで無事スポンサーできて、とてもありがたいです。

7/1の予選は実家に挨拶するために沖縄にいて結構ハードスケジュールの中で出たのですが、意外と調子が良くて決勝進出したメンバーの中で2位の成績を取ることができました。

決勝当日は、集合時間を1時間勘違いしておりかなりギリギリだったのですが、スポンサーとしてスタッフ参加した夫に道を教えてもらって何とか間に合いました。
結果は3位で予選よりも順位下がってしまってかなり悔しかったです。でもこれが結構モチベになっていて、次があったら必ず勝つという気持ちになれました。
また、これまでオンサイトの決勝に出たことはあっても優勝争いなどとは無縁だったのですが、色々な方に応援いただけてとても嬉しかったですし、表彰台に上がって賞金をいただくなどとても貴重な経験ができました。

懇親会では普段見ないような光景が広がっており、色々な方と話せて楽しかったです。決勝の2日前に入籍していたのもあって、かなりの方に結婚を祝ってもらえたのも嬉しかったです。

競プロ部の設立

社内で競プロ部を設立しました。

元々ゆるふわオンサイトなどの開催はしていたのですが、みんな学生時代からやっている方が多く、特に集まって勉強会などはしていませんでした。
そんな中、「週一で何かしたくない？」という声が社内であがり、ちょうど2月のゆるふわオンサイトの運営責任者にもなっていたので、部長をやることになりました。

週一の勉強会などを始めてみて、「コンテストの振り返り」時間をもうけたのが自分のレートにかなり効いているのを感じています。
ネタバレを踏まないためには、土曜日のABCから月曜日の「コンテストの振り返り」時間までに問題を解いておく必要があり、ネタバレ嫌いの自分にとってはかなりの強制力になっています。
また、コンテストの振り返りの中で、自分が問題を感覚的に解く一方で、社内の強い方たちは典型知識や数学的知識を使いこなして論理的な思考のもと解いていて、「再現性の高い解き方」について考えるようになりました。
もっと自分も論理的で再現性の高い解き方ができるようになってパフォーマンスを安定させられるよう頑張りたいです。

おわりに

全然黄パフォ以上が安定しておらず、まだまだ青黄往復するとは思いますが、レート変動を楽しみながら続けていければと思います。
参考: AtCoderRatingContributionGraph

CodeQUEEN 2024 の開催も決まったので、より強くなれるよう頑張っていきたいです！

AHC初参加記＆AHC019参加記

はじめに

こんばんは。ももはらです。
今回AtCoder Heuristic Contest 019でAHCに初参加してみたので、記録の意味で参加記を書こうと思います。
高度な知識とかをお求めの方はブラウザバックでお願いします。

環境構築

Rustの勉強もついでにしちゃおうかな？と思ってたので最初にRustをインストールしました

インストールはここから：はじめに - Rustプログラミング言語

AHCは問題文と一緒にツールも置いてあってすごい
ローカル版にテストケースも入ってたので実行してみたりしておお！ってするのをやってました
atcoder.jp

ちなみに結局Web版の方がVisualizeされてわかりやすかったので手元はほとんど使ってません！

問題文を読んでみる

長いです。困りました。
どう取りかかっていいか全くわからないです。
(あと最初めちゃくちゃに誤読していて、ブロックで作る図形が2個じゃなくてN個だと思ってました)

とりあえず困ったのでマラソン自体を勉強するべく記事を漁ったところ、terryさんの記事がひっかかりました。

www.terry-u16.net

AHC001についての記事で、記事に沿って自分も実装してみることにしました。

AHC001の問題概要：いろんな企業が(xi,yi)を含む位置に大きさriの広告を出したい

なんだかAHC019より簡単そうに見えます（２次元ですし）

さっそくブログに沿って次の流れで実装しました

①1*1の豆粒広告をたくさんおく
②ランダムに大きくしてみる
③ランダムにシフトしてみる

あとは、マラソンだと「秒数制限が来たら処理を切る」みたいなのが必要だったのでライブラリ化したりしました。
焼きなましパートは力尽きたのでやれてません（やらなくば）

とりあえず正の得点を得て、貪欲してみて、話はそれからでいいんだなというふんわりした理解を得ました。

いざAHC019に

atcoder.jp

問題概要：正面のからみた絵と真横から見た絵が２組渡されるので、それぞれについてブロックを組み合わせて立体を作りたい。ブロックはできるだけ大きくて少ないほど嬉しい。それぞれでブロックを共有してもいい。

1×1×1配る

提出1

AHC001の経験を生かして？豆粒からです。
３次元なのもあって実装をバグらせまくります。

ようやくできた！と思って喜び勇んで出したらWAが帰ってきます
焦りましたがデバッグ用の出力そのままにしちゃってました
（あと実は数字もずれてました）

98個です

ランダムな2つをペアにする

提出2

ランダムに２つ選んでペアにします

53個まで減りました

ペアにするときに貪欲で大きくする

提出3

今度はペアにするときに大きくしてみようとしました
６方向みて、ペアのどちらも大きくできそうだったら大きくします

52個であまり小さくならないです
強い気持ち出だすとスコア的にはよさそう？ってなります

提出4

バグに気づきます
continueすべきところでreturnしていて、最初の大きくする方向がダメだったときに全て1*1*1で終わっていました

39個になりました

提出5

リファクタして、while文で描いてた部分を再帰にしたり、0-indexで管理できるようにしました
再帰にしたら見え易くはなったのですが、遅くなったことによってかスコア的には落ちたので戻しました

今も必要なブロックにだけおくようにする

提出6

最初に正面から見ても横から見ても1のところに全て置いていたのですが、もう置かれてる列や行かどうかを管理して、
ペア作りでどちらも置かなくていい場合は無視するようにしたり、最後の穴埋めでも置かないようにしました

17個です
一気に減りました

数ケース回して、一番いいやつをとる

提出7

リファクタでだいぶ綺麗になったので、１手戻しもできそうなみためになったので、
５ケース回して、一番スコアがいいものを採用する実装もしてみました

13個です
いい感じです
でもプレテストの合計得点的には下がります（謎）

回転してあわせてみる

提出8

実装が大変そうだったので後回しにしていた回転を実装します

サンプル的には13個で変わらないんですが、３方向だけでもだいぶスコアが低くなり順位上がりました

提出9

3方向でいい感じだったので、頑張って12通り作ります

ついに10個になりました
だいぶいい感じです

１個のものを減らしたい

Nが大きいケースについて考察できてなかったのでseed=97のケースなどでビジュアライズしてみます

いいかんじに22個までは絞ってくれるんですが、1*1*1のやつがめだったりしています

体積2以上の塊になるときしかペアを作れないようにする
→ヒット率が下がるので、処理が周りきらず逆効果

最後に1同士となりあっていたらくっつける候補にして２ずつのペアにできないかを探索する
→ペアの入れ替えがうまくいかずに実装で敗北

という感じでタイムアップしました

結果

システスで321位から311位になりました。
初参加で水パフォでて最初の問題文を見たときの絶望感を考えると思ったより高くて嬉しいです。

感想

AHC初参加でしたが、提出するたびにスコアや順位が上がったり下がったりするのでハラハラして楽しかったです。

アイデアが出なくなるよりも先に時間の限界がきてしまったので、次はより時間をとって取り組めるようにしたいですね。
AHCはたくさん出るほどレートが高くなるみたいなので、たくさん参加してレートあげていきたいです！

ここまでお読みいただきありがとうございました。

AtCoderで黄色になりました

はじめに

　こんにちは。ももはらです。
　ついに黄色になりました！！！！

　1983になって黄色リーチになってからだいぶ長かったですが黄色に無事なれてよかったです。
　青になってから思い出深かったことを書いていこうと思います。
　役には立たないですが、暇だったら読んでください。

目次

思い出深い問題

　青になってから最初、なぜか緑diffに苦戦していたので緑diffが多いですが、苦戦した問題を紹介していきます．

パナソニックプログラミングコンテスト2020 D-String Equivalence

atcoder.jp

　まずは、忘れもしないこの問題、、、「やりたいことはわかるが実装できない！！！！」となり、コンテスト時間も迫ってきたので、「気合の10重ループや！！！！」をかきました。

void solve() {
	ll n;
	cin >> n;
 
	ll i0 = 0;
	string s(n,'a');
 
	if (n == 1) {
		cout << s << en;
		return;
	}
 
	REP(i2, 2) {
		s[1] = 'a' + i2;
		if (n == 2) {
			cout << s << en;
			continue;
		}
 
		REP(i3, i2+2) {
			s[2] = 'a' + i3;
			if (n == 3) {
				cout << s << en;
				continue;
			}
			REP(i4, max({ i2,i3 }) + 2) {
				s[3] = 'a' + i4;
				if (n == 4) {
					cout << s << en;
					continue;
				}
				REP(i5, max({ i2,i3,i4 }) + 2) {
					s[4] = 'a' + i5;
					if (n == 5) {
						cout << s << en;
						continue;
					}
					REP(i6, max({ i2,i3,i4,i5 })+2) {
						s[5] = 'a' + i6;
						if (n == 6) {
							cout << s << en;
							continue;
						}
						REP(i7, max({ i2,i3,i4,i5,i6 })+2) {
							
							s[6] = 'a' + i7;
							if (n == 7) {
								cout << s << en;
								continue;
							}
 
							REP(i8, max({ i2,i3,i4,i5,i6,i7 }) + 2) {
								s[7] = 'a' + i8;
								if (n == 8) {
									cout << s << en;
									continue;
								}
								REP(i9, max({ i2,i3,i4,i5,i6,i7,i8 }) + 2) {
									s[8] = 'a' + i9;
 
									if (n == 9) {
										cout << s << en;
										continue;
									}
									REP(i10, max({ i2,i3,i4,i5,i6,i7,i8,i9 }) + 2) {
										s[9] = 'a' + i10;
										if (n == 10) {
											cout << s << en;
											continue;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

atcoder.jp

　どうしてこんなことに。。。
　てか今数えたら9重ループでした。
　一文字目は流石に賢く処理しててちょっと安心しました（え？）
　ちなみにこの回で入水したんですが、再帰がかけない青コーダーはやばいのでおちて良かったと思います。

ABC161 D-Lunlun Number

atcoder.jp

　前回で何も学んでなかったしupsolveもしてなかったので当然再帰がかけずとけませんでした！
　ルンルンナンバーでまったくルンルンできなかった！！！

　ちなみにこの回はLunlun Numberを切り捨てることで冷えを回避しています。

　流石にこのあと緑diff対策の精進ちょっとしてました。。。

ARC109D-く

atcoder.jp

　この問題もかなり苦い思い出です。
　コンテスト終了18秒後にACしました。

　この問題をきっかけに速度が圧倒的に足りないと感じてえでゅふぉバチャをたくさん走るようになりました。
　後、チョコ食べてた時間なかったら通ってたなーってなったので、コンテスト中にチョコを食べる量を減らしました。ダイエットにも貢献してるかもしれません...

チーム練

harahara

　青になってからちょっとした頃(4月？)に、stoqくんとhanyuくんをお誘いして、ICPC向けにチームharaharaを組むことに成功しました！
　当時は水青青だったのが今は青黄黄ですね。
　チームメイト二人はhighestを1900にのっけている中、1800で停滞してた時期もあったので、追いつけて嬉しいです。
　わりと停滞してた時期は研にも競プロにも苦しんでたんですが、ICPCに出るのだからこんなところで競プロ引退しちゃダメだよなって気持ちで頑張れました。
　や、まじでチーム組んでなかったら引退してたな。ありがとう。。。

　ICPCのセット、いつもとは違うグラフの問題（最大独立集合とかの指数アルゴリズム系？を使う問題）とかも多くて、面白いです。
　構文解析担当になったのもあって、苦手な再帰系の実装もかなり上手くなった気がします。国内予選Dとか構文解析パート以外も楽しくてすきすきです。
　あとはチームメイトに恵まれたおかげで、苦手分野は全部投げて自分の好きな問題を好き放題解いて良いので、チーム練バチャはかなり好きです。
　
　模擬国内とかの参加記です。
はてな

合宿コン

　HUPCとかACPCとか、オンラインチーム戦してとても楽しかったです。
　普段組まない人と組むの楽しいし、１週間で死ぬほど問題解けたのがすごい競プロ週間って感じで満喫できて最高でした。
　ACPC day2でharaharaで9位とれたのかなりうれしかったです。

詳しい参加記です。
はてな

精進内容

　書き忘れてたので書き足します。
　典型知識がとにかくない。実装がやばい！って感じだったので、解説ACもありで埋めてました

  • ABCのC-F埋め

　ABCはとにかく典型問題が多いので埋めとくべきときいたので解説ACもありでがんばりました
　埋まりきってないです。

  • ARC青diff埋め、黄diff埋め

　これ割と楽しいです。昔の問題は今だと典型も多いのでかなり勉強になります。埋まりきってないです。

  • EDPC埋め、TDPC埋め

　これかなりDPの典型を知るのにいいと思います。
　TDPCのT放置してます。

  • えでゅふぉ埋め

　40以降からいいかんじらしいので40からうめてて今45おわりました。
　Contest Maniaとかのサイト使うとかなり捗ります。

  • 蟻本の類題記事

　今中級をやってます。反転？あたりまでやりました。
qiita.com

　飽き性なので、何かに飽きたら別の埋めにうつったり、くじかつに出てみたり、えすえふさんのバチャに出てみたりとかしていました。鬼精進！みたいなのはむいてなくて、精進したい気分の時にいろいろ手出してみる感じでやっています。

まとめ

　黄色になれてめちゃくちゃ嬉しいです。
　黄色維持できるよう頑張りたいです！
　ここまで読んでいただきありがとうございました。

ICPC模擬国内&国内予選参加記

はじめに

stoq(@stoq_)くんとhanyu(@hanyu_kyopro)くんとチームharaharaを組んでICPCの模擬国内と国内予選に参加してきたので、参加記を描こうと思います。

目次

模擬国内

前日早起きだったし余裕だろって寝て起きたら13:41でびびる。


なんかstoqくんもご飯食べ損ねてた。

ごはんぬき模擬国内開始。
A:やった
B:はにゅくんがやってくれた
C:stoqくんがやってくれた（すごい）

D:構文解析だからやります！をして嘘解法2ペナだしたりする戦犯をする。（(())())))みたいなのを落とす。）
左側に対応できるカッコの範囲を持った状態で左からみてく。
左が足りなくなったらたす。
最後まで見ても右側がたりなかったらたす。
これでO(N)でできるんだけど、左右独立で書いたり、にぶたんしたりするともっとあっさりかけたなってなってました。

E:はにゅくんがやってくれた（すごい）

Dをペナらせてる間にCE通っててすげーってなってた。
模擬国内は5完27位で通過ライン！

国内予選

ゼミで早起きしたあと昼寝を試みるも寝られず、寝不足のまま国内予選へ。
チームメイト二人もなんか眠そうにしてた。

開始した瞬間、ページがうまく表示されなくて焦る。
慌ててコーチに連絡してたけど、連絡つかず>

ので、定期的にリロードしてがんばった。

A:つながらない時間があったのでめっちゃharaharaしながら解いた。
順位表的に他チームも見れてなかった時間がありそうで安心する。
B:はにゅくんがやってくれた
C:stoqくんがやってくれた

D:構文解析だからやります！をして、ぺなださずになんとか通す。
n=16で、n!だと間に合わないので、bitDPにあたりをつける。
→状態を0,1でおきたい
→式が値xになるかを判定したい時、xより順序が早いか遅いか(1,0)の情報があればいい
→(x,xより早い文字の集合)ごとに計算して、O(n*2^n*(|S|+|T|))でとける

これ構文解析じゃないパートが結構面白かった。
D通した時点でharahara10位に躍り出る（やばい）

ここからは落ち着いて好きな問題考えるフェーズだった。

E:閉路がある場合がわからないをする
F:はにゅくんががんばってた
G:フローぽいけど何？ってなる
H:stoqくんががんばってた

国内予選は4完28位で通過！

おわりに

なんとか国内予選は突破できたので横浜行くの楽しみにしてます。
英文読解とか色々練習しておきたいです！
頑張りたいです。

HUPC & ACPC参加記

はじめに

HUPCとACPCに参加してきたので参加記をかこうとおもいます。
もともとはHUPCのday3にだけ参加するつもりだったのに気づいたら全日参加してた（なんで？）

目次

HUPC day1

ゼミ前に早起きしたら、3時間セットだったので出たくなっちゃってチームメイトを当日9時とかに募集する。

ぶちさん(@betit0919)とすぎやんさん(@yuji9511_compro)がつれたので、チームAoi3renseiを組んで参加しました！

Aoi3renseiっていってるけどすぎやんさん黄色だったような。。。？

最初A担当してすぐとけたあと、Eにいって嘘解法をなげる（戦犯か？）

↓
チームメイトがBCDやってくれる
↓
E実装するもWAで、チームメイトに確かめてもらうも、「これはあってる」x2をいただいて「3人あってるのでヨシ！」で進むもWAとれず
↓
あとになってたこあしとたこあしつながってるみたいなコーナーケースに気づいて、チームメイトにたすけてする
↓
ぶちさんが最小被覆集合の記事を見つけてきてくれる（天才か？）
stackoverflow.com
↓
実装を任されるも間に合わず。。。くやしい
てか復元部分いらないのに復元部分をバグらせていました（あほ）

ふりかえるとわりと戦犯してないか？ユルシテ。。。
ICPCチーム以外の人と組んだの初めてだったのでかなり新鮮でたのしかった。

HUPC day2

day1でたらたのしくなっちゃったので、明日も出ちゃおっかなってなる。
今度は前日にぷちくん(@petite_prog)とstoqくん(@stoq_)を誘って参戦！

haraharaよりもmomohara度が高いチーム名が誕生してしまう

J3回目投げた時に、ジャッジが詰まってたのか更新した時にWAでてきて、チームメイトに「何が間違ってると思う？」って相談してたら、
チームメイト「あれ？順位表見たらteam_momohara、J ACしてるよ！？」
ももはら「え？？？？」
ってなってて笑ってました。

J解けたの結構えらくない？あとHがわりといい感じの方針だったらしくて、誤読なかったらもっと詰められたかな？ってなってました。
後半はHの実装したり、ぷちくんといっしょにstoqくんを熱烈応援してた。

HUPC day3

前々から約束してたはにゅくん（@hanyu_kyopro）、かいとくん（@tran0826）と参戦！
チーム戦オンサイトでもやりたいねってことではにゅくんにきてもらったし、せっかくなのでharahara+tran0826でおひるごはんたべた。


チームharahara初めての顔合わせで緊張しました。

コンテストではAMを担当しました。
途中ラーメンに囲まれててついツイートしちゃった（おこられた）

なんか最後らへんははにゅくんといっしょにかいとくんを熱烈応援してた。

ACPC day1

HUPCに参加したら、harahara(momohara, hanyu, stoq)でも参加したくなってきちゃってACPCに誘う。
A~Cを先に割り振っておくとお得なことを覚えたので、A担当したいです！っていいだす。
問題開けてみたらCがグラフらしかったので、Cも担当になった。
ACを通して、Gを無限にばぐらせておわった。

A:やる
C:双方向の辺と単方向の辺が混ざる場合のへんの必要数を勘違いしてサンプルに困惑→丁寧に書いてなおす。
G:三分探索だと信じてたけど嘘だったらしくて反省（ごめん）

3人で1問ずつバグらせてたので、伸び代はありそうだよな〜って思ってた。

ACPC day2

ひきつづきharaharaで参戦！
この日もA担当したいです！っていいだす（この日現在レートは一番上だったぽい？highestまけてるから許されろ）

Aを通す
↓
EながめてたらなんかDPだけどわかんないになってる間にチームメイトがBを通す。
チームメイトが解けたらしいので渡す。
↓
後ろ眺めてたらJがクエリの平方分割で解けそうだったので考察まとめたりしてる間にチームメイトがCEFを通す（チームメイトえらくない？？？）
無事Jを通す
↓
stoqくんがI頑張ってる間にGがなんか解けそうな見た目してるので考える
↓
「G、区間に辺を貼るテクでとけそう」ってはにゅくんにいったら、はにゅくんも同じはてなブログ開いててわらいました
Lorentさんありがとうございます！！！
互いの考察はなしてたら、気にしてたケースが誤読でありえないことを教えてもらい、ももはらの考察の方が軽そうだったので実装
Gを通す

9位？？？？え？？？？？？

haraharaがつよすぎてチームメイトと一緒にちょっと困惑してた
あと、Twitterでいろんな人につよいって褒めてもらえて嬉しかった

ACPC day3

締め切りがずれたので結局参加できた。てんぷらさん（@tempura_cpp）にチーム組んでもらった（まじ？）

ABFを担当しました。
A：誤読？で時間を使った。かす。
B：すぐできた
F：すぐ思いつきはしたけど、O(N)だとおもってあれ？ってなってたらちゃんとO(N^2)だった。（nPrはいつでも前計算できる大きさと考えてた）
てんぷらさんがめちゃくちゃDをばぐらせてて面白かった。

Hわからなすぎてチームメイトを熱烈応援していました。


まとめ

チーム戦いろんな人と走るの楽しい！！！！ってなったし、チームharaharaで9位とれたのも超嬉しい！！！！！！！
チーム戦いいねになりました。

1年間の精進記録

はじめに

　こんばんは、ももはらです。
　AtCoderをはじめてそろそろ一年が経つので、精進記録を書きたいと思います。
　今こんな感じのパフォーマンス遷移をしていて、水停滞から青パフォ安定（？）までに精進したことを、具体的に書きたいと思います。（青なりました記事はほぼ日記だったので）

　私が水色で停滞していた理由としては、以下のことが考えられます。

  • アルゴリズムを覚えても、使い方がわかっていないため、コンテストででるのが一回目だとうまく使えない
  • 知識が偏っていて、にぶたん、桁DPなどの典型がかけない

　そのため、どうやってアルゴリズムについて勉強して、使えるようにするか、を主に書きたいと思います。

目次

過去問うめ

　ABCのCとDを並行して進めており、Cは埋め終わりましたがDはまだ19問残っています。
　基本的には1時間位考えてもわからない問題は解説ACですすめています。解説ACするときの注意すべき点は、どうやって考えたらその解法にたどりつくのかを意識することであると思います。同じような問題がでたときに、たどり着けなくては意味がありません。
わかりやすい目安としては制約条件があります。

  • n<=1e18：O(1)、O(logn)の解法などが当てはまります。数学か、二分探索などを考えてみましょう。
  • n<=1e12：O(1)、O(√ｎ)の解法などが当てはまります。約数などを使ってできないか考えてみましょう。
  • n<=1e6：O(n)でも間に合います。文字列とか数列だったら前から見てくのとかを考えてみましょう。
  • n<=1e5：ソートO(nlogn)は許されそうです。ソートして前からうまいことできないか考えてみましょう。また、n回二分探索をしたりもできるので、色々できそうです。
  • n<=1e5、a<=1e18：決め打ち二分探索O(n*log(a))などによくある制約です。aの値を決め打ちしてうまくできないか考えてみましょう。
  • n<=1e3：ここらへんになると色々あります。ABCのEFだとDPの確率高そうです。
  • n<=40：半分全列挙O(2^n/2)ができます。20個ずつに分けて全列挙したものを保存して、それについて二分探索したりできます。
  • n<=18：bit全探索O(2^n*n)が間に合います。一人につき(0,1)で考えられないか考えてみましょう。
  • n<=8：全探索O(n!)が間に合います。迷わず全探索です。お供にnext_permutationの使い方を覚えとくと便利です。


　こうやって見てくと、天才じゃなくても解法が思いつけそうな気がしてきませんか？
　こういうアルゴリズムがあるんだってなったときは、そのアルゴリズムが「どのくらいの計算量なのか」＋「どんな制約ででやすいのか」を一緒に覚えてあげるようにしましょう。
　また、一つ新しいアルゴリズムを覚えたときは、解説ACするだけじゃなくて類題も解くようにするとベストだと思います。

コンテストの復習

　最近はAtCoderだけではなくて、Codeforces、yukicoderさんのコンテストに参加するようにしています。そして、精進のためにはコンテストに参加するだけじゃなくて、必ず復習時間を設けることが大事だと思っています。
　コンテスト中に問題文を読んで考えてたけどわからなかった問題は、必ず数日以内に自力ACもしくは解説ACするようにしています。この「あと一問」が解けるようになれば着実にパフォーマンスは伸びるので、あと一問を必ずACするようにするのは大事だと思います。

アルゴリズムの勉強

　水色になってから蟻本を購入し、本格的に勉強し始めました。
　今は下記サイトを参考に進めています。
qiita.com

　区間スケジューリングや、個数制限なしナップザック問題など、最近見たことのある問題もあると思います。
　また、上記のサイトでは、結構レベル上めの問題も紹介されていて、面白いです。（普通に解けないのが結構あります）
　おそらく、蟻本をただ読んだだけでは、具体的にどういう問題に使えるんだろうというところが曖昧で、実際に問題を見ても解法が浮かばない恐れがあります。なので、必ず新しいアルゴリズムを覚えたときは類題をときましょう。（圧力）

まとめ

　上でつらつらとやったことを書いたんですが、大事だと思ったことをまとめると以下2つです。

  • 新しく知ったアルゴリズムは「どんな計算量か」＋「どんな制約で使えるか」も覚える
  • 解説ACした問題は必ず類題をとく

アルゴリズムを覚えるのと、使えるのは違います。覚えただけで満足しないようにしましょう。

おわりに

　ここまで読んでいただきありがとうございました。
　青になった記事よりも精進内容をわかりやすく書こうと頑張りましたが、どうなんでしょう。（自分でわからなくなってきました）
　記述に間違いがあったらTwitterでこっそり教えて下さい。
　よい精進生活を。

AtCoderで青になるまでにやったこと

はじめに

こんばんは、ももはらです。

今回、ABC157でAtCoder青になりました。

なので、初めての色変記事を書きたいと思います。

といっても、日記的なものなので、役立つ記事が読みたい方はブラウザバックしましょう。

f:id:momoharahara:20200301233559p:plain

目次

 

茶になるまで

「kakiraさんになにか面白いもの進められたぞ～？」でAtCoderをはじめてみたものの、最初はよくわかっていませんでした。

初回でAGCにでて0完したりを2回繰り返して、3回目に参加したABCで3完し、はじめてコンテスト中ACを達成しました。このときはCをけんちょんさんのブログで見たばかりの累積和で通せて嬉しかったです。

緑になるまで

C++を触ったことはあったものの知ってるのはvectorまでで、mapやsetなどのSTLを全く知りませんでした。なので、まずはSTLでなにができるのかを調べてたりしました。この頃はコンテストのたびにC++リファレンスとにらめっこしてました。

水になるまで

このころはとりあえず過去問を解いたり、コンテストに出て、とけない問題は教えてもらったりしてました。特にグラフ問題まわりのアルゴリズム（ダイクストラとかワーシャルフロイドとか）すごいとなりはじめました。

あと、高専出身なのもあり高校数学できないのが悔しかったので、組み合わせ周りを勉強したりしてました。重複組み合わせを理解したときは天才になった気分になれました。まだまだ抜けがありそうなのでまた勉強したいです。

青になるまで

勉強したこと

アルゴリズムの勉強ちゃんとするか～と思って蟻本を買ったりしました。けんちょんさんのブログを見ながらちまちますすめていて、いま初級編のおわりあたりにいます。おかげで、最近だと区間スケジューリング問題や個数制限なしナップザック問題が解けました。やはり後出しじゃなく勉強するのはいいなとなりました。

過去問ときも並行してすすめて、特に、「グラフ楽しくないですか？」になって集中的にときました。最近のお気に入りは拡張ダイクストラです。頂点を増やして典型問題に落としこむという発想、めちゃくちゃ面白いです。解けても解けなくてもこの問題たのしー！となります。

また、最近では「制約から考える」ということを重視するようになりました。制約と照らし合わせて考えることで、TLEになる解法を無駄実装するのが減り、制約から解法が思いつくことが増えました。

DPやにぶたんなど、いままで知っていても思いつけなかったアルゴリズムを、制約から考えることで徐々に思いつくようになっていて、ここらへんは、まだまだ伸びしろがあると思っています。

モチベになったこと

学生最強コンのイベント参加枠に入れてたので、水色になってすぐに参加してみました。

この日、ぼっち回避のためにTwitterをつくりました。

懇親会では、黄コーダーや青コーダーにびくびくしながら、お話をさせてもらいました！（いやほぼ同じ大学の人たちについていってましたが）

オンサイトイベントの空気を感じ、Twitterで競プロアカウントをつくったのは、かなりのモチベになりました。

おわりに

ABC157では、Cの実装が重めで、これひえるか～って思ったらDがグラフ問題でテンションブチ上がり最後まで頑張れました。なので、好きな問題とかを持っとくと、コンテスト中のモチベを保つのにいいかもしれません。

また、グラフ以外にももっといろんなアルゴリズムを勉強して、好きな分野を増やしていきたいです。

ここまで読んでいただきありがとうございました。