制限時間に収まらない(=不正解となる)データが与えられるだろう。したがってもっと高速なアルゴリズムを考えなさいというのが趣旨となる。常に最小のペアであることが保証される。次の答えの候補になる。言われてみればそうである(孫権顔)後は候補が複数あった場合に低コストで最小値を得られるデータ構造を考える。二分ヒープ(最小)である。模範解答のひとつとなる。さんに解説いただいて初めて理解できた。スレッドを参照されたい。num1をa、num2をbとします。a[i]+b[j]<=a[i+1]+b[j]です。a[i]+b[j+1]かa[i+1]+b[j]が答えに含まれる時、a[i]+b[j]は必ず答えに含まれます。a[i]+b[j]が答えに含まれない時a[i]+b[j+1]とa[i+1]+b[j]は答えに含まれることはありません。ここからが主題なのだが、これらの問題はプログラミング能力というか算数の問題なのだ。O(1))データ構造とだけ覚えていれば使える類のものだし、そこがこの問題を解く最大のキーというわけではない。その候補になる」という核心部分が出てこなかったし、むしろここがこの問題の最大のキーポイントであるわけで。ここからは自分でもうまく整理できていないのだが、これは「数学力」なんだろうか。僕が数学が苦手なのは自他ともに認めるところだが、いま大学院の授業についていくためにマセマの微分積分とかを解いてるけど、なんというかこう、公式あてはめて微分するとかとは違うわけじゃないですか。使われているのは中学生レベルの四則演算で、むしろ「数学的思考力」を問われているというか。社会人になってプログラマとして10年ぐらいやっていて忘れかけていたけど、そういえば僕は勉強まったくできなかったな、受験敗者だったわ、忘れてた。僕には数学的思考力が致命的にない。いうのをアルゴリズムクイズを解いていると嫌というほど思い出させられる。今回の2題は非常に悔しい思いをしたので覚えたが、これを繰り返していけば僕のように頭がよくない人間も類題を解けるようになるのか、それともちょっとひねられるだけでまたまったくお手上げになってしまって悔し涙に枕を濡らすのか、いまは分からない。願わくは2年後に読み返したときに「あの時はあんなしょうもない問題で悩んでいたんだなぁ😅」と思えるようになっていたいが、どうやることやら。Androidを使って、前回と同じく下のようなチャットアプリを作るので、興味のある方は前口上を飛ばして後半をお読みください🎄Amplifyとは本題に入る前に、Amplifyを最近よく耳にするようになったけど何かよく分かっていないという人向けの説明をします。Amplifyはモバイルバックエンドを爆速で作るためのサービスです。https://aws.amazon.com/jp/amplify/他のいわゆるモバイルバックエンドとの際立った違いのうち、個人的に強調したいのは以下2点です。バックエンドはAWSのサービスであり、真の意味でスケールするGraphQLのマネージドサービスを利用できる本日時点で唯一のプラットフォームであるAmplifyの良い点として、フロントエンドから利用する時はそれと意識せずに簡単に構築できるけれども、バックエンドはAWSが個別に提供するサービスで構成されているという点です。これは、バックエンドをキャパシティのよく分からないブラックボックスとして扱うことなく、必要であればAWSを使い慣れたインフラ部隊と協力して本当の意味でスケールするようにチューニング可能だということです。AmplifyはGraphQLのマネージドサービスを提供する今日時点で唯一のプラットフォームです。GraphQLの良さは他の記事に譲りますが、これを自前で構築するのは中々骨が折れます。AppSyncが使われますが、これはGraphQLのマネージドサービスであり、サーバのプロビジョニングやチューニングを気にすることなくGraphQLのメリットを享受できます。Studioとの統合がすすみ、CLIを単独で使用することは今後かなり少なくなります。したがって、基本的には普段開発しているときのようにCocoaPodsやGradleでライブラリを導入するように使い始めることができます。具体的な使い方はこのエントリの後半で解説します。APIやGraphQLAuth...認証と認可Storage...ストレージAnalytics...分析とユーザエンゲージメントPredictions...AI/MLの組み込みXR...AR/VRのような機能のうち、使いたいものを好きなだけ選んで使うことができます。これまでもモバイルからAWSのサービスを使うことは当然できました。SDKによって簡単に実現できます。これはどちらかと言えば「AWSのこのサービスを組み込みたい」というマインドセットで使います。iOS/Androidでは「APIを組み込みたい」というように、ユースケースの側面から使うことができます。前置きが長くなりました。ここまでがAmplifyの概要です。iOS/Androidについて解説します。2019で新しく発表された、Amplifyをモバイルからより簡単に使うためのアップデートです(公式ブログ)。使ってGraphQLにつなぐ方法を紹介しましたが、これが新しいAPIでどんな感じになるのか見てみましょう。iOS/Androidはプレビューリリースで、本番環境での利用はまだ想定されていません。Androidを使ってGraphQLの読み書きをしてみたいと思います。序盤は公式サイトの手順に準じます。プラグインをインストールします。Java8の設定と依存関係のインストールをします。これはGraphQLのスキーマ定義で、これを元にAndroid用のモデルが自動生成されます。以前のエントリと同じくリアルタイムチャットアプリを開発してみます。前回と同じ次の定義で作ってみましょう。CLIをインストールします。npmを使うのでNode.jsが入っていない人はインストールしてください。コマンドを実行します。AWSのマネジメントコンソールにリダイレクトされるので、そこでユーザを作成してキーを発行してください。ここは次のチュートリアルに非常に詳細な解説があります。プロジェクトをビルドします。タスクが追加されます。CLIが必要なバックエンドをプロビジョニングしてくれます。この作業は数分かかることがあります。完了したら、これらを使ってチャットのメッセージを読み書きしてみましょう。最初にAmplifyを初期化するための設定をします。カスタムApplicationクラスを作成し、次の内容を追記します。追加するのを忘れないでください。android:theme="@style/AppTheme">あとは読み書きをするだけです!まずはミューテーションから。ようなビルダーがついてきます。ユーザの入力に合わせて簡単にモデルを組み立てることができます。メソッドを呼ぶだけです。})}次はクエリです。メソッドを呼ぶだけです。描画するといった使い方が一般的でしょう。})}最後にサブスクリプションです。メソッドを呼ぶだけです。これだけでメッセージの作成をリアルタイムに通知してもらえるので、チャットアプリのようなものがいとも簡単に作成できます。)}めちゃくちゃ簡単ですね!ここまでが公式のチュートリアルに相当する内容です。時系列でメッセージを取得ここからは少し発展的な内容を扱います。AmplifyでGraphQLを使う場合、デフォルトではAppSyncとDynamoDBが使われます。DynamoDBは扱うデータサイズや規模によらず、うまく設計すればミリ秒単位のパフォーマンスを維持できるKVSおよびドキュメントデータベースですが、一般的なRDBMSを1台だけで扱うときとは違う点を考慮する必要がある場合があります。日付をソートキーとして設計するのがよくあるパターンです。使ってメッセージを時系列に取得することにします。前出のGraphQLのスキーマを次のように変更します。部分で時系列に取得するためのキーを追加しています。部分で、このキーを使ったクエリをする際の名前を指定しています。実行してモデルファイルを再生成し、バックエンドにプロビジョニングします。これで、GraphQL的には次のようなクエリで時系列で取得できるはずです。