ABC175-F Making Palindrome を解いた。
大まかな方針を知ってても実装にめちゃめちゃ時間がかかった、というか色々な慣れないことをする必要があったせいで、アルゴリズムが分かっててもコードへの落とし方に迷いまくった。文字列を頂点とするグラフを作るのが本当に大変。文字列ごとに数値を用意すること自体はまだ楽だが、辺を貼る処理が本当に面倒だった。突き合せの比較処理の実装にかなりの時間を要してしまった。
これを考察と実装合わせて時間内に解けたらそりゃ橙パフォももらえるな、と思う。
実装が本当に大変だったので予め解法を知っててもかなり達成感があった。きついけど良問！
CSSによるスクロールバーの外観の制御を試してみた。::-webkit-scrollbarとかのやつ。
「widthいじってもバーの幅変わらんな」と思って戸惑っていたら、どうやら縦スクロールバーはwidthで横スクロールバーはheightでいじるらしい。そりゃそうか。確かにこれは分かりやすい。
::-webkit-scrollbar-trackの使いどころが今一つ分からない。::-webkit-scrollbarの側だけの設定では不十分なのか？まあ2重箱になっていればその分自由度が増えそうではある。ちょっと色々な装飾がしたかったら役立つのかもしれない。
ARC116に出た。ちょっとというか大分てこずったが、大失敗はしなかったので良かった。問題も結構好きだ。
Aは、とりあえず愚直素因数分解を考えてみて、$N\leq 10^{18}$という制約から通常の素因数分解は無理、テストケースの数からしてosakなど使っても不可能と言うことで見切りを付けた。
素因数分解された状態を考えて考察したところ、2が含まれていればそれだけあらゆる奇数の約数に対して偶数の約数あるじゃんということに気付いてAC。不安なので一応ちょっとだけ実験した。
Bは良く分かんないので最初は一旦飛ばした。良く分かんなかったというか、主客転倒とソートにはすぐに思い至ったのだが、同じ値の$A_i$が複数あるときにめんどくさいことにならないかが心配で正当性が示せなかった。
小さいケースで試した感じ、同じ値が複数あることはあんまり気にしなくても正しい答えが出てくれてそうだったので未証明で続けた。実際気にしなくてよかったらしい。理由は良く分かってない。後でちゃんと証明したい。
$A$をソートした上で、全ての$i,j (i\leq j \leq N)$について$A_i, A_j$がそれぞれ最小値、最大値になる場合を調べる$O(N^2)$解をまず書いて、それを数式処理で$O(N)$にするやつをしてAC。やったことはかなり簡単なことだがスピードが出なかった。こういうのをスッパスッパできるようになるのも上位になるために必要なことなんだろうな。
CはBより先で爆速でACした。一瞬橙prfが表示されたんだぞ！！！！俺はえらいんだぞ！！！！！！
どんどん倍数になっていくそうなので、あんまり自由度はなさそうだなと感じる。上限がMだそうなので、2倍2倍とでもしていけばすぐに上が詰まってしまう。で、これはDPなどで「行く途中」を順々に考えるのではなく「ゴール」の方を決めて、道筋を分配するような考えで行けそうだなと感じた。$A_N$の値を1からMまで動かしてそれぞれ素因数分解して、各素数を$A_i \rightarrow A_{i+1}$の遷移の部分に割り振るパターン数を数える。$A_0=1$と考えれば遷移はN回と考えられる。$A_N=\prod_{i=1}^{l}p_i^{k_i}$と素因数分解できたとき、それに対応するパターン数は重複組合せを用いて$\prod_{i=1}^{l} {}_n \mathrm{H}_{k_i}$と計算できる。組み合わせは前計算をしていれば$O(1)$なのであとはやるだけ。
Dは本当にかなり悩んだ。まず最初とりあえずdp[数列の長さ][総和][総xor]という4乗DPを書いて、まあそりゃ答えは出るのでこれを高速化できないかと思ったが当然無理。根本的な発想の転換が必要になる。
で、40分飛んで、ようやく「あっこれビットごとに独立して考えられるし1のビットがどの変数に移動しても変わんないじゃん」「ビットごとの1の数で考えられるじゃん」という真実に気付いてACした。気付くのが遅い！
足し算とXORの値が固定ってかなりきつい制約だよなと思ったけど、こう考えるとゆるゆるである。面白い。ただ本当にさっさと気付きはしたかった。
上から1の数を決めていくDFSを書いたがサンプルケースでTL超えたので、メモ化を付けたら通った。とっさに「とりあえずメモ化」がすんなり出てきたのは良かったと思う。せっかく解ける直前まで追い詰めたのに詰めが甘くてTLEとれず、みたいなことにならなくて良かった。
しかしCで「先にゴールが決まっていてそれを分配する」のイメージはあったのになんでこの発想に40分至らなかったんだか。「bit」を「素数」に、「1の数」を「素数の冪」に言い換えればほぼ同じだよね？惜しいことしたなあ。
時間余ったので一応Eを考えたが解けず。フローは絶対間に合わないし、全頂点から距離測定したらますます間に合わないし。答えはにぶたんだったらしい。確かに答えの数値さえ出ればいいんだもんね…納得。ただ解説の問題P3については理解しきれてはいないので要復習。
javascriptでscrollIntoViewという機能を知った。特定の要素にスクロールしてくれるらしい。
特定の要素を注目させたいという目的ならばかなり有用なのだが、スクロールバーの位置調整という意味では使いにくい。というのも、特定のスクロールバーだけを動かしてこの要素を中央にしようみたいな機能ではなく、とにかく画面全体のスクロールバーで出来る限りを尽くしてこの要素を画面内に持って来ようという機能なのだ。
細かい指定もできないし、そういう意味では他のスクロール系機能との住みわけが出来ている。繰り返し言うが単に注目を行かせるだけの目的ならかなり便利だ。
ちょっとしたページを作っている。久しぶりに何かしら面白い物が出せそうだ。
Categories: 未分類