新卒1年目の振り返り

概要

新卒のソフトウェアエンジニアとして就職して1年が経過するのでこれまでを振り返る。

 

結論

  • 入社後しばらく抱いていた「満足に仕事ができないんじゃないか」という不安の多くは解消され、日々の業務をこなす程度ならそこまで難しくはないと感じた
  • チーム向けのツールを勝手に作っていたら正式な業務としてチームの運用ツールを好きな言語で書けることになるなど、少し背伸びした成功体験も得られた
  • とはいえまだまだできないことは大量にあり、終わりのない道を歩き始めたばかり(ヒカルの碁

 

筆者の背景

  • 大学入学後に競プロからプログラミングに入門して、数理論理学に対する興味から型システムに惹かれて大学院で専攻変更
  • ハッカソンインターン経験なし
 

振り返り詳細

この1年をいくつかのトピックに分けて振り返る。試験的に、今回は意識して散文チックにしてみたい。そのため話題があちらこちらへと飛び火する。
 

技術研修はありがたい

配属される前に数ヶ月の技術研修があった。これがかなり良かった気がする。内容は社内外の技術を使って、フロントエンド、バックエンド、DBを使ったWebアプリケーションを作成するのが主なものだった。この研修を受ける前の私と言えば、フロントエンドとバックエンドの違いを自分の言葉で全く言語化できず、CI/CDのやり方もてんで知らず、REST APIも多分わからない、つまりはど素人だったわけだけど、この一気通貫で概要をさらう研修のおかげでWeb開発の概観に対する直観を得ることができ、それまでWeb開発に対して漠然と抱えていたコンプレックスのようなものが多少解消されたように感じた。多くのプロダクトは、それ自体が複数のコンポーネントから成り立っており、このコンポーネントの区切り方は大体共通認識があること、だからこそそれぞれのコンポーネント間のやり取りには汎用的なAPIが既に提供されており、我々はその使い方を都度調べながら繋ぎ合わせることでシステムを組み上げることができるという認識を得た。そして、このコンポーネントへの分解の仕方、各コンポーネントの一般的な組み立て方、それらの間の連携の仕方は独創性というよりは覚えゲーなところ(特に初期段階)があり、よく言われる「(ソフトウェア)エンジニアは覚えることが多くて大変」という主張の、覚える対象が何を指しているのかということについて自分なりの答え合わせができた。Web開発に対して感じていたハードルが下がったことで何か作ってみたいという気になり、次のようなものを作成した。
  • 漫画更新bot
    • DBに登録されたweb漫画の最新話が更新されたかをチェックしに行って、更新があった場合はDiscordに通知するプログラム
    • cronで毎日1回実行している
    • 運用中に漫画が掲載される url と html の構造が変わって処理が失敗したことがあり、そういったイレギュラーに気づけるようにロギングや通知設定を見直した。作り捨てではなく使い続けるからこそ見つかる改善点などに気づけて楽しかった
  • アークナイツの便利ツール
    • アークナイツという私の生きがいとなるゲームがある。このゲームに関するREST APIサーバと、これUIを通して利用できるツールを作った
    • html とcss はほとんどわからないけど ChatGPT に聞いたらなんとかなったので、本当にいい時代に生まれてきたと感じた
 

配属後の仕事の話

技術研修の後は配属先でOJTが始まった。配属されたチームの扱ってるコンポーネントは多く、必要になる技術領域も馴染みがなくて最初はキャッチアップにかなり苦労した。自分がわからないことを言語化・構造化してはそれをメンバーに尋ねるというサイクルをよく回したが、チームの方は嫌な顔せず毎回丁寧に回答してくれたのでありがたかった。様々なタスクに入りながら過ごしてしばらくしたあと、業務には、似たようなタスクが不定期にやってくることを実感するようになった。学生の頃の授業や部活の練習のように、習熟を目的として集中的に反復するのではなく、タスクは仕事上必要になったタイミングで発生し、それらのほとんどは似たもの同士に分類できる(その分類の種類は仕事による)。従って、一度経験したタスクを次の似たようなタスクに活かすためのメカニズムを外部に任せることはできない。ここで役に立ったのが自分のためのメモあるいはドキュメントだった。世間ではメモの大切さが謳われ、メモの取り方の本が出たりもしているが、自分はそれを大したことだとは思わず今まで一度もメモらしいメモをとったことがなかった。やってみると、メモは仕事以外にも色々役に立ちそうなことがわかってきた。たとえばTwitterのTLにはいつも有益だったり面白そうな情報が出回っているが、それをいつでもその時に摂取できるわけではない。一旦どこかにストックしておいて、後から適切なクエリによってそれを引っ張り出せるようになっているとありがたい。このクエリがディレクトリ構造におけるファイルパスのようなものだと管理が破綻するので、ではタグでやるのはどうかということで今はObsidianを試している。ただしやっぱり「いつ」「何を」メモから引っ張り出すかは本当に難しいので、この部分はAIがいつかやってくれるといいなと思う。一人一人の人生経験だけをDBのデータとして使い適切なタイミングで適切な情報を思い出させてくれる秘書みたいなAIができたらいいな。てか作ってみたい。業務効率化アプリとしての可能性を感じています。
 

働いてみての気づき色々

ソフトウェアエンジニアとしてチームで働くようになって、いくつか気づいたことを記す。
 
まずはスクラム開発?について。チームではスクラム開発を採用しているが、自分にはこれが初めてのスクラム開発(というか初めてのチーム開発)だった。ソフトウェアエンジニアリングに限らず、チームで何かを達成する際の問題解決フレームワークとして色々優れているなというのが全般的な感想で、たとえば中高生の学園祭の準備とか集団で何かを決めるときにこのやり方を知っていたらもっと上手くできたかもしれないと思った。スクラムは大雑把にいうと、こいつが関心のある対象のうち最小のものであるタスクを、チームの誰もが不確実性が低い状態で遂行可能にし続けることが目的で、そのためにリファインメントで曖昧な課題を噛み砕いて具体的な受け入れ条件の定まったアイテム(タスクの集合からなる)にしたり、日々のデイリーなどの振り返りで現状の進捗や肌感を共有しながらタスクの再定義や分配を行なっている印象を持った。ただこれができるかどうかはチームの抱えている課題の難易度と、チームメンバーの能力に依存するので、上述のような理想状態でいられることはほとんどないと思う。たとえばリファインメント対象が難しいものであれば、それを噛み砕ける一部の優秀なメンバーへの負担が大きくなってしまうし、チームメンバーのスキルがスクラムの要求水準に満たなければ、タスクを見積られた時間内に終わらせることは難しくなり、それへの適応として当人はプランニングの時点での稼働可能時間を少なく見積もるようになったり、デイリーでのタスクの再振分が頻発することで、スクラムが期待するようなアプローチにイレギュラーが発生する。ただこのような問題はおそらくありふれているので、妥当な解決策があるかもしれない。スクラムに関する有名な本とかもいくつかある気がするので、いつか読んでみたいかも。
 
続いてこれは社会的責任を負った企業のエンジニアなら普通なのかもしれないが、システムの安全性にすごく気を遣っていると感じた。具体的には、何をするにしてもその正常性の確認のために監視設定を入れたり、様々な観点から結合テストを行なったり、リリースがうまくいかなかった場合の手順やその遂行可能性なども厳しくチェックしていた。一方でこれらが全てプロダクトの安全性に寄与しているのか、しているとしてそれはどの程度なのかはまだ正直よくわからない。ただ静的検証の技術はまだまだ一般的ではない(そもそも目的の性質を証明する方法は現時点でも未解明かもしれない)ので泥臭く良いテストを考えるしかなさそう。
 

とある挫折、そしてRustという救済の光

社会人になってから経験したちょっとした挫折は、自分が技術的に興味のあることがほとんど共感されないことだった。最初に述べた通り自分は競プロからCSの門戸を叩いて、そこから同じく興味のあった数理論理学からプログラミング言語理論と型システムの分野にいきなりジャンプした珍しいタイプの人間なので、視野やスキルセットがかなり偏っている。好きな分野を答えてもそこから話を広げられず申し訳ない思いをしたことも少なからずあった。自分は何らかの性質を演繹によって保証することに興味があり、その保証された「安心な領域」を社会全体に広げていくことで世の中が生きやすくなったらいいと考えている。そのための手段として世界を記述するプログラミング言語に注目していて、OCamlHaskellが好きだ。一方でプログラミング言語は非常に強い正の外部性を持つ。つまり、その言語がもたらす恩恵は、その言語自体の本質的な魅力だけでなく、それを使っている人の数、周辺ツールやエコシステムなどに大きく影響を受ける。一般的に広く使われている言語に比べるとOCamlHaskellにはそのような強みは薄く、この外部性の恩恵に与れないまま、業務領域へのキャッチアップと並行してこれらの言語を使ってプログラムを書き続けることは、自分の能力ではかなり限界があると感じていた。
 
あるときRustに出会った。正確に言えばRust自体はずっと前から認知していたが、何かのきっかけでRustに入門した。

 

まず、ヴァリアント型やパターン(もちろんワイルドカードパターンもある)マッチ構文、式指向なところがプリミティブとして備わっていることがすごく好き。こういった機能がプリミティブとして提供されているなら構文自体もその旨みを引き出そうとした設計になっていて一貫性があって扱いやすいという信念がある。逆にそうでなく、既存の機能をこう組み合わせればこういうこと"も"できるよといった言語では、まずそのテクニックを知っていないとできないし、それがデザイン(?)パターンとして認知されるまで時間がかかるし、なっても認知コストがかかるので、前者の言語との間にはやはり深い深い溝がある。Haskellなどと比べると抽象性はやや劣るけど、逆に、Haskellだと抽象性が高すぎて魔法にしか見えないところをRustは愚直にやっているところがあったりして、Rustのレイヤは一つ下なんじゃないかなという直観がある。だからこそOSや組み込みシステムなどのレイヤでも人気があるのだろうし自分も低レイヤには興味があるのであわよくばRustに連れて行ってほしい。あとRustの所有権やlifetimeの概念が自分にとってはすごくよかった。何でよかったのかというと、自分が修士の時に研究していたテーマと類似点があったから。自分はある特定の言語の型システムの設計とその型安全性の証明をしていたのだが、この体系で安全な型をつけるには変数が存在できるスコープを追跡する必要があり、型にもそのスコープが現れた。自分の体系はずっとひどくお粗末な気がしていたし、プログラマがスコープを書かないといけない言語なんか実用的じゃないんじゃないと思っていたけど、それをRustという人気言語が反証してくれた(Rustにはlifetimeパラメータが型に現れることがある)のが嬉しかった。もちろん自分の研究していた体系は素人のtoy programming languageなのでRustの足元にも及ばないし、そもそも型安全性の証明ができた(と自分が思った)のは修論執筆直前で学会の査読に通ったというわけでもないので客観的な事実としてはただの思い込みなんだけど、Rustに親近感と愛着を覚えるにはそれで十分だった。
 
Rustはその難しいという評判と打って変わって、周辺ツールやドキュメントは恐ろしく丁寧なところも好きだ。前述したようにプログラミング言語が普及するには正の外部性をうまく使うことが大事だ。開発に便利なツールチェインや丁寧なドキュメントは利用者を増やすことに大きく貢献する。自分もRust自身やRustを使った何かについて発信することで、いろんな人が心地よくRustで開発できるような環境づくりに少しでも貢献できたらと思う。
 
また、業務とRustの関わりだと、チーム内のとあるオペレーションを自動化するツールをRustで作って共有した。このおかげかはわからないが、今度は業務時間としてチームとして進める別のオペレーションを補助するツールをRustで作れることになった。今はどちらのツールも既に作業に組み込まれていて、自分にしてはすごくいい体験をさせてもらえてありがたかった。
 

来年度やりたいこと

今年度の振り返りとしてはこれくらいで、次は来年度にやりたいことを簡単に書き出す。
まず仕事がもっとできるようになりたい。チームのプロダクトやそれが依拠している技術に対する理解はまだまだ不足している部分があるので、引き続きできることを増やしていきたい。仕事はできないよりできた方が楽しいからね。一方で、自分のやりたいことと仕事の内容が完全に一致しているわけじゃないので、ちゃんと自分の興味に費やす時間も守っていきたい。あと友達を増やしたい。基本的に超インドア人間で仕事もリモートワークなのでプライベートで人とコミュニケーションを取る機会が非常に少ない。ただ友達を増やそうとして友達を作るのは難しいし自分にも向いていないので、自分が好きなコンテンツに関するコミュニケーションに対してもっと積極的に足を踏み入れていくところから始めたい。
 
終わりです。
 

大学院から情報科学系分野を専攻にした人間のエンジニア新卒就活雑感

tl;dr

私のこと

就活結果

  • 受けた企業数:5社
  • 内定:3社
  • 途中辞退:1社
  • コーディングテスト落ち:1社

 

はじめに

ここからはもう少し詳しく就活の体験記を書きます。私は社会科学系の学部在籍時に数理論理学と競プロにハマって,特に型理論に関して詳しくなりたいと思って他大学他分野に院進した人間です。冒頭の私の状態からソフトウェアエンジニアとしての就職は難しいかなと思っていたのですが,なんとかなりました(内定を1つ以上得られた)。これはその備忘録です。

 

就活期間

M1の夏頃にインターンのことを考え始めました。当時は,ただでさえ修士から新しい分野で研究を始めるという遅いスタートを切っているので,これ以上研究以外のことに時間を割きたくないという気持ちと,そうはいっても一つもインターンに行かないで本選考は大丈夫なのかという不安のジレンマを抱えていました。結果,特別魅力的だった1社にのみ応募してダメだったら割り切ることにしました。そして落ちました。

11月頃から各企業が本選考の受付を開始していたと思います。私も思い出したように就活を再開しました。いくつかの企業にエントリーし,初めて内定が出たのが1月末,結局他の企業の結果も聞くために3月末まで就活を続けました。

 

企業選びの基準

次の2つの基準で選考に参加する企業を選びました。

  • 型システムおよび静的型付き言語が好きなので,そういった技術との関わりが多いこと
  • 提供している商品やサービスが社会の役に立っていると感じられる,あるいは好きになれること

自分のモチベーションを保ち続けるために最も重要な2つのことがこれだと思いました。

私がそもそも専攻を変えてまで修士に来た理由は数理論理学と型システムに衝撃を受けて惚れ込んだからなので,そういった技術と関連があるところで仕事ができるかどうかは死活問題でした。ゆくゆくは色々な技術に触れていくことになると思いますが,最初の仕事としては自分のこだわりが特別強いところから始めた方がよいとの判断からです。あとは単純に自分の知識が多少活かせるというのもあります。またそういった企業の探し方として信頼していたのが,自分と同様の分野の人がいる企業を探すという方法でした。一口にエンジニアと言ってもその人たちの選好は様々だと思います。しかし同じ分野の人たちならばある種のこだわりや価値観を一部共有でき,それは企業選びの際に参考になります。実際ありがたいことに選考の途中で私と同じ分野出身の方とお話する機会を設けていただき,それが後悔のない意思決定につながったと感じています。

また,私自身の志向として公共の利益に貢献できると嬉しいというのがあって,自分の関わっている製品が,できるだけ特定の集団によらない様々な人の役に立っていたり,あるいは特定の集団であっても,理不尽な不利益(定義は非常に難しいですが)を被っている人たちの役に立っていたりするんだと自信を持って言えるのであれば,モチベーションは自然と沸き続けると予想しました。

基準はこの2つ以外にももちろんあったと思います。たとえば私は持病があって働く環境に関するこだわりが普通より多少強く,そういった点なども考慮しました。

 

競プロは役に立ったか

立ちました。どの企業の選考にもコーディングテストがありましたが,AtCoderのABCとかの問題とだいぶ傾向が似ていて,ほとんどの問題は苦労することなく解くことができました。コーディングテストで落ちた1社については,問題の内容がWeb関連に大きく寄っていたのが原因です。

 

就活,なんか思ってたのと違った

就活をする前とした後で印象が大きく変わりました。就活する前は,私は圧倒的な高みにいる面接官から一方的に評価を下される立場にあり,面接官は終始高圧的な態度でこちらと相対するものだと思っていました。しかし実際に面接を受けてみると,面接官は表情が豊かで相槌を頻繁に打ってくれる方が多く,コミュニケーションは非常に楽しいものでした。面接官の方からは,面接はお互いが対等な立場にあり,ミスマッチを防ぐために自社のことを誠実に伝えようという意図が感じられましたし,私も自身のことを誠実に話して,それで落ちたらしょうがないと思うようになりました。

就活の面接は自己分析と強みのアピールをしないといけないといった認識があったのですが,事前に話すことを考えたりはしませんでした。基本的にはどの選考でも就活(企業選び)の軸が重要視されている気がして,そこから話が膨らんでいくので,その意思決定基準さえしっかりしていれば特に会話に困ることはありませんでした。あとは大学入学以降のできごと(競プロにハマったり修士に行くことにしたり)を振り返ってその意思決定に至る経緯やその際考慮したことなどを振り返るといった,いわゆる自分語りを促されることが多くありました。私は自分語りは嫌いではないですし,それが許される機会は貴重ですので気持ちよく喋りました。前述のように面接官はミスマッチを防ぐために私が自社でうまくやっていけそうな人かを知る必要があり,そのために色々と人となりを話して欲しかったのだと思います。したがって私も相手が知りたそうな情報を意識しながら適切だと思う切り口で自分語りをした記憶があります。

あとはこのご時世だからか,選考はすべて私服のオンライン面接で行われました。気楽に臨めてよかったです。

面接を担当してくださったほとんどすべての方とのコミュニケーションが楽しく,大変感謝しています。特に就活の最初期は尋常ではない不安と焦りで正気ではいられなかったのですが,その時に受けたカジュアル面接を担当してくださった人事の方が常時笑顔の太陽みたいな人で,それで一気に持ち直しました。多分その人のことはこれからも忘れないと思います。

 

おわり

就活中は競プロで繋がって一足先に社会人になったFF競プロerに色々と相談に乗っていただきました。ありがとうございました。私にも何か聞きたいことがあればお答えしたいです。

内定先には明らかに即戦力とはほど遠い実力で採用してもらったと思いますし,ちゃんと戦力になって恩返ししたいという気持ちが強いです。がんばります。

小野『情報科学における論理』6章解答

小野『情報科学における論理』に収録されている問への私の解答を、練習を兼ねてここに記載します。解答は順次追加するかもしれません。

 

6章 自然演繹の体系

問6.4

https://drive.google.com/file/d/1grZA1mAm8sR3DCWwYFM31bp4MDT406ay/view?usp=sharing

 

問6.5

https://drive.google.com/file/d/1ZsiXQfY0jt1xHh-NhTjIsV3iZ7JXlX97/view?usp=sharing

AtCoderで青色になったので今までを振り返る

この記事には自分語りが多分に含まれます。苦手な方は十分にご注意ください。

この記事について

  2020 年 1 月 19 日の AtCoder Beginner Contest 152 で青色になることができました。初参加の 2018 年 10 月 27 日から 15 ヶ月ほどが経ち、丁度いい機会でもあるので、変色記事として自分と AtCoder を始めとする競技プログラミングコンテンツの関わりについて書き留めておこうと思います。変色する機会でもなければ書かないと思いますし、次の(上方への)変色機会が果たして来るのかどうかは怪しいので。
  内容は雑多に自身の背景や精進方法等を時系列順に記していくつもりですが、ほぼ自分語り主体の散文です。よほどの物好きでない限り、この記事は退屈に感じるでしょう。AtCoder の練習方針やその成果を中心とした内容は「緑色になるまで」から始まりますので必要であればそこからお読みください。

f:id:ose20:20200120032254p:plain

大学入学まで

  高校までは地元の家から近い学校に通っていて、特筆することもない学生生活を送っていました。ただ公立高校にしては珍しくカリキュラムが特殊で、数3の授業も受けられる文系のような課程を選択できたので、私はそれを選びました。今思い返せば、競プロの問題にも極限や期待値を考えるような問題があるので、当時の自分の選択にはいくらか救われている部分があると思います。
  パソコンはほとんど触ったことがありませんでした。情報の授業の時間に自分の何十倍ものスピードでタイピングをする新聞部員を見てかっこいいなと思った記憶があります。
  あと、これは私が競プロにハマったこととは多分無関係なのですが、自宅浪人という引き篭り生活をする某年間に家族以外との会話をほとんどしなかったので、大学に入ってから人との会話で言葉に詰まったりして大変でした。今はいくらか改善したと思います。

学部2年夏まで

  競プロが出てこないので飛ばします。しかしこの間にそこそこ真面目に単位を回収したことで、結果的にその後の競プロ精進の時間が確保できたように思います。専攻している学問分野を好きになれたことも私にとっては大事な財産です。あとレポートが書けなくて困ったのでタッチタイピングの練習をしました。

競技プログラミングに出逢うまで

  夏頃に、なんの前触れもなく気が触れてプログラミングに興味を持つようになりました。しかし計算機科学なんていう格調高い学問領域は疎か、パソコンにすら普段あまり触れない状態では何をしてよいのか皆目検討がつきません。Twitter で適当に情報を探しながら、progate をやってみたり、Udemy を見ながら簡単なアプリを作ってみたりしました、作ってみたりしたのですが、コンピュータやその他の情報技術について何にも知らない状態だからか、自分が理解できていないコードを書いてアプリが動いているのを見てもあまり感動しませんでした。ただ、その時見ていた Udemy の動画の講師の方が Project Euler を紹介していて、こちらはものすごく面白く感じました。他にも似たようなサイトがないか探してしていたところで偶然見つけたのが AtCoder でした。(大変お待たせしました。ここからは競プロの話になります。)

緑色になるまで

AtCoder に辿り着いたのは僥倖でしたが、まだ私には使える言語がありません。そこで友人に尋ねてみると、Python をお勧めしてくれました。入門者用の本も、もう自分には必要ないからと譲ってくれました。これで準備は整ったので、基本的な文法や入出力の仕方を調べながら、積極的にコンテストへ参加していきました。当時の ABC はまだ 4 問で、個人の感触としては、アルゴリズムやデータ構造のちょっとした知識がないと難しい問題が C で出ると 2 問しか解けないけど、D に難しい問題が置かれたときに C までの速解きに成功すると一気に伸びるというようなものだったと思います。この時期はひたすら ABC の AB 時々 C を埋めていました。

f:id:ose20:20200120045555p:plain
Python を使って緑まで

水色になるまで

  大学が春休みに入ったこともあり、アルゴリズムやデータ構造についてもう少し体系立った学習がしたいという思いから、『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』(通称:螺旋本)に手を出しました。また、この本のソースコードが C や C++ で書かれていたことや、参考にしようとした他の方のコードが C++ で書かれていることもあって、C++ をしようということになり、その前段階として結城浩先生の『C言語プログラミングレッスン』も一緒に読み進めていきました。
  この螺旋本には好きなところが 2 つあって、1 つはコンテストでは直接出題はされないけれど、アルゴリズムを理解する上で基本で大切な題材を取り扱っていることです。初等的整列の章では普段自分が何気なくしているトランプや UNO の手札の整列がアルゴリズムとして与えられたことに感動しましたし、木の章では探索順序について理解を深めることで、多くの問題について解答を容易にしてくれたように思います。もう 1 つはコンテストで直接役立つ典型アルゴリズムを幅広く学べることです。グラフ上の様々な最短距離問題や動的計画法の理解についての取っ掛かりを得たのは有意義だったと感じています。
  もう 1 つしていた練習として、~ ABC125 の水 Difficulty くらいまでの問題を周回するというものがありました。特に点数がついていないABC041 から前のセットは典型問題が多く、dp、尺取り法、いもす法、二分探索、累積和、木上の探索などの今でも即戦力で役に立つ武器があまり捻りのない形で置いてあるので、これらの問題を定期的に解き直して他の場面でも応用できるように練習しました。
  そんな練習が功を奏したのかどうかは定かではありませんが、平成最後の ABC で水色になることができました。

f:id:ose20:20200120050733p:plain
丁度 C++ に乗り換えた時期でもある

青色になるまで

 やったことは水色になるまでと基本的には変わらないんですけど、EDPC などの有志コンや Codeforces や AOJ にも少しずつ手を広げていきました。それに伴って、復習する問題を一元化して管理するためにスプレッドシートを使うようになりました。自分が挑戦した問題のうち、学びの大きかった問題をここに投入し、毎日ここから数問とり出して解き直し、問題の整理や定式化、正解となる方針を選択する理由などを話したり書いたり等の表現をすることが日課になりました(ちょうど別のある人にとっての Streak 繋ぎのように、私のやる気を維持する習慣のようになっています)
  あとは月並みではありますが、日々のコンテストでフィードバックを得ながら自分の弱点を探していき、それに対する対処(新しいアルゴリズムを覚える、特定分野の問題を多く解く、趣向の違うコンテストに出る、日々の練習で考察に使う時間を伸ばす・縮める、等)をして、またコンテストに出て...という繰り返しをしながら、精進もアドホックにしてきたように思います。今回青を達成できたコンテストも、少し前にたまたま LCA と包除原理の勉強をしていたのが幸いし、運よく時間内に解くことができました。

f:id:ose20:20200120061604p:plain
復習リスト 日に日に溜まって既に 300 問ほどあります

これから

AtCoder を始めるときに目標としていた色を達成できたので、とりあえずここで一区切りかなと思います。競プロを始めたことによっていくらか視界も広がりました。今はプログラミング言語について漠然とした興味があり、型理論やラムダ計算などの分野を勉強してみたいです。
  他には、まだ知らなかったり、ちゃんと理解していないデータ構造やアルゴリズムと仲良くなって、コンテストでうまく使えるようになりたいと思います。ここから 1 色上はまだまだ遠いですが、これからも練習を積んでできることを増やしていきたいです。
  最後になりましたが、同レート帯で競い合ったり、いろいろと御教授くださったり、様々な形で私と関わってくださった皆さん、いつもありがとうございます。私もコミュニティに恩返しができるように努めていきたいです。

Codeforces Round #584 - Dasha Code Championship -C問題 Paint the Digits 解説

codeforces.com

【本記事の想定する読者】
本問題が解けなくてつらくなっている昨日の私


【問題概要】
長さ n の数列が与えられる。以下の条件を満たすように、各要素を色1、色2のどちらかに塗ることができるか?できるなら一例を挙げよ。
・同じ色の要素の順番は入れ替えずに、色2で塗られた要素が色1で塗られた要素の右側に来るように並び替えると、数列は全体として非減少数列になる。


【制約】
テストケースの数 t について 1 ≦ t ≦ 10,000
テストケース全体を合わせて、数列の長さ n について t ≦ n ≦ 200,000


【最終的な方針】
境界 d∈[0,10)について全探索する。計算量はO(d|s|)。


【最終的な方針へ辿り着くまでの道筋と実装の注意】
 やりたいことはわかるがイマイチ実装が思いつかない。できそうでできない問題っぽい...。こういう時は、条件をできるだけ定式化してみる。

 与えられた数列のうち、色1で塗るものを a0,a1,...,alast とし、色2で塗るものをb0,b1,...,br としてみると、(色1の要素)(色2の要素)のように並べ替えた数列が非減少数列であるとは以下の条件を満たすことと同値である。i の普遍集合は整数とする。
i ∈[0,last), ai ≦ ai+1
i ∈[0,r), bi ≦ bi+1
・alast ≦ b0

 数列に出てくる数がいずれも一桁であることと、三つ目の条件に注目すると、alast ≦ d ≦ b0 なる d が[0, 10)の範囲にしかないことがわかるので、あとはこの d に対して条件を満たす数列を構築できるか判定できればよいということになる。その判定方法のイメージは下の画像のように、与えられた数列を、[0, d]の範囲の数だけを含むようなaiと[d, 10)の範囲の数だけを含むようなbiに分離することである。

f:id:ose20:20190915131516j:plain
ごちゃまぜの数列を色1で塗るものと色2で塗るものに分離するイメージ


 実装方法は提出コードを参考にしてほしいが、いろいろ罠があるので注意されたい。具体的には色2で塗る部分を小さい方から見ていき、そのあとに色1で塗る部分を小さい方から見る。その際すでに色2で塗った部分を無視しながらループを進める必要がある。


【提出コード】

#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string s; cin >> s;
        vector<int> color(n, -1);
        
        // left[i]: i 入っている一番左の位置(なければ-1)
        vector<int> left(10, -1);
        rep(i, n){
            int t=s[i]-'0';
            if(left[t]==-1) left[t]=i;
        }

        bool nothing=true;
        rep(d, 10){
            if(left[d]==-1) continue;
            // colorを初期化
            rep(i, n) color[i]=-1;

            // 色2で塗れるものから埋める
            int pre=d;
            color[left[d]]=2;
            repr(i, left[d], n){
                int t=s[i]-'0';
                if(t>=pre && t>=d){
                    color[i]=2; pre=t;
                }
            }
            // 色1で塗れるものを埋める
            pre=0;
            color[left[0]]=1;
            repr(i, left[0], n){
                int t=s[i]-'0';
                if(t>=pre && t<=d && color[i]==-1){
                    color[i]=1; pre=t;
                }
            }

            // 全て塗れていれば終わり
            bool ok=true;
            rep(i, n) if(color[i]==-1) ok=false;
            if(ok){
                rep(i, n) cout << color[i];
                cout << '\n';
                nothing=false; break;
            }
        }
        if(nothing) cout << "-\n";
    }

    return 0;
}

Submission #60594202 - Codeforces

ABC86-D Checker

atcoder.jp

【本記事の想定する読者】
本問題が解けなくてつらくなっている過去の私


【問題概要】
座標(xi,yi)をBまたはWに塗りたいという要望がN個与えられる。無限に広がる2次元グリッドを1辺の長さがKである市松模様で塗る時、最大でいくつの要望を叶えられるか。


【制約】
1 ≦ N ≦ 100,000
1 ≦ K ≦ 1,000
0 ≦ xi, yi ≦ 1,000,000,000
i ≠ j ならば (xi, yi) ≠ (xj, yj)


【最終的な方針】
2次元版のいもす法を用いる。いもす法についてはこちら
いもす法 - いもす研 (imos laboratory)
つまり、各希望(xi, yi, B(W))についてそれを叶えてくれるような市松模様を2次元の配列に記録していき、最後に配列全体を見て最大値を答えとする。


【最終的な方針へ辿り着くまでの道筋】
  市松模様の塗り方はそこまで多くなさそうなので、これを全部見るのはどうか。つまりある塗り方を1つ固定したら、その塗り方で叶えられるような希望が何個あるかわかるので、その中の最大値を答えとすればよい。

  市松模様の種類については、黒く塗られた部分の左下のグリッド(x, y)が必ず[0,2K)×[0,2K)にあり、さらにこの範囲からどの2つをとって、それを黒い部分の左下にするような市松模様にしても違う塗り方なので、{市松模様の塗り方}と{(x, y)|(x,y)∈[0,2K)×[0,2K)}に全単射が作れる。つまり、市松模様の塗り方は2K×2K通りある。

  各塗り方に対してN個すべての座標について、その塗り方で希望を叶えられるか判定する必要があるので、この方針の計算量はO(N×K2)となり、時間内に収まりそうにない。長々と書いてきたのに残念だが、この方針は却下する。

  それでは次は、固定するものを市松模様ではなく希望にしてはどうだろうか。(こういった固定するものを変えるというのは競プロに限らず典型テクニックなような気がしますが、どうなんでしょうか)つまり、各希望(xi, yi, B(W))について、(xi, yi)をB(W)に塗ることができるような市松模様の塗り方はどこだろうかと考える。先の議論を思いだすと、市松模様は[0,2K)×[0,2K)の範囲の座標を黒い部分の左下の座標として考えてよいので、例えば市松模様(i,j)(黒い部分の左下が(i,j)になるような塗り方)によって(x, y)をB(W)に塗ることができるなら2次元配列imos[i][j]の値を1増やすという操作をする 。・・・(※)

  これをすべての希望について操作するとimos[i][j]には市松模様(i,j)で叶えることのできる希望の数が格納されていることになる。あとはこの配列の値をすべて見て、一番大きい値が答えといった算段である。

  この方針でもそのまま素直にやると計算量は先ほどと同じになってうまくないが、実は(※)の操作について、例えば座標(x, y)を黒で塗れるような市松模様(を黒い部分の左下の座標で表したもの)の集合は座標上に図示すると正方形となる。正確には無限に続く市松模様なのだが、必要な部分だけ取り出すと高々数個の正方形になる。この正方形の各マスに全て+1する作業はいもす法を使うことによって高速化できる。下の画像は、K=3の時に、(4,2)が黒で塗られるような市松模様の集合を黒で塗りつぶしたものである。ピンクも含まれる。注意したいのが、この集合自体も市松模様となっているがそれはあまり関係なく、黒で塗られたグリット一つ一つが、そのグリッドを黒の部分の左下とした市松模様を表しているということである。

f:id:ose20:20190909214122j:plain
K=3のとき、斜線が引かれているグリッドを黒い部分の左下とする市松模様を塗ると(4,2)を黒く塗ることができる



  この正方形(場合によっては長方形)の部分をすべて+1する部分はいもす法を適用するだけなので、上述のリンクを参照してほしい。ここの実装方法はいろいろあろうが、一応私のやり方を記しておく。とはいえあまり上手い方法に思えないので参考にしないでほしい。また本家の解説にもある通り、(x,y)を白にしてほしいという希望と(x+k,y)を黒にしてほしいという希望は同値であり、(x,y)を黒にしてほしいという希望と(x+2K,y)を黒にしてほしいという希望は同値である(yについても同様)のであらかじめ入力を(x,y)∈[0,2K)×[0,2K)を黒にしてほしいという風に変形しておく。これを踏まえて(x,y)∈[0,2K)×[0,2K)を黒に塗ることができるような市松模様の黒い部分の左下の座標(これも[0,2K)×[0,2K))をカウントすること考えると、高々7個の正方形について見ればよいことがわかる。このときにimosの配列外を参照してしまわないように注意する必要がある。

f:id:ose20:20190909220103j:plain
(i,j)を黒く塗ることができるような市松模様の黒い部分の左下の集合のうち、これだけ見れば十分という部分



  ここまで来れば、あとはimos配列を横と縦に累積和を取った後に、すべての範囲を参照して一番大きい値を答えとして出力すればよい。


【提出コード】

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i=(l); i<(r); ++i)
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

// (x,y)∈[x-k+1, x]*[y-k+1, y]の範囲でimos[i][j]+=1と累積されるように値をセットする
void set_square(int x, int y, int k, vector<vector<int>> &imos){
    if(x<0 || y<0 || x>=3*k-1 || y>=3*k-1) return;
    imos[ max(0, x-k+1) ][ max(0, y-k+1) ] += 1;
    imos[ max(0, x-k+1) ][ min(y+1, 2*k) ] -= 1;
    imos[ min(x+1, 2*k) ][ max(0, y-k+1) ] -= 1;
    imos[ min(x+1, 2*k) ][ min(y+1, 2*k) ] += 1;
}

void set_imos(int x, int y, int k, vector<vector<int>> &imos){
    set_square(x, y, k, imos);
    set_square(x+2*k, y, k, imos);
    set_square(x+k, y-k, k, imos);
    set_square(x-k, y-k, k, imos);
    set_square(x+k, y+k, k, imos);
    set_square(x-k, y+k, k, imos);
    set_square(x, y+2*k, k, imos);
}

int main(){
    int n, k; cin >> n >> k;
    // 入力を受け取り、扱いやすいように希望を同値変形して座標を圧縮する
    // 具体的には全ての希望を、「(x,y)∈[0,2k)*[0,2k)を黒に塗りたいな」という希望に同値変形する
    vector<int> x(n), y(n);
    rep(i, 0, n){
        cin >> x[i] >> y[i];
        char c; cin >> c;
        if(c=='W') x[i] += k;
        x[i]%=2*k; y[i]%=2*k;
    }

    // 市松模様は[0,2k)*[0,2k)のどこを黒い部分の左下にするかという情報で一意に定まる(全単射)ので、そのように表す
    // imos[i][j] := (i,j)が黒い部分の左下になるような市松模様を塗った時に叶えられる希望の数
    vector<vector<int>> imos(2*k+5, vector<int>(2*k+5, 0));
    rep(i, 0, n){
        // (x[i],y[i])を黒に塗れるような市松模様(X, Y)について、最後に累積した時に imos[X][Y]+=1 になるように重みを加算する
        set_imos(x[i], y[i], k, imos);
    }

    // 左→右へ累積
    rep(i, 0, 2*k) rep(j, 1, 2*k) imos[i][j] += imos[i][j-1];
    // (問題文の画像で)下→上へ累積
    rep(j, 0, 2*k) rep(i, 1, 2*k) imos[i][j] += imos[i-1][j];

    // 最大値の検索
    int ans=0;
    rep(i, 0, 2*k) rep(j, 0, 2*k) chmax(ans, imos[i][j]);

    cout << ans << '\n';
    return 0;
}

atcoder.jp