なが月・17日目 - Napier

17日目

午前

早く起きたのでポートフォリオの更新をしていた。テキストが多くなると読みづらいのでBootstrapカードに置き換えた。

ABC132のC問題において、もちろん問題なく正解(35ms)はできたものの、C++答案の中で2倍の速度(15ms)のものがあったので調べたところ、

ios_base::sync_with_stdio(false);
cin.tie(NULL);

という記述を発見した。それぞれ「coutとstdioの同期を無効化する」「cinが呼ばれたら自動的にそれまでのcoutバッファを出力する仕組みを無効化する」という入出力高速化テクニックであるらしい。これについてIOI 2009 Technical Info (PDF)では、「cin/coutは遅いことからscanf/printfが推奨されるが、それでも使いたい場合は上記2行を挿入した上で、一行ごとにflushしてしまうendlではなく"\n"を使い、また同期が無効化されるためcinとscanf、coutとprintfを混在させない」旨の助言が記されていた。

午後

午前の続きでABC132Dを解いていた。コンビネーションになることは分かったが、必要になる階乗をそのまま計算すると爆発するのでDPで求めようとした( ${}_n C_r$ = combination[n][r])が、計算段階で最初0≦i≦Kについてのfor文にしてしまっていたため負の要素番号参照で実行時エラーを起こし、各行でearly returnしてどこでコケているのか探さなくてはならず、スタックトレースから異常の場所が一目でわかるPythonがありがたく思えた。この問題が解消した後も全く順調ではなかった。WAを連発し、コンテスト終了後に公開される全テストケースを見て100 10を入力すると負数が出力されたのである。これはオーバーフローに違いない。しかし10^9+7で割った余りを求める意義とは、10^9+7未満の二つの数を足してもintの範囲に収まりオーバーフローしないところにあるはずだ...と思ったところで、出力段階では二つの数を掛けていることに気づいた。64bit整数でなければ駄目だったのだ。答案の中には配列の要素数をNより常に大きい数で確保したり、不要なはずのN, Kも含めてすべてlong long intで宣言しているものが見受けられるのは、要素数が1ずれたり、こういうオーバーフローに気づかずペナルティを受け時間を浪費することを避けようとするものだったことがよくわかった。

またPythonで単に指数表記(1e9)すると小数扱いされ計算がおかしくなるので、整数扱いされるように操作しなくてはならないということもわかった。

AEチュートリアルでは、ストップウォッチボタンを押すことで最初のキーフレームが記録され、その後はタイムライン上を動かしてから値をいじることで新規キーフレームとして自動登録されることがわかった。テキストを追加・編集する際は、ワークスペースを切り替えるとよい。

https://helpx.adobe.com/after-effects/how-to/creating-animating-text.htmlでは、テキストアニメーションを学ぶ。テキストレイヤーにアニメーターを追加すると範囲セレクターと選択したアニメーターの内容が追加される。ここで仮に不透明度アニメーターを0%とすると、文字が消える。さらに範囲セレクターの開始ストップウォッチを押すことで、範囲セレクターの開始値がキーフレームキャプチャの対象になる。1秒後にこれを100%に変えると、文字が一文字ずつ透明から不透明になっていく。これは「不透明度を0%にする」効果が最初テキストの全体(開始0%-終了100%)に適用されていたのが、テキストの中盤より後に適用され(開始50%-終了100%)、最後には全く適用されなくなる(開始100%-終了100%)という仕組みのようだ。

夜になって突然ABC138の告知が来たので慌てて準備をして取り組んだ。D問題は直接の親子ノード情報をまず収納して、DFSで親の親に子の情報を伝えることにしたがそれでも根まで伝播させられないのでダメだなと思いつつ提出、Python3とC++の両方でAC+TLE+WA構成の結果が返ってきた。大きいノード＝子から順番に自分を含めた子孫setを親に渡す方式なら少なくともWAは避けられそうだが、どのみちTLEしている。今日中にD問題を理解できればよいのだけど。

解説を読むと、制約により子は必ず親より番号が大きいので、各操作において指定された根にカウント加算量を貯めておいて小さいほうから順番に直接の親からのカウント加算量を自分に加算することで漏れなくカウントが成立することがわかり、子孫一覧を作ってシミュレーションするなど不必要であった。

今日のDは比較的簡単に解決したが、そもそも正解者数が多く解けてしかるべき問題だった。シミュレーションが最大4*10^10回の加算を行うことから早々に別の方法を考えることが求められたといえる。