過去に、Androidの64K問題でいろいろと足掻いてきましたが、光明が見えましたのでメモ
※実際の具体的なソースやサンプルデータは大人の事情のため、載せていません。あしからず。

64K問題って何？

僕が勝手に呼んでいる呼称ですが、使ってる人もちらほらいるのでこの名前でいきますね。

64K問題とは、Androidアプリが参照しているメソッドが64K(65536)を超えてしまうと、ビルドエラーになってしまう問題。

解決方法

Android5.0以降なら MultiDEXビルドが可能で、dexを分割して、64Kを超えるdexを分割してできるようになります。
Building Apps with Over 64K Methods

build.gradle

android {
    compileSdkVersion 21
    buildToolsVersion "21.1.0"

    defaultConfig {
        ...
        minSdkVersion 14
        targetSdkVersion 21
        ...

        // Enabling multidex support.
        multiDexEnabled true
    }
    ...
}

dependencies {
  compile 'com.android.support:multidex:1.0.0'
}

AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.example.android.multidex.myapplication">
    <application
        ...
        android:name="android.support.multidex.MultiDexApplication">
        ...
    </application>
</manifest>

純粋なAndroidアプリ（サードパーティのエンジンを載せていないもの）ならこれで解決！やったね！
(試してません)

解決できない場合

多くの方は解決できなくて泣きたいと思っていると思います。
例えばこんな方たち

Android4もサポートするんだけど・・・
Unity(ゲームエンジン)使って作ってるんだけど・・・

僕もその仲間の一人でした。
Unityで開発を進めており、MultiDEXでのビルドができませんでした。
（UnityはMultiDEXをサポートしていません。たぶん。）

そもそも、65536超えることなんてあるの？

あまりないと思いますが、簡単に超えてしまう方法があります。

それは以下の２点のような場合

「google-play-services」を利用

これを使うだけで、34000以上もの関数が追加されてしまいます。

Androidのメソッド数が64k(65536)を超えてgoogleplayservicesをチェックするときのメモ((φ(･д･｡)

このリンク先の関数の数はビルドエラー時に出力されたログから抽出したものですが、
8.4のバージョンでこれだけの数が使用されてしまいます。
なので、Google先生も公式に、使う機能だけ使おうね。と声を大にして言っています。

ライブラリプロジェクトを利用

さて、もう一つの意外な問題が、ライブラリプロジェクトの利用による関数の追加です。

「ライブラリには、いろんな処理が入ってるから関数が増えて当然でしょ？」
と思ってるあなた。
違うのです。
AndroidManifest.xml と project.properties が入っていると、一つのライブラリにつき、2000近く関数が増えてしまうのです。
（僕調査）

ビルドエラー時に見覚えのないパッケージが関数を2228ほど使用していました。
そのライブラリは、Unityの Plugins/Android/ 以下にひっそりと存在し、jarなどのライブラリファイルもありませんでした。
ファイル構成はこちら

Plugins/Android/Hogehoge/AndroidManifest.xml
Plugins/Android/Hogehoge/project.properties

UnityでManifestの自動マージを行ってもらっていたので、こういう構成にして用意していたのですが、
ライブラリ扱いされアウト。メソッド数が2000近く増えてしまう結果に。。。

真・解決方法

実際に、僕が行った解決方法は以下の3つの手段をとりました。

ライブラリファイルの精査
ライブラリの改修
GooglePlayServicesの精査

ライブラリファイルの精査

ほんとくだらないですよね。
Manifestのマージだけのプロジェクトなら、そもそもマージしておけよって話ですね。
もちろん、マージして影響が出ない範囲で、というのが前提ではあるのですが、これは一番有効手だと思います。

ライブラリの改修

これは、自作ライブラリがある場合、もしくはライブラリ提供者が改修と許可している場合にのみ有効な手です。
（改修すると、プログラム全体を公開しなければいけないとかなるとめんどいので、あまりお勧めしません。）

僕の場合は、編集可能なライブラリを全部まとめて一つに統合しました。

GooglePlayServicesの精査

言わずもがな。
モンスターライブラリのgoogle-play-servicesを精査して使うもののみ使おうね、って話です。
これをして、20000くらいなら簡単に削れると思います。

おしまい

とまあ今回はこんな感じですが、声を大にして言えることは、

外部ライブラリ使いすぎるなよ！ってことです。

これ違うよ、とかありましたら、コメントでもDMでもお願いします。
僕個人の調査と主観で記述しております。

おまけ

GooglePlayGames for Unity の罠

あいつ、Nearby入れないと動かねえぞ！
2000以上関数増えるぞ！ひどいぞ！
・・・何か取り除く方法あるのかな。
もう自作しちゃったから遅いけど。

外部ライブラリの罠

通信クラスやJSonパーサーをさらに外部のライブラリ使ってて腹が立ちます。
標準使えよ！お前らにパフォーマンス求めてないから！使いたいのは機能だけなんや！

別の会社のライブラリしこしこ作ってる人に聞いたところ、
「楽じゃん？」って言われました。ほんと激おこ。

まぁ「複雑な処理を作ってくれたプロがいるのなら、その機能をお借りする」のは当然のことなので、しょうがないとは思うんですけどね。
（僕もUnity使ってるし。）

Android 64K(65536)問題の解決策についてメモ((φ(･д･｡)