C問題復習～AtCoder Beginner Contest 参戦録 #3

はじめに

社内外の優秀なエンジニア達から「技術トークが多少わかる採用担当」として信頼を得ることを目指して、AtCoder Beginner Contest（通称ABC）へ参加している。

経緯は記事 エンジニアから信頼される人事を目指して～AtCoder Beginner Contest 参戦録 #1 - Qiita に綴った。

弊社フロントエンドで使われているJavaScriptを使って5回参加したところ、全てでA, B問題までという結果に終わった。B問題の難易度はFizz Buzzと同等とのことだ¹。

C問題は、全く歯が立たなかったものもあれば、もう少し時間があれば解けそうだったものもあった。ここでC問題を復習し敗因をまとめたい。今回は2回分。

同じC問題とは言え、多少難易度が変動することもあるようで、各回の、実際の正答率から割り出した難易度は有志による非公式サイトAtCoder Problems² を参照した。
難易度の定義はAtCoder社が提供している人材サービスのサイトを参照した。

AtCoder Beginner Contest C問題復習 その1

ABC 170 （6/14開催）

C問題 - Forbidden List

• 難易度: 灰色(Eランク)

アプローチふりかえり

• 立てた方針

  • 与えられた整数列 p_1, ... p_n を小さい順に並べ替える
  • それぞれと X を比較して、絶対値が一番小さいものを探す

• 解けなかった理由

  • sort() の考え方が理解できず挫折（引数に関数が入るってどういうこと・・？）

  引数に比較関数を指定しない場合には文字列として比較されるので注意が必要です。

  (【JavaScript入門】sort()による配列・文字列・オブジェクトのソート方法 より)

公式解説

• 与えられた整数列 p_1, ... p_n を起点にするのではなく、 X を起点にして考える

解き直し

• 要素数の数え方を調べた（引数の中に関数が入っているのは「高階関数」というらしい³がそれは追って学ぶ）

ABC 171 （6/21開催）

C問題 - One Quadrillion and One Dalmatians

• 難易度: 茶色(Dランク)

結構難しいと思います。C問題にしてはなかなか。苦労した人も多いんじゃないかと思います。

(Youtube解説より)

アプローチふりかえり

• 立てた方針
  • 26 + 26^2 + ・・・という式が頭に浮かんだが、方針は立たず
• 解けなかった理由
  • プログラムで何を求めれば良いのか、問題設定ができなかった

公式解説

• 与えられたNの値の最大値から、犬の名前の最長の長さを求める→15文字
• N番目の犬の名前の長さが l 文字の名前の中で、辞書順で N-(26+26^2+26^3+...+26^(l-1)) 番目を求める

解き直し

• 配列の宣言の仕方を調べた
  • (初心者向け) JavaScript 配列の作成と初期化 - Qiita
• ◯番目のアルファベットを文字列を変換するやり方がどうもわからず、断念

おわりに

これまで5回挑戦したABCのC問題を一気に復習し、次のコンテストでC問題まで完答するぞと意気込んだもののそう甘くはなく、、今回は2回分で時間オーバー。

FizzBuzzレベルの卒業まで、もう少し時間がかかりそうだ・・

1. AtCoder コンテストについての tips - Qiita ↩

2. メンター役になってくれているエンジニアの友人が教えてくれた。感謝。 ↩

3. JavaScriptの配列で要素のカウントと連想配列にする方法 - suzu6 ↩