noyのブログ

健康なエンジニアを目指す人のブログ

はてなサマーインターン2019に参加しました

まとめ

はてなサマーインターンに参加しました

id:noy72 です.はてなサマーインターン2019の参加記です.

インターンとの出会い

1, 2年前に研究室の繋がりではてなに遊びに行ったことがありました.私が所属する研究室のOBがはてなにおり,そのOBの方から研究室の先輩,そして私に話が流れてきました.

その時にバイトやインターンの話を聞き,機会があれば行ってみようと思いました.

インターン選考

選考は Web申し込み→簡単なプログラミング課題→面接 の順に行われます.

Web申し込み

書類を書かなくて良いのはいいですね.

プログラミング課題

プログラミング課題はROT13でした.アルゴリズム部分での差別化はあまりできないと思ったので,基礎的な部分をきちんと抑えることを意識して ROT N (-1e9 \leq N \leq 1e9 ぐらい) といくつかのテストを書きました.

面接

面接はがっつり時間をとって行われ,十分すぎるほど話せます.インターンにおいて初めの学びがこの面接で,こちらの意見に対し,面接官の方が「意見の要約+それについて良いと思う理由」を返すのが非常に印象的でした(勘違いだったら忘れて下さい).とても話しやすかったです.要約することで相手の意見をきちんと理解していることを伝え,その上で感想を言う…… 見習おう,と思いました.

もし私がインターンの面接をまた受けるなら,今まで何をやってきたのか→なぜこのインターンに応募したのか→どのチームに配属されたいか・何をしたいか という流れを抑えると思います.今回の面接では失敗したので.

インターン

はてなサマーインターンでは講義パートの前半部分とチーム開発の後半部分に分けられます.そこで感じたことをつらつら書きます.

インターンの参加メンバー

インターンの参加者は自分を含め 8 人です.自分以外の7人,みんな強そうだと思いました(小並感).

前半2週間

わからなかったら人に聞く

メンターの方がちょくちょく声をかけてくれるので質問がしやすかったです.また,インターンに割いている人数が多いため,質問待ちをすることがありませんでした.

密度が高い

課題には業務時間ほぼまるごとかかりました.業務時間中に暇になることなく,残業続きになることなく,ちょうどよい分量だと思います.用意されているオブション課題を全部終わらせるなら残業は必要そうです.自分は業務後,社員さんに混じって呑気にMTGのドラフトをしていました.

学ぶ範囲が広くて面白い

前半二週間で様々な講義が行われます.Web開発に必要な知識に加え,コミュニティについてや企画についての講義もありました.

成果発表について

想定していた全ての機能を実装することはできませんでした(MTGのせいではないはず).経験のないフロントエンドでかなり詰まったので,全く知らない事に関してはどこかでちょっと触っておくといいかなと思います.

後半2週間

丁寧に教えてくれる

質問があれば丁寧に答えてくれるし,何もわからない状態であればペアプロをしてくれる.多くの時間を使ってもらいました.

開発に参加できた

何もわからない状態から始まりましたが,メンターやチームの方のサポートがあり何とか手を動かすことができました.

TDDとかテストとか

最初からTDDのようにテストを書いてから実装を進めればよかったんじゃないかと思っています.また,テストを読めばクラスや関数がどう使われているかがわかってコードが読みやすいんじゃないでしょうか.

誰か教えて下さい.

優しい

平和に過ごせました.ありがとうございます.

後半二週間で実際にやったこと

配属先はtomato3713さんと同じくmackerelチームで,ダッシュボードのウィジェットの開発をしました.私の担当はバックエンドで,scalaAPIを生やしました.もっと手際よく開発したかった……

開発した機能の詳細はtomato3713さんの記事に任せます.

f:id:noy72:20190913120513j:plain:w500
こんなのです

2019/09/30:追記

アップデート情報にアラートステータスウィジェットが載りました. ヘルプも増えてる〜(当たり前)

mackerel.io

mackerel.io

思ったこと

時間は大切

学びたいことがあるなら時間のある時にたくさん手を出しておいた方が良い.

悩みすぎ禁物

全くわからないときは全くわからないことを伝える.よくわかっていない状態で何かするのは無駄.

日頃の行い

そこまで時間をかけてはいないけど,技術書を読むだとか,写経でWebアプリ作るだとか,Pythonスクレイピングするだとか,Chrome拡張機能を作るだとかで得た知識があったおかけで,インターンでは致命傷で済みました.

学ぶぞ! という気持ちで新しいことに挑むのもいいですが,自分が必要に思う機能を小さくても良いから作ってみるということを普段から行うのも無理なく知識を増やせていいと思いました.

あんまり会社っぽくない……?

想像の会社とちょっと雰囲気が違いました.一部の社員の方から「サークルっぽい」「研究室っぽい」という声を聞いたので,やはり特殊なようです.ただ,東京オフィスは京都オフィスより会社っぽいとの話も聞いたので,はてなというより京都オフィスの特徴のようです.

おわりに

インターンに参加しようと思っている人へ:はてなインターンおすすめです.

インターンで会った人へ:どこかで会ったらボドケで遊んでください.

他のインターン生の記事

furutsuki.hatenablog.com

utgwkk.hateblo.jp

blondenamazu.hatenablog.com

ergofriend.hatenablog.com

10-1.hatenablog.com

tomato3713.hatenablog.com

lunastera.hatenablog.com

『Clean Architecture 達人に学ぶソフトウェアの構造と設計』を読んだ

https://asciidwango.jp/post/176293765750/clean-architecture
asciidwango.jp

ソフトウェアの構造や設計についてどう考えるかを書いた本.「どのように実装するか」が気になってきた人向け.個人的にはかなり読みやすかった.

詳細の決定はあえて先延ばしにする

ソフトウェアの設計と聞くと,割と詳細まで決めてしまうというイメージがあったけど,この本では「詳細の決定を送らせろ」と述べている.初めから完璧なアーキテクチャはないため,具体的な実装部分はあえて決めないという手法を紹介している.

本書では,あるソフトウェアのデータアクセスの方法を例に先延ばしについて説明している.まずはスタブを作る.スタブでは開発が進まなくなった時,RAMにデータを保存するメソッドを実装する.そして,永続化を考えなければならなくなった時,単にファイルに書き出すメソッドを実装する.具体的な実装を簡単に切り替えるようにしておき,必要になるまで実装しないことで,後から柔軟に変更をすることができる.

データベースを先に決めてしまったため面倒なことになるという失敗はつい最近起こしたばかり.具体的な部分を決めるのが早すぎるというのは初学者あるあるかも知れない.

境界線を引く

詳細を先延ばしにするためには,機能がきちんと分けられていないといけない.依存関係をきちんと整理し,ビジネスルールと具体的な実装を分離する必要がある.具体的な実装が分離されているから,必要になった時に置き換えることができる.

やっぱりバランスが大事

同じ理由・同じタイミングで変更されるコンポーネントのまとまりと,再利用しやすいまとまりが一致するとは限らない.どんな理由でもコンポーネントをまとめることは,インタフェース分離の法則のように「必要な部分だけつまめるようにする」ことに相反する.コンポーネントをどのぐらい分離させて何をまとめるのかは,上手にバランスを取らなくてはならない.

境界線を引くと言っても,もしかしたら引かない方が良いこともある.変更される可能性が高い部分は分離させておき,変更が起きにくい部分はまとめてしまうなど,柔軟に対応する必要がある.

『コーディングを支える技術 成り立ちから学ぶプログラミング作法』を読んだ

gihyo.jp

プログラミング言語の文法や機能を,言語の比較や歴史的な背景を用いて解説した本.個別の言語の知識は数年後も役立つかは分からないので,言語に依存しない普遍的な知識を学ぶ方がいいと著者は述べている.「何の言語を勉強すればいいですか」という質問の一つの答えになりそう.

「プログラミング作法」とあるけど良いコードの書き方の話ではない.

本書の対象者を自分なりにいうと,「プログラミング言語にはそれぞれ違いがあることを知った初学者」だと思う.静的型付け,動的型付け,変数のスコープ,継承,ミックスイン……などの概念をなんとなく知っている人なら内容を楽しく読めると思う.「この言語では,その機能をこうやって実現するのか」という新しい発見ができる.プロは「そうだね」っていいそう.

あるプログラミング言語を解説した書籍はたくさんあると思うけど,この本は機能という面から複数の言語の仕様を解説している.新しい言語を学ぶ際にも,本書のように複数の知識と結びつけるようにすれば,より効果的に,学べると思う.「プログラミング言語を1つ知っていれば,別の言語を学ぶときにその知識が使える」ということ.

というわけで,色々な言語を学んでみたいと思っている初学者が読んでみると面白いんじゃないかと思う.ただ,プログラミング初心者(プログラミングについて一切知識がない人)が読んでも意味がわからないと思うので注意.

面白かった章

11章 オブジェクトとクラス

少なくとも2人のオブジェクト指向言語の設計者が,「オブジェクト指向」という言葉を全く違う意味に使っています.特に,型と継承に関しては意見が逆向きです.(p.186)

クラスとは何なのでしょうか?この質問も一般的に答えようとすると泥沼にはまる,危険な質問です.(p.189)

この章では,「変数と関数を束ねて模型を作る方法」として,以下の4種類を解説している.

  • モジュール
  • 関数も変数と同じようにハッシュに入れる
  • クロージャ
  • クラス

「変数と関数が束なった模型」の表現方法が言語によって異なり,さらに役割も異なる.そして,言語ごとに「オブジェクト指向」という言葉が意味するものも異なる.

クラスとは,オブジェクト指向とは一体……うごごご!

『情熱プログラマー ソフトウェア開発者の幸せな生き方』を読んだ

この本は,ソフトウェア開発において良いキャリアを築くための方法を説明することを目的としている.以下の5つの章があり,製品に必要な側面をキャリアに応用する方法を説明している.

この本は「ソフトウェア開発者もビジネスマンである」ということを強調する.会社の目的は利益を上げることで,技術を学んだり利用したりする場を提供するわけではない.開発者でも自分の技術をビジネスの側面から評価することも必要である.だから,良いキャリアを築こうと思うなら,技術の分野は製品と同じように市場を選ばないといけないし,投資しないといけないし,売り込まないといけない.

もちろん,技術よりビジネスが重要と主張しているわけではない.あくまでも,テクノロジの価値をビジネスの側面から考えることも必要であるという主張である.「研鑽を怠らない」という章では,時代遅れな技術屋にならないための方法を述べており,高い技術力を持つ開発者でい続けることを重要視していることがわかる.

いくつかの節には「今すぐ始めよう!」というリストがあり,その節の内容を達成するための手法が書かれている.抽象的な目標を達成するための具体的な行動を決める参考になる.

好きな節

3 コーディングはもう武器にならない

どんなテクノロジに投資するか考えるだけでは不十分だ.テクノロジなんて,お金で手に入る日用品なんだから.(p.9)

タイトルが刺激的.

11 魚の釣り方を学ぶ

自分からどんどん訊いて,調べて学べ!という内容.自分が知らないことを深掘りしたり,使っているツールについて調べたり.当たり前だけど難しい.

25 自分にどれだけの価値があるか?

「給料上げろってお前言うけどさ,それだけの価値を生み出してんの?」という内容.

ちなみに次の節で,「お前の職務における存在なんて,バケツの中の小石ぐらい」といわれる.

45 君は既に職を失っている

自分の職務をやり遂げるのは良いけど,それで満足してちゃだめなんだ.自分はプログラマ(あるいは設計者,テスター)だっていうアイデンティティにこだわるな.

『おれは あの職種で職を得たと思ったら いつのまにか失っていた』

感想

元も子もないことをいうと,自分の価値観に沿った選択が幸せな生き方になるので,自分の好きなようにやるのが1番良さそう.あと,ビジネスの知識を身に付けることが必ずしもエンジニアとしての成長に繋がるとは限らないので,どれだけ分野を広げるかは自分と要相談.

当然だけど,本書はエンジニアとしてある程度の能力があることが前提になっているので,ひよこエンジニアがビジネスをかじってもひよこエンジニアである.

「開発者もビジネスマン」という言葉だけだと,「開発者もビジネスについての知識が必要である」という主張をしているように見えるけど,そうではなくて,「ビジネスの文脈から自分の技術の価値を説明できますか」という話だと思う.本書に「ビジネス側の人もちょっとぐらい技術について知っていれば,もっと楽に話できるのにって思わない? そういうことよ」みたいな記述があるので,ビジネスの知識といっても共通言語になる程度だと思う.

著者は Extreme Programming (XP) について学んだことがキャリアの転換期だったと述べている.XP の経験を通して,技術だけではなく(ある程度の)ビジネスの知識,1つの技術ではなく複数の技術,という考えになるのは分かる気がする(やったことないけど).

メモ

市場を選ぶ

  • 最先端のテクノロジ ハイリスクハイリターン
  • 需要と供給がキャリアにどのような影響を与えるか
    • 就職や転職で必要とされている技術は何か
    • オブショア企業がカバーしている技術は何か
  • 環境によって自分の能力が決まる部分もある
  • キャリアはビジネスとして考えるべき

製品に投資する

  • 理解していないことを掘り下げる
  • ツールの使い方を知る
  • ビジネスを基本を知る
  • 財務処理の一連の流れを聞く
  • ソフトウェア開発の方法論について学ぶ
  • オープンソースプロジェクトのコードを読む
    • プロジェクトの長所,短所
    • 利用できそうなロジックやパターン
    • アンチパターン
  • 仕事を自動化する

実行に移す

  • 今の職務は全力で
  • 自分は価値を算出できているか
  • 成功に溺れず,取り替えが効く存在を目指す
  • 八時間燃焼

マーケティング

  • 視点によって評価軸が変わる
  • 他職種の人とコミュニケーションできるようにする
  • 自分の業績は自分のビジネスの言葉で売り込む
  • エレベータスピーチを考える
  • 自分自身のブランドを築く

研修を怠らない

  • 未来を見据え,意図的に自らのスキルを育成する
  • 自分がプログラマ(設計者,テスターなど)であるというアイデンティティにこだわらない
  • 自分のキャリアについてのロードマップを作成する

『Webを支える技術 -HTTP、URI、HTML、そしてREST』を読んだ

gihyo.jp

2010年出版

この本は,Webに関連するいくつかの技術の仕様を解説し,Webサービスの設計方法を示すことを目的としている.Webについて学びたい人の最初の一冊に良さそう.ただ,約10年前の書籍である.むしろ,10年近く経っても基礎的な部分はあまり変わっていないことを体現していると言える.

Webサービスの開発手法ではなく仕様と設計の話なので,今すぐサービスを開発したいという人には向かない.「Webサービスの開発って何を考えないといけないんだろう……?」「そもそも仕様は……?」と気になってきた人向け.Webサービスの動作に意識が向けられるようになる.

第1部~第3部は基礎的な内容で,それらに比べると後半の内容はやや難しい.とりあえず前半部分を読んで,後半は必要に応じてで良さそう.

自分は「JavaScriptが難しい」という話を聞いて,それと関連して(JavaScriptが使われる)Webの仕組みも複雑だと思い込んでいた.しかし,著者はWebがシンプルであると言い切っている.考えてみると当たり前のことだけど,Webの仕組みと言語の仕様は別である.各技術をひとまとめにして複雑さを感じるのは良くない態度だなぁ,と反省.

Webは色々なところで使われているし,基礎の技術が大きく変わることもあまりないので,それらについて知っておくのは割と良いかもしれない.

おすすめ

第3部HTTP

Real World HTTPが背景知識がないためか読みにくかったので(文章が読みにくいわけじゃないよ!),先に本書を読んだ.HTTPの構成,メソッド,ヘッダについてわかりやすくまとめられている.

ある技術を学ぶときに,それが利用されている環境や状態がわかっているのとそうでないのでは,学習のしやすさが段違いだと改めて思った.

メモ

Web概論

Webを支える技術

  • HTTP 情報を取得するためのプロトコル
  • URI 情報を指し示す
  • HTML 情報を表現する文書フォーマット

ハイパーメディア

様々なメディアをハイパーリンクで結びつけて構成したシステム

REST

Webのアーキテクチャスタイル(アーキテクチャパターン)の一種.他に,MVC(Model-View-Controller)やパイプ&フィルタ,イベントシステムなど.

RESTは以下の6つを組み合わせたアーキテクチャスタイルのこと.

  • クライアント/サーバ
  • ステートレスサーバ
  • キャッシュ
  • 統一インタフェース
  • 階層化システム
  • コードオンデマンド

HTTP

MIMEメディアタイプ

リソースの表現の種類を指定する.

  • Content-Type メディアタイプ(テキスト,画像,音声など)の指定
  • charsetパラメータ 文字エンコーディングの指定

コンテントネゴシエーション

メディアタイプなどをクライアント側が指定する.

ハイパーメディアフォーマット

microformats

Web上のリソースにメタデータを与えるための技術.

Atom

凡用XMLフォーマットの一種.ブログなどの更新情報を配信するためのフィードとして知られている.

『この一冊でよくわかる ソフトウェアテストの教科書 品質を決定づけるテスト工程の基本と実践』を読んだ

www.sbcr.jp

ソフトウェアのテスト技法とテストドキュメント,モニタリングについて解説した本.テストについての概念ではなく技法についての実践的な内容になっている.平坦な言葉で説明されているので,ソフトウェアテストについての知識がなくとも十分読める.初学者向け.練習問題付き.

例として挙げられているのは組み込みソフトウェアなので,Web系だとあまり参考にならない部分もありそう.ただ,テストの知識がないと,テストが冗長になったり抜けが起きたりするので,基礎的な部分を身につけるために読むのはあり.

メモ

求められる品質意識

  • Verification and Validation(検証と妥当性確認)

    • Verification 開発仕様書通りにソフトウェアが作成されているかを確認
    • Validation ユーザーの要求が満たされているか確認
  • 品質とユーザー満足度の関係

    狩野モデル(かのうモデル)

テスト工程

  1. テスト計画

    テストの目的を決める.次に,テストする方法(テスト観点)を決める.目的を品質特性に変換することで,テスト観点を抽出できる.

    テスト観点一覧表 機能 * テスト観点の表で,各マスに必要な観点かどうかを真偽値で示す.

  2. テスト設計

  3. テストケース作成

  4. テスト実施

  5. テスト報告

ホワイトボックステスト

主に単体テストで行われる.

制御フローテスト

フローチャートからカバレッジ基準を満たす経路を見つけ,その経路を通るテストをする.

データフローテスト

データや変数が,定義→使用→消滅の順に処理されているか確認する.

メモリリークが起こるようなバグを検出できそう.

テスト技法

  • 同値クラステスト 結果が同じになるテストをまとめる

  • 境界値テスト  C(x) = True, C(x + 1) = Flase みたいなことを確かめるテスト

  • デシジョンテーブルテスト 全ての条件をどのように満たすか(真偽値,不等号)全列挙し,その結果を示す表.ワイルドカードを使ったり,表を分割したりする.

  • 状態遷移図 オートマトンのあれ.エッジを網羅したりノードを網羅したりする.

  • 状態遷移表 状態 * アクションの表を作り,動作結果を記入する.N/Aで仕様書にはない「できないこと」がわかる

  • 組み合わせテスト

    条件を組み合わせて行うテスト.そのままだと組合せ爆発するので,以下の手法を用いて減らす.

    二因子間網羅 どの要素の組み合わせも 2つ以上,テストケースに存在する.

    • All-Pair法 二因子間網羅を満たすテストケースのみ
    • 直交表 二因子網羅+α

テストドキュメント

テスト工程で作られるドキュメントの総称

項目:https://ieeexplore.ieee.org/document/4578383

思ったこと

  • 機能が正しいか調べるのはかなり大変

    そもそもテストは間違っていることは示せるが,正しいことを示せない. テストは単にやればいいだけじゃなくて,何を目的にしていて,それがどのようなテストで達成できるかを考える必要がある.その上,全てのテストケースを全列挙すると爆発するので,上手に減らさないといけない.

  • 厳しい時間的制約のため,テストが十分に行えないところも多そう

  • アジャイルみたいなウォーターフォールではない開発ではどのようなテストを行っているのか?

AtCoder Beginner Contest 114の解説+α

ABC114の解説とか別解とか.

A 753

はい.

print("YES" if int(input()) in {3, 5, 7} else "NO")

B 754

文字列を切り出して絶対値をとる.

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

signed main(){
    string s;
    cin >> s;

    int ans = 1e8;
    rep(i,s.size() - 2){
        ans = min(ans, abs(753LL - stoi(s.substr(i,3))));
    }
    cout << ans << endl;
}

その他

文字列の長さと切り出す長さがともに  10 ^ 5 ぐらい大きくなっても解ける.しゃくとり法を使えば線形時間である(modを取るのは必須).

C 755

357のみからなる数値の全列挙

自分が最初に書いた解法は公式の想定解法と同じ. 3, 5, 7 からなる数値を全列挙し,それが条件を満たすかを調べる.

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

int n;
int ans;

vector<int> v = {3,5,7,};

bool check(int number){
    bool res[3] = {};
    while(number != 0){
        rep(i,3){
            if(number % 10 == v[i]) res[i] = true;
        }
        number /= 10;
    }
    return res[0] and res[1] and res[2];
}

void dfs(int number){
    if(number > n) return;
    if(check(number)) ans++;

    number *= 10;
    for(auto i : v){
        dfs(number + i);
    }
}

signed main(){
    cin >> n;
    dfs(0);
    cout << ans << endl;
}

桁DP

公式解説放送でも触れられていたように,別解として桁DPがある.桁DPは  1 〜 N までの数値に,ある条件を満たす数値がいくつあるかを  O(\log N) で数え上げることができる.つまり,今回の問題の制約が  1 \leq N \leq 10 ^ {100000} でも解ける.典型な400点問題っぽい.

DPテーブルの意味は以下である.今回は  0, 3, 5, 7 以外の数字は使わないため,数字は  4 種類だけ考える.

dp[i][j][k][l][m][n] = 
    [どこまで見たか]
    [Nより小さいことが確定しているか]
    [3が含まれているか]
    [5が含まれているか]
    [7が含まれているか]
    [0が含まれているか(先頭の0を除く)]

桁DPは上位の桁から数字を決定していくため,小さい値は  0 を先頭に詰める.そのため, 3,7,5 に加え  0 も必要になる.また,[0が含まれているか(先頭の0を除く)]は, 00357 03570 などの区別をつけるために必要である.

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

signed main(){
    string s;
    cin >> s;

    int dp[20][2][2][2][2][2] = {};
    dp[0][0][0][0][0][0] = 1;
    rep(i,s.size()) rep(j,2) rep(k,2) rep(l,2) rep(m,2) rep(n,2) {
        int lim = j ? 9 : s[i] - '0';
        for(auto d : {0, 3, 5, 7}){
            if(d > lim) break;
            dp[i + 1][j or d < lim][k or d == 3][l or d == 5][m or d == 7][n or (d == 0 and (k or l or m))]
                += dp[i][j][k][l][m][n];
        }
    }

    int sum = 0;
    rep(i,2){
        sum += dp[s.size()][i][1][1][1][0];
    }
    cout << sum << endl;
}

愚直解(っぽいの)

また,愚直解(っぽいの)を高速化することでも通る.本質は想定解と同じ.

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

bool check(int n){
    bool r[3] = {};
    while(n > 0){
        int a = n % 10;
        n /= 10;
        if(a != 3 and a != 5 and a != 7) return false;
        if(a == 3) r[0] = true;
        if(a == 5) r[1] = true;
        if(a == 7) r[2] = true;
    }
    return r[0] and r[1] and r[2];
}

signed main(){
    int n;
    cin >> n;

    int ans = 0;
    for(int i = 3; i <= n; i++){
        for(int j = 1e9; j > 0; j /= 10){
            if(i >= j and  i / j % 2 == 0){
                i += j - 1;
                break;
            }
        }
        if(check(i)) ans++;
    }
    cout << ans << endl;
}

 1 〜 Nを単純にループさせるとTLEするので以下の部分で高速化を図る.

for(int j = 1e9; j > 0; j /= 10){
    if(i >= j and  i / j % 2 == 0){
        i += j - 1;
        break;
    }
}

 i のある桁が偶数なら  i は七五三数ではないことが明らかなので,その値を雑に飛ばしている.偶数を使わない  5 進数にすることに近い.こんな中途半端に高速化する意味はない.

D 756

素因数の組み合わせの全探索

 N!素因数分解し,素因数の組み合わせを再帰的に全探索すればACする.素因数の数が少なく,約数が  75 までなので全探索でも十分に間に合う.

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

void primeFactor(int n, map<int,int>& m){
    for(int i = 2; i * i <= n; i++){
        while(n % i == 0){
            ++m[i];
            n /= i;
        }
    }
    if(n != 1) m[n] += 1;
}

int ans;

void dfs(int idx, int p, vector<int>& v){
    if(p == 75) ans++;
    if(idx >= v.size() or p >= 75){
        return;
    }

    rep(i,v[idx] + 1){
        dfs(idx + 1, p * (i + 1), v);
    }
}

signed main(){
    int n;
    cin >> n;

    map<int,int> m;
    range(i,1,n + 1){
        primeFactor(i,m);
    }

    vector<int> v;
    for(auto i : m){
        v.emplace_back(i.second);
    }
    dfs(0, 1, v);
    cout << ans << endl;
}

DP

 2 ^ 3 3 ^ 2 2 ^ 2 3 ^ 3 は,約数の数で見れば同じである.つまり, 素因数  e _ i までを用いて表現される値の約数が  x 個であるならば,それらをまとめて計算できる.つまり,

 dp[i][j] := e _ i までを用いて表現される値の約数の個数が  j になる場合の数

としてDPを更新できる.

計算量が計算しにくい. O(\frac{N ^ 2X}{\ln N}) よりも結構少なそう( X は約数の個数).

 N = 1000, X = 1000 でも高速に動いた.

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

void primeFactor(int n, map<int,int>& m){(略)}

int dp(vector<int>& e, int x = 75){
    vector<vector<int>> dp(e.size() + 1, vector<int>(x + 1,0));
    dp[0][1] = 1;
    rep(i,e.size()){
        range(j,1,x + 1){
            rep(k,e[i] + 1){
                if(j * (k + 1) > x) break;
                dp[i + 1][j * (k + 1)] += dp[i][j];
            }
        }
    }
    return dp[e.size()][x];
}

signed main(){
    int n;
    ...
   (略)
    ...
        v.emplace_back(i.second);
    }
    cout << dp(v) << endl;
}

その他

典型ポイント

  • 巨大な値を素因数の積で表現する
  • 約数を見たら素因数を考える
  • 再帰関数による全列挙

所感

CもDも全探索で解けるので割と難易度は低めだと思う.「とりあえずわからない部分は愚直(ナイーブ,全探索)に考える」ことはかなり重要で,これができると急に解ける問題が増える.

Cを解けるかどうかの境目にいる人は,DFSやBFSのような全探索と,とりあえず全探索する方法を考えることが重要になってきそう.