好きな英単語集

完全に主観で好きな単語集

随時追加

単語 ひとこと
abyss 説明不要
evanescence 意味も響きもいい
otherworldly シーキューブの非公式英語版で知った
translucent
pulverize 東京テディベア英語カバーで知った
precipice ポケモンで知った。だんがいのつるぎ
iridescence OneShotで知った
equilibrium 物理で知った
tranquil
nefarious
deep-six 厨二心がくすぐられる
quote-unquote 遊び心(?)があって好き
celestial ポケモンで知った。テッカグヤ
extraterrestrial マブラヴ設定wikiで知った
perseverance 強そう
xenophobia "xeno-"はかっこいい
pseudo- これつけるとかっこよくなる
sparkle "-kle"はどれも好き
acquiesce 似た単語があまりない
mirage
supernova むかし色違いウルガモスにこのニックネームつけてた
catastrophe
extermination 遊戯王で知った
genesis
harbinger SCP-1281で知った
void
vanity 遊戯王で知った
gnaw けものフレンズ1期のビーバーが木をかじるシーンの英語字幕で知った
thrice twiceに比べて絶妙なマイナーさが好き
glacier "ier"がいい。ポケモンで知った
meteor ポケモンで知った。コメパン
annihilation 発音わかりにくい。聖闘士星矢で知った
quiver ポケモンで知った。ちょうのまい
phantasm 月姫で知った。空想具現化
kaleidoscope
oblivion
noxious OneShotで知った
epiphany DDLCで知った
silhouette 毎回綴りを忘れる。リグレットメッセージの英語カバーで知った
thou/thee/thy 悪ノ召使英語カバーで知った
eclipse 動詞として使われたときが好き
dazzling ポケモンで知った。マジカルシャイン
lunar ポケモンで知った。みかづきのまい
never-ending
once in a blue moon 母校の学園祭のテーマだった
throw one under the bus 情景を想像すると面白い
ooze なんか響きが面白い。SCP-3333で知った
incinerate 強そう
captivate 悪ノ召使英語カバーで知った
eternity 最強
fate Fateで知った
albatross around one's neck 情景を想像すると面白い
maiden ローゼンメイデンで知った
fair 「美しい」のほう。悪ノ召使英語カバーで知った
soul 「人間」のほう。鉄壁で知った
burden 悪ノ召使英語カバーで知った
heavenly
blessing
retribution 悪ノ召使英語カバーで知った
sheer ポケモンで知った。ぜったいれいど
precious
devour 意味と語感がマッチしている
appreciate
omniscience "omni-"はだいたいかっこいい
sovereignty シーキューブで知った
rose-tinted シーキューブ英語版で知った
allure 遊戯王で知った。闇の誘惑
disdain 悪ノ召使英語カバーで知った
haze カゲロウデイズで知った
entwine ローリンガール英語カバーで知った
excruciate 東京テディベア英語カバーで知った
integrity 東京テディベア英語カバーで知った
demystify
galore 使い方が好き
paradox "para-"はかっこいいの多い
memoir "oir"もいい
perish ポケモンで知った。ほろびのうた
a myriad of むかし逆を張って"a lot of"のlotの代わりを探してたときに見つけた
a plethora of 上に同じ
in lieu of instead ofって言いたくないときに使う。使ったことはない
encrypt
enigmatic
arcane ポケモンで知った。ウインディ
unprecedented eが多い
bury one's head in the sand 情景を想像すると面白い
eviscerate かっこいい
electrocute

好きな日本語単語集

完全に主観で好きな単語集

随時追加

単語 ひとこと
風琴 シャナで知った
玲瓏 空の境界で知った
怜悧
煌めく 園城寺怜と花田煌が咲の好きなキャラツートップです
黄泉 聖闘士星矢で知った
澪標 漢字も意味も響きも使われ方もいい
わくらば 「病葉」でも「邂逅」でも好き
響む(とよむ) なめらかな感じがして好き
比翼連理 なんかのSSのタイトルになってて知った記憶
水鶏 響きがいい
熾す この漢字かっこいい。熾天使とか
歌う 日常語だけど響きがいいと思う
古(いにしえ)
金(くがね) 「こがね」はそこまで好きじゃない
銀(しろかね) 「白金」じゃないのがポイント
銅(あかがね)
鉄(くろがね)
幽世 遊戯王で知った。最強クラス
逢魔が刻 忍たま乱太郎で知った
服う(まつろう) これは平仮名より漢字のほうが好き
上代の助動詞
上代の助詞。上つ代・時つ風・天つ神など
神さぶ シャナで知った
焔(ほむら) ルビサファで知った
掌(たなごころ) なんか好き
詩篇 「編」でなく「篇」
真名
楼閣 「摩天楼」よりこっち
冀う 遊戯王で知った
吟ずる
薄明 ハクメイとミコチ』を読もう
愛染 ドイツ語っぽい
皇(すめらぎ) 賭ケグルイで知った
夜伽 「伽」が強い
遍く
偽典 見た目と意味が強すぎる
微睡み ひらがなもいい
僭称 してみたい
遥か
翡翠 月姫で知った。漢字が強い
忌憚
霹靂
階(きざはし)
韜晦 図書館の魔女で知った
響きが好き
たまさか
玉響(たまゆら
射干玉
まほろ
あらゆる
神楽 銀魂で知った
腕(かいな) ルビサファで知った
陥穽(かんせい) シャナで知った
白夜
極夜
銀河 銀河鉄道の夜好き
白昼夢
叢雲
朧月夜
眼(まなこ) 遊戯王で知った
紫苑 「シオン」って名前好き
終(つい) 「終の棲家」とか好き
黎明 ( | )
揺籃
秘蹟
真紅
水銀燈 翠星石が一番好き
銀沙
悠久 「悠」も「久」もいい
久遠
螺鈿 図書館の魔女で知った
盈月 咲で知った
烏有
月読 遊戯王で知った
斎く 「斎」が強い
濫觴 字面と意味のミスマッチがすごい
意味も字面も好き
俯瞰
福音 「音」を「いん」と読む単語は強い
螺旋
蠕動 字面の絶妙な気味悪さがいい
蠢く 「うごめく」感すごいよね
叡智 「叡」が強い
原罪 moonlit bearで知った。厨二病御用達
盟神探湯 恵まれた漢字から繰り出されるカスみたいな読み(響きは好き)
異端審問 月姫で知った
衣(ころも) 響きがころころしててかわいい
答ふ(いらう)
誰何
鈴生り 「すず」という響きが好き
追儺 意味も響きも好き。新世界よりで知った
凍つ
誘蛾灯
揺蕩う
随(まにま) 千本桜で知った
この漢字に限る。「瓶」はだめ
薬研 図書館の魔女で知った
懶惰 「だらん」のアナグラムなのが推しポイント
甍(いらか) 方丈記で知った
炯々 「炯」の字のギラギラしてる感じが好き
永久(とこしえ)
枸櫞
泡沫(うたかた) 最強クラス
同胞(はらから)
艶やか(あでやか) 光沢のある絹のイメージ
とげとげしてる感じの響きが好き。エメラルドで知った
茉莉花 図書館の魔女はいいぞ
不壊(ふえ) 咲で知った
深山幽谷
竜胆(りんどう)
虹彩 英語の"iris"も好き
蜃気楼 語源も現象も好き。見たことないけど
弥縫
海神(わだつみ) 鳥の詩で知った
穿つ
喰む
桔梗 犬夜叉で知った
ポケモンで知った
妖(あやかし)
冥王代 図鑑で年代のところにこれ書いてあって興奮したの俺だけじゃないだろ
菘(すずな) 春の七草最強。次点は妹のナズナ。ビリはホトケノザ
漁火
永訣 シーキューブで知った
桎梏 遊戯王で知った。結構文章で使われてるイメージ
暮れなずむ 「なずむ」がいい。「ず」の摩擦がいい
御厨(みくりや) 「くり」の軽さがいい
淫靡 かなり官能的な字面だと思う
迂遠 うえーん
産土(うぶすな)
卜占 「卜」の字が好き。主に読み方の意外性が
須臾 「刹那」よりこっちのほうがいい
碧海
那由多
傅く 「従う」とか「跪く」は無理やり従わせてる感あるけど「傅く」は主従純愛モノという感じがする
湯女(ゆな) 完全に響き
蝕む 字のかっこよさがヤバい。「日蝕」「月蝕」は絶対にこっちで書く
煙霧
霊媒
謀る(たばかる) ひっくり返してる感じの響きがする
依る
憑く 漢字が強い
燐光
風花(かざばな) 意味がきれい
神無月 「カンナ」は「シオン」と同レベルに好き
幾星霜 「霜」の字がいい味出してる
しむ 助動詞
爾来 「爾」の字がいい
鼎立 使う機会があったら積極的に使っていきたい
深窓
瑠璃
琳琅 草枕で知った
襤褸 「ぼろ」と「らんる」のギャップがいい
瀝青 字が強い
紫電 リリなので知った
睦む
集く
汎神論
童(わらべ)
霊廟 遊戯王で知った
碩学 図書館の魔女で知った
交叉
諒とする 図書館の魔女で知った
妾(わらわ)
幽か
珊瑚
動物としても好きだし、字が体を表しているのも好き
奇譚 「譚」の字がいい
鎖す(とざす)
極光
詳らか
初音 ミク
飛鳥
水鏡
睡蓮
磐座
祝詞
神託 「オラクル」もかっこいい
言祝ぐ
神籬(ひもろぎ)
巫(かんなぎ ダイパで知った
依り代
宸翰 図書館の魔女で知った
篝(かがり) ルビサファで知った
真砂 ダイパで知った
辰砂 宝石の国で知った
水底(みなそこ) 静かな感じの響きで好き
静謐
認める(したためる)
言葉(ことのは) 裏表ラバーズで知った
問わず語り シャナで知った
めだかボックスで知った
薄墨色 草枕で知った
銀箭 草枕で知った
聖闘士星矢で知った
天鵞絨 ポケモンで知った。漢字がかっこよすぎる
渺々 シャナで知った
あえかな
星辰
弑逆
天蓋
こそ+已然形で逆接になるやつ 「こそあらめ」とか好き
あわい
なかんずく
散華
徒花
破暁 シャナで知った
斑鳩

AtCoder試験管 典型・面白い問題集

典型っぽいのと面白いの。 随時追加。

C - LCM 111

C - エックスオア多橋君

D - Chaotic Polygons

D - 偶数メートル

C - アットコーダー王国の交通事情

C - 億マス計算

C - 茶碗と豆

C - 高橋王国の分割統治

D - 注文の多い高橋商店

C - 蛍光灯

C - A mod B Problem

C - 高橋君、24歳

C - 器物損壊!高橋君

D - トランプ挿入ソート

D - 禁止された数字

D - サプリメント

D - バレンタインデー

D - LCM Rush

D - 射撃王

C - 双子と○×ゲーム

D - ナップサック問題

D - 食塩水

D - 塗り絵

D - プレゼント

D - 道路の老朽化対策について

D - 徒競走

B - ドキドキデート大作戦高橋君

D - GCD区間

D - 道を直すお仕事

ARC114-C Sequence Scores 解説

問題リンク

C - Sequence Scores

問題概要

 1 以上  M 以下の整数からなる長さ  N の数列  A に対して、 f(A) を、すべての要素が  0 である長さ  N の数列  X に以下の操作を繰り返して  A を得るのに必要な最小の操作回数とする。

  • 整数  l, r\ (1\le l \le r \le N) と、正整数  v \le M を1つ選び、各  X_i\ (l \le i \le r) \max(X_i, v) で置き換える。

ありうる  M^N 通りの  A すべてに関する  f(A) の和を \mod 998244353 で求めよ。

思考過程

こういう「ありうるすべての○○についての総和」みたいな問題は、まとめて数え上げられることの方が多い気がする。 A_i の位置に  x を追加したとき、操作回数が増えるのは、

  1. これまでに  x が使われていない場合。
  2. これまでに  x が使われたが、その後  x より小さい数字が使われている場合

の2パターンに分けられる。 i, x を固定し、それぞれを丁寧に数える。

パターン1

 A_i = x かつ、すべての  j \lt i について  A_j \neq x であるような  A の数は、

 (M-1)^{i-1}M^{N-i}

に等しい。

パターン2

ある  k \lt i が存在して  A_k = x であり、かつ、ある  l\ (k \lt l \lt i) が存在して  A_l \lt x となるような  A の数を求める。 A_j = x\ (j \lt i) である最大の  j の値(これを  k とおく)で場合分けをする。 k を固定したとき、

  •  j \lt k, i \lt j については  A_j は自由に決められる。
  •  A_k,\ A_i は仮定より  x に等しい。
  •  k \lt j \lt i については、「『すべての  j について  A_j \ge x 』でなく、かつすべての  j について  A_j \neq x である」ものを数えればいい。

また、これらは互いに独立に決められるので、 k を固定したときのパターン数は、

 \displaystyle{M^{k-1}\cdot ((M-1)^{i - k - 1} - (M - x) ^ {i - k - 1})\cdot M^{N - i}}

に等しい。

解法

あとは上の2式の  i, x, k に関する総和を取ればよい。このままだと  O(N^2 M) かかってしまうが、  k に関する和は等比数列の和の公式を使って以下のようにまとめられるので、 O(NM) で解ける。


\begin{aligned}
&\sum_{k = 1}^{i - 2} M^{k-1}\cdot ((M-1)^{i - k - 1} - (M - x) ^ {i - k - 1})\\ 
&= \sum_{k = 1}^{i - 2} \frac{M^k}{M} \cdot \left( \frac{(M-1)^{i-1}}{(M-1)^{k}} -\frac{(M-x)^{i-1}}{(M-x)^k} \right) \\
&= \sum_{k = 1}^{i - 2} \left(\frac{(M-1)^{i-1}}{M} \cdot \left(\frac{M}{M-1}\right)^k - \frac{(M-x)^{i-1}}{M} \cdot\left(\frac{M}{M-x}\right)^k \right) \\
&= \frac{(M-1)^{i-1}}{M} \cdot \frac{M}{M-1} \cdot \frac{1 - \left(\frac{M}{M-1}\right)^{i-2}}{1 - \frac{M}{M-1}} -  \frac{(M-x)^{i-1}}{M} \cdot\frac{M}{M-x}\cdot\frac{1 - \left(\frac{M}{M-x}\right)^{i-2}}{1 - \frac{M}{M-x}} \\
&= (M - 1)^{i - 2}\cdot \frac{1 - \left(\frac{M}{M-1}\right)^{i-2}}{1 - \frac{M}{M-1}} - (M-x)^{i-2} \cdot \frac{1 - \left(\frac{M}{M-x}\right)^{i-2}}{1 - \frac{M}{M-x}}
\end{aligned}

実装

TLがやや厳しめで、毎回累乗や逆元を計算していると間に合わないので、前計算が必要だった(1146ms)。

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

int main(){
    int n, m; cin >> n >> m;

    if(m == 1){
        cout << 1 << '\n';
        return 0;
    }

    //逆元の前計算
    vector<mint> inv(5010, 0);
    for(int i = 1; i < 5010; i++){
        inv[i] = mint(i).inv();
    }

    //累乗の前計算
    vector<vector<mint>> pow(5010, vector<mint>(5010, 0));
    for(int i = 0; i < 5010; i++){
        mint p = 1;
        for(int j = 0; j < 5010; j++){
            pow[i][j] = p;
            p *= i;
        }
    }

    //1 - (m/(m-i))^jの前計算
    vector<vector<mint>> r(5010, vector<mint>(5010));
    for(int i = 1; i < m; i++){
        mint t = 1, u = inv[m-i] * m;
        for(int j = 0; j <= n; j++){
            r[i][j] = 1 - t;
            t *= u;
        }
    }
    for(int j = 0; j <= n; j++) r[m][j] = 1;

    //r[i][j]の逆元の前計算
    vector<mint> rInv(5010);
    for(int i = 0; i < 5010; i++){
        if(r[i][1] == 0) continue;
        rInv[i] =  r[i][1].inv();
    }
    
    mint ans = 0;
    for(int i = 1; i <= n; i++){
        for(int x = 1; x <= m; x++){
            ans += pow[m-1][i-1] * pow[m][n-i];
            if(i <= 2) continue;
            ans += pow[m-1][i-2] * r[1][i-2] * rInv[1] * pow[m][n-i];
            ans -= pow[m-x][i-2] * r[x][i-2] * rInv[x] * pow[m][n-i];
        }
    }

    cout << ans.val() << '\n';
}

感想

考察自体はすんなり行けたが、添字合わせや定数倍高速化でものすごく時間を取られた。

ARC124-D Yet Another Sorting Problem 解説

D - Yet Another Sorting Problem

問題概要

 \{1, \ldots, N + M\} の順列  p = (p_1, \ldots, p_{N+M}) が与えられる。 i, j\ (1\le i \le N, 1\le j \le M) を選び、 p_i p_{N+j} をswapする操作を任意の回数行う。順列を  (1, \ldots, N+M) にソートするために必要な操作の最小回数を求めよ。

思考過程

 p_1, \ldots, p_N p_{N+1}, \ldots, p_M を左右に分けてサンプル2を書いてみる。順列なので、とりあえずサイクルごとに色分けして矢印を引いてみた。それぞれのサイクルが何回の操作で元に戻せるかをみると、左右にまたがったサイズ  r のサイクル(タイプ1と呼ぶ)は  r - 1 回の操作で正しい位置に戻せるが、サンプル2における  \{8, 10\} のように、右側(あるいは左側)の頂点だけからなるサイクル(タイプ2と呼ぶ)は解消に  r + 1 回かかることがわかる。タイプ2のサイクルの解消過程は、もう片側の頂点を含むようなサイズ  s のサイクルと辺を交換してタイプ1のサイクルに変化させ、 r + s - 1 回かけてそれを解消するということをしている。タイプ2のサイクルたちをどのように解消すれば回数を減らせるかを考えると、タイプ2のサイクルが両側にある場合、それらの間で辺を交換することで、 1 + (s + r - 1) 回で2つのサイクルが解消できて、これがもっとも経済的に見える。

結局、

  • 両側にタイプ2のサイクルがある限り、それらの間で辺を交換してタイプ1のサイクルに変換する。
  • タイプ1のサイクルをすべて解消する。
  • 残ったタイプ2のサイクルをすべて解消する。

という戦略を考えた。この戦略の最小性の証明はできなかったが、合ってそうだったので提出したら通った。証明は公式解説が分かりやすい。

実装

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m; cin >> n >> m;
    vector<int> p(n + m);
    for(int i = 0; i < n + m; ++i){
        cin >> p[i];
        p[i]--;
    }
    vector<int> seen(n + m, 0);
    vector<vector<int>> cycles;
    for(int i = 0; i < n + m; ++i){
        if(seen[i]) continue;
        int now = i;
        vector<int> temp;
        while(!seen[now]){
            seen[now] = true;
            temp.push_back(now);
            now = p[now];
        }
        cycles.push_back(temp);
    }
    vector<vector<int>> left, right, both;
    for(auto c : cycles){
        if(c.size() == 1) continue;
        bool l = false, r = false;
        for(int i : c){
            if(i < n) l = true;
            if(i >= n) r = true;
        }
        if(l and r) both.push_back(c);
        else if(l) left.push_back(c);
        else right.push_back(c);
    }
    int ans = 0;
    for(auto c : both) ans += c.size() - 1;
    for(auto c : left) ans += c.size() + 1;
    for(auto c : right) ans += c.size() + 1;
    ans -= 2 * min(left.size(), right.size());
    cout << ans << '\n';
}

感想

公式解説の証明思いつける気がしないので、これ本番中に解いた人はどうやって正当性を示したか教えてほしいです。

日記 2021/09/18

昨日の日記を書いたあと、寝ようとしたら敷布団を干しっぱなしにしていた。ベランダの窓を開けると雨がざんざか降ってて布団がびっしょびしょになっててすべてが嫌になったので、ベランダの庇の下に取り込んで適当に放置した。

仕方ないので掛布団と毛布を床に敷いて寝たら、固い。起きてもなんか疲れが取れていなくて最悪だった。

夕方までの記憶マジでない。なにしてたっけ? 整数論とか近似アルゴリズムとか勉強してた気がする。一般の巡回セールスマン問題には多項式時間近似アルゴリズムが存在しない(ハミルトン閉路問題が解けてしまうため)が、三角方程式を満たす辺長のグラフなら2-近似アルゴリズムが設計できる、というのが面白かった。

ABC-Fを1問解いた。

F - Distributing Integers atcoder.jp

解法と感想(クリックで展開)

全方位木DPをやる問題。しばらく前に理論を勉強したので、何も見ずに実装できるか挑戦してみた。少しバグらせたが、全体としてはスムーズに実装できた。全方位木DPを学んだときは、こんなものが  O(N) で計算できるのかと驚いた記憶があって、かなりお気に入りのアルゴリズム


21時からABC219に出た。54分5完、274位。 Aは面倒だったのでupper_boundで求めた。Bはやるだけ。Cはソートの比較関数を実装する。Dはナップサック問題のアレンジ。個数が  X, Y 以上になるものを  X, Y にまとめる。Eは面倒だった。堀の内部に入れる位置をbit全探索する。堀の内部が連結で、かつ穴がなければOK。穴がないかの判定はすべての0が外周の0から到達できるかをBFSで調べた。自分が実装している最中に、ほとんど解法を教えているようなclarが公開されてかなりびっくりした。聞く側はあのように聞くしかないだろうが、そのまま公開するのはどうなんだろう……? Eを通したあと、順位表を見てFより解かれていたGを考えたが解けなかった。解説を読むと平方分割で解くらしい。平方分割を使う問題は一度も解いたことがないので、これは無理だったと思う。終了後のTLを見ると、どうも典型90問でほとんど同じ解法の問題が既出だったらしい。勉強不足を咎められて反省。典型90問は埋めよう埋めようと思って放置している状態が続いている。

パフォは2088で、レートは1692から1738に上がった。ここ3回ABCで黄パフォを出せていてとてもいい。もう一段実力が伸びれば黄色になれそうな気がしている。明日のARCも温まりたい。

23:35からCodeforces Round #743 Div. 2に出た。A問題のジャッジに一万年くらいかかっていて、案の定30分くらい経ってunratedになった。C問題までは通したので解法を書く。Aは1の位の数を0にしたあと、各桁とswapして減らしていく。Bはよくわからなかったので、 A の先頭を固定してセグ木上の二分探索で  B の先頭を求めた。Cは閉路判定をしたあとDAGの最長パスを求める。番号が小さい頂点から大きい頂点へは遷移する必要がない。Dは後ろから見る貪欲を投げたが落ちてしまった。TLを見るに累積xorを使ってどうにかするらしい。01列で累積xorを考えるのは何回か見たのに自分の典型引き出しに入っていなかったので、以降意識することにする。upsolveは明日。

こどふぉがunratedになったので高校同期と通話しながらコードネームをやった。今日は全体的に荒れてて楽しかった。

f:id:Focus_Sash:20210919031154p:plain
ねしゃ~がヤバかった回

ちなみに想定解は「オブラート」。どっちもどっち。

寝る。

日記 2021/09/17

今日はなぜか朝7時に起きた。やよい軒で朝食を食べたら満腹になって二度寝してしまった。13時ごろ起きて少し問題を考察したあと、14時半に家を出て本郷キャンパス圏論のゼミに出席した。院試のせいで中断していた圏論ゼミだが、今日から再開。『Category Theory in Context』最後の第6章に入った。今日はKan拡張の導入パートで、いまいちモチベーションが分からなかったところもあったが、どうやら先々の伏線になっているらしい。

ゼミが終わったあと学科同期と駄弁り、図書館でいくつか本を借りたのち帰宅した。家の近くに新しくラーメン屋が開店していることに気がついた。開店記念サービスで500円かつライス無料らしい。ちょうど夕食に悩んでいたこともあって、ものは試しと入ってみた。

まず、うるさい。開店直後で気合が入っているのかもしれないが、狭い店内で5、6人が頻繁に叫ぶとさすがにうっとうしい。そして色々と雑。注文を間違って覚えていたり、料理を出す順番を間違えたりと、何人かの客が迷惑を被っていたのを見た。自分が店に滞在していた短時間でこれだけトラブルがあるのは、部外者としても大丈夫なのかと心配になる。これは完全な憶測だが、店員どうしがやけに親しげなことを見るに、この店はなにかの内輪で運営されていて、「文化祭」的なノリが残ってしまっているのだと思う。まあ開店したばかりだし、良い人たちではあると思うので、この先頑張ってほしい。あと、頼んだライスが一瞬で渡されて、しかもパサパサしてて温かくもなかったんだけど、あれ注文前によそってあったのをそのまま出してるよね? それヤバくない?

ちなみにラーメン自体の味は可もなく不可もなく、という感じだった。この店で食べるくらいなら本郷の『にし乃』や『ねむ瑠』に行くので、もう二度と入ることはないだろう。

家に帰ってからABC-Fを2問解いた。どちらも数え上げ。

F - Enclosed Points atcoder.jp

解法と感想(クリックで展開)

簡単。各  i について、点の部分集合  S\subset T であって、点  (x_i, y_i) S のminimum bounding boxに含まないようなものの個数を求めればよい。これは  x_j > x_i である点のなす部分集合、 y_k > y_i である点のなす部分集合の数の和から、  x_l > x_i, y_l > y_i である点のなす部分集合の数を引く、ということを4方向についてやればよい。 x_l > x_i, y_l > y_i であるような点の数は、 x 座標でソートしてこれまでに出現した  y 座標の値をBITで管理すれば求まる。BITで集合を管理することがかなり多いので、insert(x)get_kth_element()などのインターフェースをライブラリに加えてみた。集合に対する操作が直感的になってうれしい(大差ない気もする)。


F - Surrounded Nodes atcoder.jp

解法と感想(クリックで展開)

これも難しくない。ある頂点  v を白に固定したとき、部分集合  S\subset V であって、 S を含む最小の部分木が  v を含むようなものの個数を求めればいい。これは、 v を根とみたときの  v の子の部分木のサイズを  r_1, \ldots, r_k として、 2^{N - 1} - \sum 2^{r_i} + k - 1 で求まる。すべての頂点について、その頂点を根とみたときの子の部分木のサイズを求める必要があるが、これは全方位木DPっぽくやると O(N) で求まる。


21時からyukicoder contest 314に出た。4完40位。 Aでめちゃくちゃ詰まった。丁寧に場合分けすると、答えが閉じた式で書ける。Bは簡単で、 A_1 以外から始まる項は+-ですべて打ち消すので、 A_1 から始まる  N 個のありうる項すべてについて出現回数を足せばいい。Cは面白い。 x_i = \frac{1-p_i}{p_i} と置くと、 P(\mathrm{even}) - P(\mathrm{odd}) = \prod (1 - x_i) となる。これが負になればいい。確率ちょうど  1/2 のコインを入れてしまうと、そのうち表が出た個数のパリティで全体のパリティが決まってしまうので、他をどう選ぼうとアリスの勝率は  1/2 にしかならず、不適。よって、 x_i > 1 であるようなコインを奇数個、 x_i \lt 1 であるようなコインを任意個選ぶ場合の数が答え。Dは複雑に見えて一本道の問題。制約が小さいので、 x 軸正方向に進む回数を全探索する。これを固定すると、それぞれの方向に進む回数が一意に定まる。あとは重複組合せを使って、それぞれの回数を分配すればいい。どうしても1ケースだけ通らず、8ペナも出してしまった。

AとCとDに時間を取られた。考察はほとんどできていても、細かい式変形が間違っていて無駄足になったり、バグらせたりで解くのが遅い(こどふぉが苦手なのもこれが主要因)。どうしたらいいんすかね。前者はサンプルの計算を同時にすれば軽減できそうだが、後者は……? 真面目に「バグを減らす方法」を模索しないと。