Firmianaの落書き

プログラミング関係のことを中心に書きます（多分）

【LaTeX】改ページできるitembox環境をtcolorboxで作る

LaTeX

よく考えたら \mathrm{\LaTeX}に記事のネタが色々転がっていることに気付いたので、書きます。

さて、ascmacパッケージが提供するitembox環境は、シンプルな見た目で使い勝手はよいものの、長大な範囲を囲んでしまうとページからはみ出してしまう問題がありました。

ページ番号に被る＋用紙からはみ出している

ところで、tcolorboxパッケージが提供するコマンド\newtcolorboxと、ライブラリbreakableを使えば、改ページ可能なtcolorbox環境を作ることができます。これを使ってitembox環境を極力再現することを考えました。軽く調べると「ちゃんと動かない例」はでてきますが、案外やっている人がいないように見受けられたので、ある程度説明を入れつつ書いてみます。やばいところがあればコメントでもTwitterのDMからでも教えてください。

結論

次のxitembox環境を作成しました。

\usepackage{tcolorbox}
\tcbuselibrary{breakable, skins}
\newtcolorbox{xitembox}[2][]{
  empty, breakable=true,
  left=6pt, right=6pt, top=2pt, bottom=6pt,
  colframe=black, colback=white, coltitle=black,
  borderline={.8pt}{0pt}{black},
  title={#2},
  \ifx#1lattach boxed title to top left%
  \else%
    \ifx#1rattach boxed title to top right%
    \else attach boxed title to top center%
    \fi%
  \fi%
  ={yshift=-\tcboxedtitleheight/2,
    yshifttext=-\tcboxedtitleheight/2,
    xshift=\ifx#1l10pt\else\ifx#1r-10pt\else0pt\fi\fi%
  },
  boxed title style={
    enhanced,
    colback=white, colframe=black!0,
    left=0pt, right=0pt
  },
  arc=10pt
}

次のように使います。

\begin{xitembox}[l]{タイトル}
中身
\end{xitembox}

実際、次画像のように、itemboxに近い見た目で、かつ自動で改ページされます。

以下、雑に説明していきます。

枠線の形状

まずitembox環境の枠線について。itemboxを定義しているfascmac.styを確認すると、

  • 枠線の太さは0.8pt (.8pt)
  • 角の丸み (半径) は10pt

になっていることが分かります。これらは、

borderline={.8pt}{0pt}{black},
arc=10pt

として設定しています。borderlineオプションは、第1引数に線の太さ、第2引数に「枠線をどれだけ内側にずらすか」、第3引数に線の色を指定します。今回は線の太さしか触りません。arcオプションは角の半径そのままです。

タイトルの位置と書式

続いてタイトルの位置調整について。itembox環境ではオプション引数として、lまたはrを指定することでそれぞれタイトルの左寄せ、右寄せができるようになっていました。tcolorbox自体にはこんな機能はない (多分) ので、 \mathrm{\TeX}の条件分岐を使用して、必要なオプションを指定することにします。

まず、tcolorboxのtitleの位置を指定したいときは、

attach boxed title to ~~~={options}

をtcolorbox環境、または\newtcolorboxの引数に渡す必要があります。~~~には、上中央揃えならtop center、上左隅揃えならtop left、上右隅揃えならtop rightが入ります。条件分岐により、これらのオプションを使い分けてあげればよいです。コードは以下の通り。

\ifx#1lattach boxed title to top left%
\else%
  \ifx#1rattach boxed title to top right%
  \else attach boxed title to top center%
  \fi%
\fi%
={yshift=-\tcboxedtitleheight/2,
  yshifttext=-\tcboxedtitleheight/2,
  xshift=\ifx#1l10pt\else\ifx#1r-10pt\else0pt\fi\fi%
},

随分大層なことになっていますが、やっているのは前述した「オプションの選択」と、「横方向の調整」のみです。第1引数が位置の指定になっているので、文字列比較による条件分岐\ifxを使って条件分岐を行っています。lとr以外が入力されたらすべて中央揃え扱いにします。これでいいのかはさておき。

後半はxshiftでの横方向の調整を行っています。何もしないとtcolorboxの端に揃ってしまうため、itemboxの見た目に近づけるには、少なくとも角の半径以上内側にずらす必要があります。yshiftとyshifttextに関しては、縦方向の調整を行っているのみで、lやらrやらに依らず一定として問題ありません。

なお、このままだとタイトルに枠線が被ってしまうため、以下のようにタイトルの背景を白にして枠線を隠しています。

boxed title style={
  enhanced,
  colback=white, colframe=black!0,
  left=0pt, right=0pt
},
その他
  • itemboxの方が初期状態のtcolorboxより余白が少ないため、left,right,top,bottomのところで詰めてあります。

以上。

OMC246 参加記 (という名の解法記事)

OMC という名の解法記事

***
Firmiana です。今回はさっき終わった OMC246 の解法記事です。レートが 1800 を割りましたがまだなんとか息はしています。

今回の戦略

特になし (未証明エスパーはしないようにした)

文字実況

  1. コンテスト開始 (0分)
  2. A問題 1を忘れてペナ (15分)
  3. A問題CA (16分)
  4. B問題で沼る (30分)
  5. C問題を見るが解けない (45分)
  6. D問題を見るが解けない (55分)
  7. B問題でごり押しに走りCA (63分)
  8. E,F問題を見るが解けない (80分)
  9. コンテスト終了 (100分)

解法

A問題 (整数/200点)

onlinemathcontest.com

2\times 3\times 5\times 7=140>40 なので、 n の相異なる素因数は高々 3 つ。

(i) n=1 のとき、 d(1)=1, \varphi(1)=1 ゆえ 1+1=1+1 より適する。

(ii) n=p^a\ (p\in\mathbb{P}, a\in\mathbb{N}) のとき、 d(p^a)+\varphi(p^a)=(a+1)+(p^a-p^{a-1})=(n+1)+(a-p^{a-1})=n+1 ゆえ a=p^{a-1} が成り立つ。 a=1 のとき p は任意。 a\geq 2, p\geq 3 のとき、 \dfrac{\mathrm{d}}{\mathrm{d}a}\left(p^{a-1}-a\right)=\log{p}\cdot p^{a-1}-1>1\cdot 3^1-1=2>0 と \left.p^{a-1}-a\right|_{a=2}=p-2\geq 1>0 より p^{a-1}>a となるので不適。よって a=p=2、すなわち n=4 のみであり、これは適する。

(iii) n=p^aq^b のとき、考えられる a,b,p,q の組み合わせはそんなにないので全部書くと、すべて不適。

(iv) n=p^aq^br^c のとき、 n=30 のみで、これは不適。

以上より解答すべきは 1 と 40 以下の素数の総和であり、これは \mathbf{202} である。

B問題 (代数/200点)

onlinemathcontest.com

とりあえず与式を展開すると 283+2\{\sin{\theta}(21\cos{\phi}+36)+\cos{\theta}(21\sin{\phi}+27)+63\sin{\phi}+84\cos{\phi}\} となる。中括弧内を f(\theta,\phi) とおいて \theta で偏微分すると \dfrac{\partial f(\theta,\phi)}{\partial \theta}=\cos{\theta}(21\cos{\phi}+36)-\sin{\theta}(21\sin{\phi}+27) であり、 f(\theta,\phi) が最大値を取るときこれが 0 となるので、 \tan{\theta}=\dfrac{21\cos{\phi}+36}{21\sin{\phi}+27} が成り立つ。 (21\cos{\phi}+36)^2+(21\sin{\phi}+27)^2=2466+378(3\sin{\phi}+4\cos{\phi}) ゆえ、 \sin{\theta}=\dfrac{21\cos{\phi}+36}{\sqrt{2466+378(3\sin{\phi}+4\cos{\phi})}}, \cos{\theta}=\dfrac{21\sin{\phi}+27}{\sqrt{2466+378(3\sin{\phi}+4\cos{\phi})}} が成り立つ。これを f(\theta,\phi) の式に代入すると f(\theta,\phi)=\dfrac{(21\cos{\phi}+36)^2+(21\sin{\phi}+27)^2}{\sqrt{2466+378(3\sin{\phi}+4\cos{\phi})}}+21(3\sin{\phi}+4\cos{\phi})=\sqrt{2466+378(3\sin{\phi}+4\cos{\phi})}+21(3\sin{\phi}+4\cos{\phi}) となる。ここで、 3\sin{\phi}+4\cos{\phi}=5\sin{(\phi+\alpha)} なる \alpha が存在するので、 3\sin{\phi}+4\cos{\phi} の最大値は 5 であり、 g(x)=\sqrt{2466+378x}+21x とおくと g^\prime(x)=\dfrac{189}{\sqrt{2466+378x}}+21>0 ゆえ、 g(x) の最大値は x=5 のとき与えられる。この値は \sqrt{2466+378\times 5}+21\times 5=171 より、求める最大値は 283+2\times 171=\mathbf{625} となる。


C以降はもはや場所を取る意味がないので書きません、いつか解けたら追加します

感想

なんか主観難易度付けるの怠くなっちゃったのでやめます ()

OMC245 参加記 (という名の解法記事)

OMC という名の解法記事

***
Firmiana です。今回はさっき終わった (double meaning) OMC245 の解法記事です。

今回の戦略

特になし

文字実況

  1. コンテスト開始 (0分)
  2. A問題CA (8分)
  3. B問題で沼る (45分)
  4. C問題に移り解くが勘違い (49分)
  5. C問題修正 CA (61分)
  6. D問題勘違いで解けない (86分)
  7. D問題修正を試みるが悉く計算ミス (97分)
  8. コンテスト終了 (100分)

解法

A問題 (代数/100点)

onlinemathcontest.com

x,y は整数部分のみに制約があり、小数部分は任意である。それぞれの整数部分を a,b と置くと、 a+10b=30 が成り立つ。 a,b はいずれも非負整数なので、 (a,b)=(0,3),(10,2),(20,1),(30,0) のみが適する。

ここで、 a\leq x\lt a+1, b\leq y\lt b+1 であるから ab\leq xy\lt (a+1)(b+1) であって、 x,y は実数なので xy はこの範囲のすべての実数を取ることができる。ゆえに a,b を決めたとき、 xy が取りうる最大の整数値は (a+1)(b+1)-1 であることが分かる。先程求めた組 (a,b) それぞれについて、 (a+1)(b+1)-1=3, 32, 41, 30 であるから、求める最大値は \mathbf{41} となる。

本番中のメモ (A問題)
B問題 (整数/300点)

onlinemathcontest.com

解けませんでしたが途中まで書いておきます。

pq が平方数かどうか、すなわち p=q かどうかで場合分けを行う。

1. p=q のとき、 pq(2p+q+16)=p^2(3p+16) である。よって 3p+16=n^2 を満たすような素数 p と正整数 n の組を求めればよい。とりあえず p=2 は不適。以降 p\geq 3 として、

\displaystyle 3p+16 = n^2 \\ \Leftrightarrow 3p = (n+4)(n-4)

であるから、 3\leq p に注意して (n+4,n-4)=(3p,1),(p,3) の 2 通りのみとなる。それぞれ計算すれば (p,n)=(3,5),(11,7) が適する。

2. p\neq q のとき…………はい以上になります。ここから嘘議論なので書きません。気になる人は画像を見ろ。

本番中のメモ (B問題) 右側は嘘です
C問題 (組み合わせ/300点)

onlinemathcontest.com

0 超過 401 未満の平方数は 1^2, 2^2, \cdots, 20^2 の 20 個である。 a_1, a_2, \cdots , a_{20} それぞれの間は 19 個であるから、この 20 個の平方数のうちちょうど 1 つが a_n のいずれかと一致する。また、 a_2=1^2, a_{19}=20^2 とはならないので、考えるべきは 2\leq n\leq 19 について a_n=n^2 となる場合だけである。

n=k の場合を考えると、先頭から順に

\displaystyle a_1\lt 1^2\lt a_2\lt \cdots\lt a_{k-1}\lt (k-1)^2\lt a_k=k^2\lt (k+1)^2\lt a_{k+1}\lt \cdots \lt a_{19}\lt 20^2\lt a_{20}

となる。このとき a_1, a_k, a_{20} 以外の a_i は独立に動かせるから、この場合考えられる場合の数は

\displaystyle (2^2-1^2-1)\cdots((k-1)^2-(k-2)^2-1)((k+2)^2-(k+1)^2-1)\cdots (20^2-19^2-1) \\ = \displaystyle\prod_{i=1}^{k-2} ((i+1)^2-i^2-1) \times \prod_{i=k+1}^{19} ((i+1)^2-i^2-1) \\ = \displaystyle\prod_{i=1}^{k-2} (2i) \times \prod_{i=k+1}^{19} (2i) \\ = \dfrac{\prod_{i=1}^{19} (2i)}{2(k-1)\times 2k} \\ = \dfrac{2^{17}\times 19!}{(k-1)k}

で与えられる。よって総和を取れば望遠鏡和となるので、

\displaystyle \displaystyle\sum_{k=2}^{19} \dfrac{2^{17}\times 19!}{(k-1)k} \\ = 2^{17}\times 19!\left(1-\dfrac{1}{19}\right) \\ = 2^{34} 3^{10} 5^3 7^2 11^1 13^1 17^1

となる。したがって、解答すべきは 35\times 11\times 4\times 3\times 2^3=\mathbf{36960} となる。

本番中のメモ (C問題) 雑にやるからこうなる
D問題 (代数/400点)

onlinemathcontest.com

m,n を 3 以下の正整数、 a,b を a\neq \pm b かつ 0 でない整数とする。条件より f(x)-g(x)=a(x-1)^m, f(x)+g(x)=b(x+1)^n が成り立つから、 f(x)=\dfrac{1}{2}\left\{a(x-1)^m+b(x+1)^n\right\}, g(x)=\dfrac{1}{2}\left\{-a(x-1)^m+b(x-1)^n\right\} が成り立つ。 これより \max{(a,b)}=3 であることが分かる。さらに f(0)g(0)=\dfrac{\{(-1)^ma+b\}\{-(-1)^ma+b\}}{4}=\dfrac{(b-a)(b+a)}{4}=16 より (b-a)(b+a)=64 が成り立つ。

1. m=n=3 のとき、

\displaystyle f(x)=\dfrac{1}{2}\left(\cdots+(3a+3b)x+(-a+b)\right) \\ g(x)=\dfrac{1}{2}\left(\cdots+(-3a+3b)x+(a+b)\right)

であるから f(x)g(x) の x の係数は

\displaystyle \dfrac{1}{4}\left\{(3a+3b)(a+b)+(-3a+3b)(-a+b)\right\} \\ =\dfrac{3}{4}\left\{(b+a)^2+(b-a)^2\right\} \\ =\dfrac{3}{4}\left\{(2b)^2-2(b-a)(b+a)\right\} \\ =\dfrac{3}{4}\left(4b^2-2\times 64\right) \\ =3b^2-96

である。また、 (b-a)(b+a)=64 を満たすような b は、 \dfrac{a+b}{2}, \dfrac{b-a}{2} が整数であることに注意して実際に調べると b=\pm 10, \pm 17 しか許されないので、このときありうる係数は 204, 771 のみ。

2. m=2 のとき、 f,g の最高次係数が \dfrac{b}{2} となることより、 b は偶数である。1. の議論より、 b=\pm 10, a=\pm 6 としてよい。

\displaystyle f(x)=\dfrac{1}{2}\left(\cdots+(-2a+3b)x+(a+b)\right) \\ g(x)=\dfrac{1}{2}\left(\cdots+(2a+3b)x+(-a+b)\right)

であるから、 f(x)g(x) の x の係数は

\displaystyle \dfrac{1}{4}\left\{(-2a+3b)(-a+b)+(2a+3b)(a+b)\right\} \\ =\dfrac{1}{4}\left\{(a-3a+3b)(-a+b)+(-a+3a+3b)(a+b)\right\} \\ =\dfrac{1}{4}\left\{a(-a+b)-a(a+b)\right\}+3b^2-96 \\ =-\dfrac{a^2}{2}+3b^2-96

となる。 a^2=36, b^2=100 を代入して、このときは -18+300-96=186 のみが適する。

3. m=1 のとき、2. と同様に b=\pm 10, a=\pm 6 である。

\displaystyle f(x)=\dfrac{1}{2}\left(\cdots+(a+3b)x+(-a+b)\right) \\ g(x)=\dfrac{1}{2}\left(\cdots+(-a+3b)x+(a+b)\right)

であるから、 f(x)g(x) の x の係数は

\displaystyle \dfrac{1}{4}\left\{(a+3b)(a+b)+(-a+3b)(-a+b)\right\} \\ =\dfrac{1}{4}\left\{(-2a+3a+3b)(a+b)+(2a-3a+3b)(-a+b)\right\} \\ =\dfrac{1}{4}\left\{-2a(a+b)+2a(-a+b)\right\}+3b^2-96 \\ =-a^2+3b^2-96

となる。 a^2=36, b^2=100 を代入して、このときは -36+300-96=168 のみが適する。

4. n=2 のとき、2. と同様に b=\pm 10, a=\pm 6 である。

\displaystyle f(x)=\dfrac{1}{2}\left(\cdots+(3a+2b)x+(-a+b)\right) \\ g(x)=\dfrac{1}{2}\left(\cdots+(-3a+2b)x+(a+b)\right)

であるから、 f(x)g(x) の x の係数は

\displaystyle \dfrac{1}{4}\left\{(3a+2b)(a+b)+(-3a+2b)(-a+b)\right\} \\ =\dfrac{1}{4}\left\{(3a+3b-b)(a+b)+(-3a+3b-b)(-a+b)\right\} \\ =\dfrac{1}{4}\left\{-b(a+b)-b(-a+b)\right\}+3b^2-96 \\ =-\dfrac{b^2}{2}+3b^2-96

となる。 b^2=100 を代入して、このときは -50+300-96=154 のみが適する。

5. n=1 のとき、2. と同様に b=\pm 10, a=\pm 6 である。

\displaystyle f(x)=\dfrac{1}{2}\left(\cdots+(3a+b)x+(-a+b)\right) \\ g(x)=\dfrac{1}{2}\left(\cdots+(-3a+b)x+(a+b)\right)

であるから、 f(x)g(x) の x の係数は

\displaystyle \dfrac{1}{4}\left\{(3a+b)(a+b)+(-3a+b)(-a+b)\right\} \\ =\dfrac{1}{4}\left\{(3a+3b-2b)(a+b)+(-3a+3b-2b)(-a+b)\right\} \\ =\dfrac{1}{4}\left\{-2b(a+b)-2b(-a+b)\right\}+3b^2-96 \\ =-b^2+3b^2-96

となる。 b^2=100 を代入して、このときは -100+300-96=104 のみが適する。

以上より、適するものは 104, 154, 168, 186, 204, 771 であり、解答すべきはこれらの総和 \mathbf{1587} となる。

本番中のメモ (D問題)
E問題 (幾何/500点)

onlinemathcontest.com

見てない

F問題 (整数/500点)

onlinemathcontest.com

見てない

感想

……………………

主観難易度

A問題

難易度

5

VERY EASY

  • 整数部分だけ制約があって、小数部分は自由であることに気付けばOK

B問題

一応解いたので書きます

難易度

25

NORMAL

  • 難しい 謎不等式評価が見えなければほぼ詰みだと思う
  • ↑とか書きましたが pq がデカくなるから上から抑えに行くのは当然ゆえ下げた

C問題

難易度

20

EASY

  • ちょっと見えにくいが実際に書いてみれば解ける
  • とりあえず書いてから詰めた方がいいかも

D問題

難易度

35

NORMAL

  • 計算重すぎるのでやや高め
  • 工夫すれば減らせはするが……

E問題

解けていないので主観難易度は設定しません

F問題

解けていないので主観難易度は設定しません

OMCB039 参加記 (という名の解法記事)

OMC という名の解法記事

***
Firmiana です。爆死して悲しいです。引退か？

今回の戦略

  • 潜伏 : 全問題答えを出せるまで提出せず、残り時間が少なくなるか全問解けるかし次第一気に提出する。(なお途中で撤回)
  • エスパー禁止 : 理詰め縛り。戦略というよりはペナ削減狙い。
  • 順序 : 4b くらい前から解け。

文字実況

  1. コンテスト開始 (0分)
  2. A 問題を解く (2分)
  3. B 問題を沼りながら遠回り解法で解く (19分)
  4. C 問題を解く (25分)
  5. D 問題で嘘漸化式を立てまくり大量ロス (46分)
  6. 一旦ABCを提出、すべてCA (47分)
  7. D 問題撤退 (55分)
  8. E 問題本質に気付く (59分)
  9. コンテスト終了 (60分)
  10. E 問題CA (61分)

解法

A問題 (整数/100点)

onlinemathcontest.com

p+q+r=36 より p,q,r のいずれか 1 つ以上は偶数ゆえ、 p=2、よって q+r=34 。 17\lt r\lt32 に注意して調べれば r=23,29,31 が適する。よって解答は 23+29+31=\mathbf{83} となる。

本番中のメモ (A問題)
B問題 (幾何/200点)

onlinemathcontest.com

CE=DE より \triangle{CDE} は二等辺三角形。よって \angle{CDE}=\angle{DCE} ゆえ \angle{BDE}=\angle{BCE} より \angle{BDC}=\angle{BCD} となり、これより \triangle{BCD} は BC=BD なる二等辺三角形。ここで AD=x とおき、 BE が \angle{DBC} の二等分線であることを見落とすと、 BC=BD=9-x であって、 \triangle{ABC}, \triangle{ADE} に関する余弦定理より

\displaystyle \dfrac{8^2+x^2-3^2}{2\cdot 8\cdot x} = \dfrac{11^2+9^2-(9-x)^2}{2\cdot 11\cdot 9} \\ \Leftrightarrow 99(55+x^2) = -8x(x^2-18x-121) \\ \Leftrightarrow 8x^3-45x^2-968x+121\cdot 45 = 0 \\ \Leftrightarrow (x^2-121)(8x-45) = 0 \\ \therefore x = \pm 11, \dfrac{45}{8}

となる。 0\lt x\lt 9 ゆえ、 x=\dfrac{45}{8} であり、解答すべきは 45+8=\mathbf{53} となる。

本番中のメモ (B問題) 右側は100%無駄である
C問題 (代数/200点)

onlinemathcontest.com

\sin{x^\circ}=\cos{(90^\circ-x^\circ)} より、

\displaystyle \begin{aligned} \sum_{n=0}^{90} \dfrac{(\sin{n^\circ}+2)(4\sin{n^\circ}-1)}{\sin{n^\circ}+\cos{n^\circ}} &= \sum_{n=0}^{44} \dfrac{(\sin{n^\circ}+2)(4\sin{n^\circ}-1)+(\cos{n^\circ}+2)(4\cos{n^\circ}-1)}{\sin{n^\circ}+\cos{n^\circ}} + \dfrac{7}{2} \\ &= \sum_{n=0}^{44}\dfrac{4(\sin^2{n^\circ}+\cos^2{n^\circ})+7(\sin{n^\circ}+\cos{n^\circ})-4}{\sin{n^\circ}+\cos{n^\circ}} + \dfrac{7}{2} \\ &= \sum_{n=0}^{44} 7 + \dfrac{7}{2} \\ &= \dfrac{7}{2} \times 91 = \dfrac{637}{2} \end{aligned}

となる。よって解答すべきは 637+2=\mathbf{639} となる。

本番中のメモ (C問題)
D問題 (組み合わせ/300点)

onlinemathcontest.com

嘘漸化式をたくさん作った挙句解けませんでした。

本番中のメモ (D問題) 解けていない
E問題 (幾何/300点)

onlinemathcontest.com

直線 CP に関して B と同じ側に CQ=PQ=3 となるような点 Q を取ると \triangle{CPQ} は正三角形である。また、このとき AP=BP かつ \angle{APC}=\angle{BPQ} であるから、二辺夾角相当ゆえ \triangle{APC}\equiv\triangle{BPQ} である。よって BQ=AC=4 となる。

さらに、 AB の中点を M とすれば、直線 PM は \angle{CPQ} の二等分線なので、 CQ と直交する。よって AB\parallel CQ。これより四角形 ABQC は BQ=CA なる等脚台形である。 B から CQ の延長上に下ろした垂線の足を H として HQ=x とおけば、三平方の定理より BH^2=16-x^2 ゆえ 16-x^2+(x+3)^2=36 より x=\dfrac{11}{6} が成り立つ。 AB=CQ+2x なので、 AB=\dfrac{20}{3} となる。

以上より、解答すべきは 20+3=\mathbf{23} となる。

本番中のメモ (E問題) 右側は100%無駄 (2回目)
F問題 (整数/400点)

onlinemathcontest.com

見てません

感想

…………

主観難易度

A問題

難易度

5

VERY EASY

  • 数えるだけ

B問題

難易度

15

EASY

  • 私がミスっただけでそこまで難易度は高くないはずと判断

C問題

難易度

10

VERY EASY

  • 多分こうなるという素直な予想が当たる

D問題

解けていないので……

E問題

難易度

25

NORMAL

  • かなり典型だが苦手なのでこんな感じか

F問題

解けていないので……

OMC084(E) のユーザー解説 (偽)

OMC 偽ユーザー解説

***
Firmiana です。幾何を脳筋解法で解いて一撃 CA を取ることに勝る快楽はあるでしょうか、いやない (そんなことはない)。

問題

onlinemathcontest.com

主観難易度

難易度

15

EASY

  • 角の二等分線に関係する知識が必要
  • ごり押しできる
主観難易度についてはこちら

解説

公式解説では Ptolemy の定理とかいう知らない定理を使っていましたが、そんなことをしなくても解けます。スチュワートの定理の特殊な場合の等式を使用しましょう。

まず \angle{BAC} = \angle{ACB} より \triangle{ABC} は AB=BC の二等辺三角形です。また、 \angle{ADB}=\angle{ACB} と円周角の定理の逆より、 4 点 A,B,C,D は共円となります。これより \angle{BDC}=\angle{BAC}=\angle{ADB} ゆえ、直線 DP は \angle{ADC} の二等分線です。以上より、正の実数 x,y を用いて AB=BC=x, CD=8y, DA=3y と置くことができます。

長さの条件を考えると、まず AB\times CD=80 より 8xy=80、すなわち xy=10 が成り立ちます。また、 AP\times CP=24 と方べきの定理より、 BP\times DP=24 です。ここで、三角形の角の二等分線の長さに関する等式を \triangle{ADC} に適用すると、 DP=\sqrt{CD\times DA-AP\times CP}=\sqrt{24(y^2-1)} が成り立ちます。証明は外接円に関する方べきと相似により容易にできるので省略します。一応書いてある記事だけ貼っておきます。

manabitimes.jp

\triangle{ABC} について、 B から直線 AC に下ろした垂線の足を H とすれば、三平方の定理により BH=\sqrt{x^2-\dfrac{121}{4}}、さらに BP=\sqrt{x^2-24} となることが分かります。よって BP\times DP=24 より、

\displaystyle \sqrt{y^2-1}\sqrt{x^2-24}=\sqrt{24} \\ \therefore (y^2-1)(x^2-24)=24

が成り立ちます。 xy=10 より、

\displaystyle \left(\dfrac{100}{x^2}-1\right)(x^2-24)=24 \\ \Leftrightarrow (100-x^2)(x^2-24)=24x^2 \\ \Leftrightarrow x^4-100x^2+2400=0 \\ \Leftrightarrow (x^2-40)(x^2-60)=0 \\ \therefore x^2=40,60

となりました。 x^2 の取りうる値はこれ以外存在しないので、解答すべきは 40+60=\mathbf{100} です。

感想

案外シンプル？

類題

(何か見つけたら追加します)

ABC398 参加記 (という名の解法記事)

AtCoder という名の解法記事

***
Firmiana です。ABC398の解法記事です。冷えて悲しいですが書きます。

今回の戦略

特になし

文字実況

  1. 味噌汁で舌を焼いて遅刻 (6分)
  2. A問題 AC (7分)
  3. B問題 AC (8分)
  4. C問題 誤読 (11分)
  5. C問題 やっとAC (26分)
  6. D問題 解けない (40分)
  7. E問題 実装ミスTLE (44分)
  8. E問題 AC (54分)
  9. F問題 普通にWA (70分)
  10. F問題 AC (99分)
  11. 悲しい気持ちでコンテスト終了 (100分)

解法

A問題 (100点)

atcoder.jp

N が奇数のとき、出力すべきは \left\lfloor\dfrac{N}{2}\right\rfloor-1 文字の -、 1 文字の=、 \left\lfloor\dfrac{N}{2}\right\rfloor-1 文字の- をこの順に連結したもの。

N が偶数のとき、出力すべきは \left\lfloor\dfrac{N}{2}\right\rfloor-1 文字の -、 2 文字の=、 \left\lfloor\dfrac{N}{2}\right\rfloor-1 文字の- をこの順に連結したもの。

そのまま実装すれば正解できる。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  int n;
  cin>>n;
  if(n%2==0){
    for(int i=0;i<n/2-1;++i)cout<<"-";
    cout<<"==";
    for(int i=0;i<n/2-1;++i)cout<<"-";
  }
  else{
    for(int i=0;i<n/2;++i)cout<<"-";
    cout<<"=";
    for(int i=0;i<n/2;++i)cout<<"-";
  }
}
B問題 (250点)

atcoder.jp

フルハウスを作るためには、 3 枚以上ある数字が 1 つ、これ以外に 2 枚以上ある数字が 2 つ以上あればいい。数ごとに数え上げれば解ける。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  int n=7;
  vector<int> a(14,0);
  for(int i=0;i<n;++i){
    int x;
    cin>>x;
    a[x]++;
  }
  int cnt3=0,cnt2=0;
  for(int i=1;i<=13;++i){
    if(a[i]>=3)++cnt3;
    if(a[i]>=2)++cnt2;
  }
  if(cnt3>=1&&cnt2>=2) cout<<"Yes\n";
  else cout<<"No\n";
}
C問題 (300点)

atcoder.jp

map を使って A_i の重複をチェックし、重複していないものの中でインデックスが最大のものを選ぶ。私は A_i を最大化してペナった。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  int n;
  cin>>n;
  map<ll,int> a;
  for(int i=0;i<n;++i){
    ll x;
    cin>>x;
    if(a[x]==0) a[x]=i+1;
    else a[x]=-1;
  }
  int ans=-1; ll cur=0;
  for(auto i : a){
    if(cur<i.first && i.second!=-1){
      ans=i.second;
      cur=i.first;
    }
  }
  cout<<ans<<"\n";
}
D問題 (425点)

atcoder.jp

解けてないです (お帰り)

E問題 (425点)

atcoder.jp

奇数長の閉路と聞いて二部グラフを思い浮かべられれば終わり。二部グラフの異なるグループに属する 2 点の組のうち、既に結ばれていないものを全探索し vector とかで持っておく。ゲームは自分の手番でこの辺を使い切ればいいから、偶数個あるなら Second、奇数個なら First として操作を始めればいい。

First の場合は適当な組を出力しておく。

まず高橋君の解答を受け取り、-1 -1 なら終了、でなければ先程の vector から対応する組を除く (全探索可能)。続いてまだ使われていない組を出力することを繰り返す。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  int n;
  cin>>n;
  vector<vector<bool>> G(n,vector<bool>(n,false));
  for(int i=0;i<n-1;++i){
    int u,v;
    cin>>u>>v;
    --u; --v;
    G[u][v]=true;
    G[v][u]=true;
  }
  // BFS
  vector<int> iseven(n,-1);
  iseven[0]=1;
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int v=que.front();
    que.pop();
    for(int i=0;i<n;++i){
      if(!G[v][i]) continue;
      if(iseven[i]!=-1) continue;
      iseven[i] = 1-iseven[v];
      que.push(i);
    }
  }
  vector<pair<int,int>> ans;
  for(int i=0;i<n;++i){
    for(int j=i+1;j<n;++j){
      if(iseven[i]!=iseven[j] && !G[i][j]) ans.push_back({i,j});
    }
  }

  if(ans.size()%2==1){
    cout<<"First"<<endl;
    cout<<ans[0].first+1<<" "<<ans[0].second+1<<endl;
    int x,y;
    cin>>x>>y;
    int cur=1;
    while(x!=-1 || y!=-1) {
      --x; --y;
      if(x>y) swap(x,y);
      for(int i=0;i<ans.size();++i) if(ans[i].first == x && ans[i].second == y){
        ans[i]={-1,-1};
      }
      while (ans[cur].first==-1 && ans[cur].second==-1) ++cur;
      cout<<ans[cur].first+1<<" "<<ans[cur].second+1<<endl;
      ++cur;
      cin>>x>>y;
    }
    cout<<endl;
  }
  else{
    cout<<"Second"<<endl;
    int x,y;
    cin>>x>>y;
    int cur=0;
    while(x!=-1 || y!=-1) {
      --x; --y;
      if(x>y) swap(x,y);
      for(int i=0;i<ans.size();++i) if(ans[i].first == x && ans[i].second == y){
        ans[i]={-1,-1};
      }
      while (ans[cur].first==-1 && ans[cur].second==-1) ++cur;
      cout<<ans[cur].first+1<<" "<<ans[cur].second+1<<endl;
      ++cur;
      cin>>x>>y;
    }
    cout<<endl;
  }
  return 0;
}
F問題 (500点)

atcoder.jp

末尾の文字を含む区間が回文かどうかを判定したい。Manacher のアルゴリズムというのがあり、これは「 i 文字目を中心とした回文の最大長」を求められるものである。これを偶数長に拡張したものを S に適用したのち、 i 文字目を中心とした最長の回文が S の末尾を含む場合のみ考え、このときの最大値を求めれば終わり。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main() {
  string s;
  cin>>s;
  int n = s.length();

  // (追記) インターネットから窃盗してきたものをそのままライブラリ扱いして使っている
  // rad2 になっているのは奇数長を別に判定しなければいけないと勘違いしていたから
  string t(2 * n + 1, '#');
  for (int i = 0; i < n; i++) t[2 * i + 1] = s[i];
  n = 2 * n + 1;

  vector<int> rad2(n,0);
  int c = 0, r = 0;

  while (c < n) {
    while (0 <= c - r && c + r < n && t[c - r] == t[c + r]) r++;
    rad2[c] = r;

    int k = 1;
    while (0 <= c - k && k + rad2[c - k] < r) {
      rad2[c + k] = rad2[c - k];
      k++;
    }
    c += k;
    r -= k;
  }
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
      rad2[i] = (rad2[i] - 1) / 2;
    else
      rad2[i] /= 2;
  }

  int m=0;
  for(int i=0;i<n;++i){
    //cerr<<i<<" "<<rad2[i]<<"\n";
    if(i%2==0){
      if(i/2+rad2[i]==(n-1)/2){
        m=max(m,rad2[i]*2);
      }
    }
    else{
      if(i/2+rad2[i]==(n-1)/2){
        m=max(m,rad2[i]*2-1);
      }
    }
  }
  
  string u=s.substr(0,n/2-m);
  string v=s.substr(n/2-m, m);
  string w=u;
  reverse(begin(w),end(w));
  cout<<u<<v<<w<<"\n";
}
G問題 (600点)

atcoder.jp

見てない

感想

ペナがくだr (ry)、4 完でギリ耐えでした。E は解けるべきだった……

主観難易度

A問題

難易度

5

VERY EASY

  • やるだけ

B問題

難易度

10

EASY

  • 弱い数学問

C問題

難易度

15

EASY

  • 問題文が読めればなんてことはない (私は読めなかったので3ペナしている)
  • map での処理はちょっと工夫がいるかも

D問題

解けていないので主観難易度は設定しません

E問題

難易度

25

NORMAL

  • 二部グラフを思いつけば終わり
  • 処理を書くのがやや面倒ではある

F問題

難易度

30

NORMAL

  • 解かれまくったのはtestcaseがくそざこだったせいっぽいので、愚直がちゃんと弾かれていればF妥当だったのでは (ロリハはさよなら)

G問題

解けていないので主観難易度は設定しません

Onling2025 D - 初心者による解法記事

Onling 言語/命数 初心者による解法記事

***Firmianaです。この前開催された Onling 2025 の自分なりの解法記事を書いてみようと思います。言語学をちゃんと勉強しているわけではないので拙いところがあると思いますが、よろしくお願いします。

A,C 問題はちゃんと解けなかったので、B,D 問題について初心者向けに行間を狭く書ければいいなと思っています。それではどうぞ。

問題

……あらゆる問題について言えますが、記事を読まずに今から解く際は、作問者を信頼しすぎないことをお勧めします。

onling.org

問題の説明

未知の単語が22個与えられています。これらは組み合わせることで時刻を表します。22個の単語とワイルドカード*を組み合わせて語を作り入力することで、その表現が存在するか確認することができます。この入力欄を用いて、実際の時刻を表す表現を特定してください。

主観難易度

難易度

40

HARD

  • 総当たりでもなんとかなる
  • 時間はそこそこかかる (目標 : 50分)
主観難易度についてはこちら

解法

以下に私の解法を示しますが、様々・・な理由により (後述) 私は満点を得ていません (18.5pts / 20.0pts)。

1. 語順の特定

とりあえず単語の意味を置いておいて、文法を特定しにかかります。この問題ではワイルドカード*を用いて、例えば「A * B」としてAとBの間に1単語以上あるような表現が存在するかをチェックできます。これを活用して、どの単語がどの位置にあるかを調べます。

調べ方は簡単で、Aという単語について、「A *」が存在すればAは先頭にあり、「* A *」が存在すればAは中間にあり、「* A」が存在すればAは末尾にあります。このチェックを22単語すべてに対して実行し、先頭、中間、末尾で分類すると次の表の通りになりました*1。

単語先頭中間末尾
alfadjyry✅
azubuhy✅
dakyka✅
djyony✅
kazoro✅
kumy✅
mbyly✅
mcana✅
modja✅
na✅
nane✅
nne✅
nusu✅
robo✅
tano✅
tatu✅
tyza✅
uzyku✅
yxyryny✅
zaa✅
zaba✅
zyta✅

先頭、中間、末尾の2か所以上に現れる単語はないようです。また、どうやら先頭にあるのは zaa だけのようですね。これでどの表現の先頭も zaa であることが確定しました。また、すべての時刻の表現に zaa が含まれることから、zaa にはあとの単語列を「時刻」だと示す意味や、単に「○時」の意味があると考えられます。

続いて、先頭が確定したので zaa の次に来うる単語を調べます。「zaa A *」のようにすればいいですね。

表現存在
zaa + dakyka❌
kazoro❌
kumy✅
mbyly✅
modja✅
na❌
nane✅
nne✅
nusu❌
robo❌
tano✅
tatu✅
tyza✅
yxyryny❌
zaba✅
zyta✅
末尾のみの単語❌

上の表の通り、10 個の単語が zaa の直後に来うるようです。説明の都合上、こいつらをA群、上の表で❌がついている6単語をB群と呼ぶことにします。

欲張ってもう 1 単語増やして探索してみましょう。結果は下表のとおりです。

表現存在/時刻
zaa + kumy, mbyly, modja, nane, nne,
tano, tatu, tyza, zaba, zyta +		kazoro, na✅
kumy +alfadjyry✅4:00
その他 +alfadjyry❌
mbyly +azubuhy✅8:00
modja +azubuhy✅7:00
nne +azubuhy✅10:00
tano +azubuhy✅11:00
tatu +azubuhy✅9:00
その他 +azubuhy❌
kumy +djyony✅16:00
tyza +djyony✅15:00
その他 +djyony❌
nane +mcana✅14:00
zaba +mcana✅13:00
zyta +mcana✅12:00
その他 +mcana❌
mbyly +uzyku✅20:00
modja +uzyku✅19:00
nane +uzyku✅2:00
nne +uzyku✅22:00
tano +uzyku✅23:00
tatu +uzyku✅21:00
tyza +uzyku✅3:00
zaba +uzyku✅1:00
zyta +uzyku✅0:00
その他 +uzyku❌

遂に時刻が現れました！　「zaa + A群 + 末尾」 という表現で、「○時ちょうど」という時刻になるようです。しかも以下のことが分かります。

  • 末尾の単語ごとに表現する時刻の範囲がある→「朝」とか「昼」を表している？
  • A群の単語はすべて2回ずつ現れ、差は必ず12時間→A群の単語には順序がある？

ほ～いい感じですね。末尾の単語の意味も推測できていますし、A群の単語もなんとなく数値っぽいことが分かりました。一気に進捗が生まれましたね！


…………


5:00、6:00、17:00、18:00 無くね？

あれれ～、おっかしいぞ～？　単語はちゃんと網羅してるはずなのに足りない……

(本番の我(われ)ここで10分消費)

……まあとりあえず進めるか……1単語は提示されてないから多分それだろ。とりあえず「zaa + A群 + (kazoro / na)」の方を見ていきましょう。

表現存在
zaa +kumy, mbyly, modja, nane, nne,
tano, tatu, tyza, zaba, zyta +		kazoro, na +dakyka, robo✅
kumy, mbyly, modja, nane, nne,
tano, tatu, tyza, zaba, zyta +		na +nusu✅
kumy +na +mbyly✅

kumy さん何やってるんですか？

どうやら、kumy 以外のA群の単語は kazoro および na の次にはB群の単語しかとらないにもかかわらず、kumy だけはA群の mbyly を取れるようです。これは匂いますね。勘を働かせて「zaa kumy na mbyly」に続く単語を探してみると次の通りになりました。

表現存在/時刻
zaa kumy na mbyly +kazoro, na✅
azubuhy✅6:00
uzyku✅18:00

6:00 と 18:00 が判明しました！　どうやら kumy na mbyly でA群の単語と同じ働きを持つようですね。5:00 と 17:00 は依然不明ですがまあ設問 (b) の単語だと思うことにします。今のところの進捗は下表の通りですね。

表現時刻
zaa zyta uzyku0時
zaa zaba uzyku1時
zaa nane uzyku2時
zaa tyza uzyku3時
zaa kumy alfadjyry4時
?5時
zaa kumy na mbyly azubuhy6時
zaa modja azubuhy7時
zaa mbyly azubuhy8時
zaa tatu azubuhy9時
zaa nne azubuhy10時
zaa tano azubuhy11時
zaa zyta mcana12時
zaa zaba mcana13時
zaa nane mcana14時
zaa tyza djyony15時
zaa kumy djyony16時
?17時
zaa kumy na mbyly uzyku18時
zaa modja uzyku19時
zaa mbyly uzyku20時
zaa tatu uzyku21時
zaa nne uzyku22時
zaa tano uzyku23時

では、さらに語順を確定させていきましょう。kumy na mbyly はA群の単語と同様、zaa kumy na mbyly + (kazoro か na) + dakyka および zaa kumy na mbyly + na + (nusu か robo) という表現を成立させることが確かめられるので、これを1単語と扱うことにして以降解いていきます。

とりあえず0/12時台を表していそうな zaa zyta から、続く表現についてあり得るものを見ていきます。まずは zaa zyta kazoro dakyka です。

表現存在/時刻
zaa zyta kazoro dakyka +A群✅
yxyryny✅
その他❌

再びA群に加え、新たに yxyryny が現れ (なんて読むんでしょうねこれ)、また 11/23時50分 の表現が分かりました。yxyryny をいったん放置してA群の方の続きを探します。なお省略していますが、末尾が azubuhy なら11時、uzyku なら23時です。

表現存在/時刻
zaa zyta kazoro dakyka +kumy✅:50
tyza✅:51
nane✅:52
zaba✅:53
zyta✅:54
tano✅:55
nne✅:56
tatu✅:57
mbyly✅:58
modja✅:59
kumy na +✅

11/23時50分台 の表現がすべて見つかりましたが……

kumy！　またかテメェ！

どうやら zaa zyta kazoro dakyka kumy na という表現も許されるようです。／(^o^)＼ﾅﾝﾃｺｯﾀｲ　これに絞って続きを見るとA群の単語のみが出てきて、さらに次には azubuhy/uzyku しか取れません。どうやらこいつで 11/23時40分台を表現するらしいです。

表現存在/時刻
zaa zyta kazoro dakyka kumy na +tyza✅:41
nane✅:42
zaba✅:43
zyta✅:44
tano✅:45
nne✅:46
tatu✅:47
mbyly✅:48
modja✅:49

今度は zaa zyta kazoro dakyka yxyryny に絞って続きを見てみると、azubuhy/uzyku/na しかありえないことが分かります。さらに na の次には、こちらでも A 群の単語のみが現れ、同様に azubuhy/uzyku のみしか末尾に取れません。11/23時30分台の表現が分かりました。

表現存在/時刻
zaa zyta kazoro yxyryny +✅:40
na +tyza✅:41
nane✅:32
zaba✅:33
zyta✅:34
tano✅:35
nne✅:36
tatu✅:37
mbyly✅:38
modja✅:39

これで31分～59分の表現らしきものが分かりました。

zaa zyta na dakyka も同様に見てみると、以下の表のように1分～29分の表現っぽいものを発見できます。

表現表現
zaa zyta na dakyka +modja:01
mbyly:02
tatu:03
nne:04
tano:05
zyta:06
zaba:07
nane:08
tyza:09
kumy:10
kumy na +modja:11
mbyly:12
tatu:13
nne:14
tano:15
zyta:16
zaba:17
nane:18
tyza:19
yxyryny:20
yxyryny na +modja:21
mbyly:22
tatu:23
nne:24
tano:25
zyta:26
zaba:27
nane:28
tyza:29

0分を中心に、dakyka 以下の表現が対称になっているので、なんとなく kazoro が減算、na が加算っぽく見えますね。

あとは30分の表現のみが分かっていません。na nusu と na robo を見ていきましょう。

表現存在/時刻
zaa zyta na +nusu✅:30
robo✅:15

na nusu が12/0時30分を、na robo が12/0時15分を表すようです……11/23時45分どこ行った？　今のところの考察的には kazoro robo であってほしいところですが、入力欄には「そんな表現ねえよ」と言われてしまいます。

(我、20分の長考)

うーん、とりあえずA群の単語の順番を確認して、分かっている部分の単語の訳を考えますか。

2. 単語の意味を解析する

今のところ分かっているのは、「○時ちょうど」「○時半」「○時15分」「○時△分 (△は0,30でない59以下の任意の整数)」の表現です。これまでの解析により、表現の前半で「時」、後半で「分」、末尾で「時間帯」を表現していることは分かっており、「時」を含む表現には zaa が、15分/30分以外*2の「分」を含む表現には dakyka が入っているので、 zaa は「時」、dakyka は「分」のようです。

次に kazoro と na について、先程ちらっと述べましたが、それぞれ「○時ちょうど」からの減算、加算を表していると考えられます (こう考えると次の kumy na mbyly の意味も自然に分かります)。よって、kazoro は「引く」、na は「足す」だと考えられます。

さらに A 群の単語および kumy na mbyly については、先程並べた順番から以下の通り推測できます。31～59分については60分からの減算になっていることに注意です。

単語値
modja1
mbyly2
tatu3
nne4
tano5
zyta6
zaba7
nane8
tyza9
kumy10
kumy na mbyly12

kumy na mbyly は 10+2、すなわち 12 を表していたんですね。となると 11 の行方が気になりますが……

一旦置いておいて分数の部分を見ると、まず nusu は「30分」、robo は「15分」であり、yxyryny は kumy が 10 なことに注意すれば「20」であると考えられます。

最後に時間帯の部分を考えると、alfadjyry は4時～6時、azubuhy は6時から12時、mcana は12時から15時、djyony は15時から18時、uzyku は18時から翌4時なので、それぞれ「明け方」「朝」「昼」「夕方」「夜」くらいが適切かなと思います。


……ということで、すべての単語の意味を推測できました。以上の考察を基に時刻表現の文法を考えると次のようになります。以下、数値Aに対応する単語を (A) で表します。

  • (A) は次の表の通り

単語 (A)値 A
modja1
mbyly2
tatu3
nne4
tano5
zyta6
zaba7
nane8
tyza9
kumy10
?11
kumy na +mbyly12
tatu13
nne14
tano15
zyta16
zaba17
nane18
tyza19
yxyryny20
yxyryny na +modja21
mbyly22
tatu23
nne24
tano25
zyta26
zaba27
nane28
tyza29

  • 「A時ちょうど」は、時刻の数え始めが6時と18時になっていることから、
    • A が 0～6 なら zaa (A+6) (時間帯)
    • A が 7～10 か 12～18 なら zaa (A-6) (時間帯)
    • A が 19～23 なら zaa (A-18) (時間帯)
    • A が 5,17 は不明

(これ以降「A時」に対応する (A) は上の通り読み替えてください)

  • 「A時半」は zaa (A) na nusu (時間帯)
  • 「A時15分」は zaa (A) na robo (時間帯)
  • 「A時45分」は不明
  • 上記以外の時刻「A時B分」について
    • B が 1～29 なら zaa (A) na dakyka (B) (時間帯)
    • B が 31～59 なら zaa (A) kazoro dakyka (60-B) (時間帯)

実際にいくつか試してみるとうまく行っていることが分かります。

  • 4時27分：zaa kumy na dakyka yxyryny na zaba alfadjyry
  • 8時40分 : zaa tatu kazoro dakyka yxyryny azubuhy
  • 13時5分 : zaa zaba na dakyka tano mcana
  • 21時48分 : zaa nne kazoro dakyka kumy na mbyly uzyku

「11」と「45分」が見当たらないのが気になりますが……「11」は多分 kumy na modja、「45分」は多分 kazoro robo だと思うのですがどちらも弾かれてしまいます。設問 (b) で解答できる単語は 1 つだけですし…………


(我、30分の大長考)


うん、分からん (思考放棄)

他の部分は合ってそうだから点は来るやろ、とりあえずなんか書いとけ*3。

それは絶対に違う

ちなみに、ここまでの説明通り解答すれば 19.0pts を得られます。

Ex. 11 と 45分 はどこに消えたのか

さて、この問題は 2. までの手順で完全に解けているはずですが、設問 (b) の答えになりそうな単語が 2 通りあって詰め切れません。

実はこの問題不備っており、solution のところに「システム構築ミスった、ごめん、採点には考慮してあるから許してね☆ (意訳)」と書いてありました。


…………ha？

俺の長考で溶かした時間と点数返してくれ……


……ということで、入力欄が「5/17時」の正しい表記「zaa kumy na modja (時間帯)」を正しく判定できなくなっていたようです。つまり「11」が見つからなかったのは完全に不備で、設問 (b) で答えるべき単語は「45分」の方だったらしいですね。えぇ…… (涙)

――で「45分」の単語ですが、本来 kazoro robo となるべき部分が音の連続により1つの単語になっていることが示唆されているので、kazorobo となるようです。正直言オリ要素ここの音韻関係だけじゃねと思ったのですが


ということで、不備が無ければ上記の解法で問題なく完答できます。40分掛かるかどうかくらいではないでしょうか。

終わりに

まずはここまで読んでいただきありがとうございました。備忘録的に書いてみましたが、いかがでしょうか。日本語下手なので読み辛かったかと思います……すみません。

この問題は (一旦不備のことを忘れれば) Onling としてはかなり簡単で、実際平均点もそこそこあったようですが、入力欄を使って特定していく以上時間がかかります。この問題の処理速度が上位を分けたのではないかと勝手に思っています (?)


……ところで、不備を抜きにしても 19.0pts を得られると書きました。じゃ、なんで私は 18.5pts しか取ってないんだと思われるかもしれません。

落ち着いて解きましょうね

……焦りすぎて typo を生み、このように -0.5pts されていました。

設問 (b) の件と合わせて -1.5pts で、これがあれば合計 44.5pts となり銀賞に上がる (多分) うえ、B,Dの2問が満点になります。全体で1人しかいなかった2完以上の参加者に私もなれていたことを考えると、悔しいとか以前に悲しくなってきます……haha、私は幻のOnling 2完erです。


みなさんは問題が不備っていて解けなくても、慌てず取れる点を取りましょう……以上です……

*1:この問題の設問(b)にある通り、実はもう1単語存在しますが、この時点ではどうしようもないので考慮しません

*2:英語での half/quarter と同類なので、dakyka が入っていなくても自然です

*3:ここで夕方と答えたのは、本番中に「夕方」の表現が無いと勘違いして書いたものを、最後の混乱状態でそのままにしていたからです

ABC397 参加記 (という名の解法記事)

AtCoder という名の解法記事

***
Firmiana です。ABC397の解法記事です。D問題までしか解けなかったのでボリューム少なめですが悪しからず()

今回の戦略

特になし

文字実況

  1. コンテスト開始 (0分)
  2. B問題 AC (7分)
  3. A問題 誤差を気にするあまり誤読に気付かず1ペナ目 (7分)
  4. A問題 激遅AC (8分)
  5. C問題 AC (11分)
  6. D問題 xの範囲を勘違いして1ペナ目 (18分)
  7. D問題 yの全探索範囲を勘違いして2ペナ目 (41分)
  8. D問題 AC (43分)
  9. E問題 方針が浮かぶが実装できない (50分)
  10. 椅子を温めてコンテスト終了 (100分)

解法

A問題 (100点)

atcoder.jp

誤差が怖かったので (実は境界が 2^{-1} 刻みなので怖がらなくてよかった)、文字列として受け取って小数点前後で区切り、結合して 3 桁の整数として扱った。なお文字列の状態での比較でも通る (実装例2)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  string s;
  cin>>s;
  string t=s.substr(0,2)+s.substr(3,1);
  int i=stoi(t);
  if(i>=380)cout<<1<<"\n";
  else if(i>=375)cout<<2<<"\n";
  else cout<<3<<"\n";
}

実装例2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  string s;
  cin>>s;
  if(i>="38.0")cout<<1<<"\n";
  else if(i>="37.5")cout<<2<<"\n";
  else cout<<3<<"\n";
}
B問題 (250点)

atcoder.jp

前から貪欲に文字を追加するかしないかを決めればいい。具体的には今 S の何文字目までを使ったかを持っておいて、操作後の文字列の ( 0-indexed として) 偶数文字目で、かつ次の S の文字が "i" ならばそれを追加すればよく、でなければ "o" を追加したのち "i" を追加する。これで何文字増加するかが計算できる。最終的に全体の文字数が偶数でなければならないことに注意。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  string s;
  cin>>s;
  int c=0,ans=0;
  for(int i=0;i<s.length();++i){
    if(c%2==0){
      if(s[i]=='i'){
        ++c;
      }
      else{
        ++ans;
        c+=2;
      }
    }
    else{
      if(s[i]=='o'){
        ++c;
      }
      else{
        ++ans;
        c+=2;
      }
    }
  }
  if(c%2==1)++ans;
  cout<<ans<<"\n";
}
C問題 (350点)

atcoder.jp

とりあえず全体の種類数と、各数が何個あるかを求めておく。続いて前から区間を伸ばしつつ同じ計算を行って前の区間の種類数を求め、同時に後ろの区間からある数が 0 個になったら種類数を減らす。この 2 つの種類数の総和の max を都度取れば答えが得られる。

なお、以下の実装では無駄に set<int> を使っているが遅いので、この記事を書いている最中に追加した 4 本スラッシュにある処理の方が適切 (set<int> の場合 491 ms、int の場合 57 ms)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;++i) cin>>a[i];
  set<int> s,t; //// int s=0,t=0;
  vector<int> x(n+1,0),y(n+1,0);
  for(int i=0;i<n;++i){
    t.insert(a[i]); //// if (y[a[i]]==0) ++t;
    y[a[i]]++;
  }
  int ans=0;
  for(int i=0;i<n-1;++i){
    s.insert(a[i]); //// if(x[a[i]]==0) ++s;
    if(y[a[i]]==1){
      t.erase(a[i]); //// --t;
    }
    y[a[i]]--;
    //// x[a[i]]++;
    ans=max(ans,(int)(s.size()+t.size())); //// ans=max(ans,s+t);
  }
  cout<<ans<<"\n";
}
D問題 (425点)

atcoder.jp

とりあえず x の最大値を考えるが、雑に見て x^3-(x-1)^3=3x^2+3x+1\leq N となるのは x\leq 10^9 のときなので全探索できない。差の形になっているのが厄介なので (上からの評価が難しい)、因数分解を試みる。 x^3-y^3=(x-y)(x^2+xy+y^2) なので、 x-y=d とおけば、

\displaystyle \begin{aligned} x^3-y^3 &= (x-y)(x^2+xy+y^2) \\ &= d((y+d)^2+(y+d)y+y^2) \\ &= d(d^2+3yd+3y^2) \leq 10^{18} \end{aligned}

より d\leq 10^6 である。これなら全探索できるので、 d を決め打って y の値を二分探索すればいい。 y は最大 10^9 で問題ない (実はもっと減らせるがここでは意味がない)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int main(){
  ll n;
  cin>>n;
  for(ll d=1LL;d<=1000000LL;++d){
    if(n%d!=0LL) continue;
    ll k=n/d;
    ll yl=0LL, yr=1000000000LL;
    while(yr-yl>1LL){
      ll m=(yl+yr)/2LL;
      ll f=3LL*m*m+3LL*m*d+d*d;
      if(k<=f) yr=m;
      else yl=m;
    }
    if(3LL*yr*yr+3LL*yr*d+d*d == k){
      cout<<yr+d<<" "<<yr<<"\n";
      return 0;
    }
  }
  cout<<"-1\n";
}
E問題 (475点)

atcoder.jp

解けてませんが考察の方針は合っていたので書いておきます。

根を固定して葉から順に遡りつつ見ていくと、長さ K の部分木がパスでなければならないことに注意すれば貪欲に取り除いてもいいことが分かる。この操作の途中、次数 3 以上の頂点が現れたら OUT。

F問題 (550点)

atcoder.jp

見てない

G問題 (625点)

atcoder.jp

見てない

感想

ペナがくだr (ry)、4 完でギリ耐えでした。E は解けるべきだった……

主観難易度

A問題

難易度

5

VERY EASY

  • やるだけなのだが怖い

B問題

難易度

15

EASY

  • B 問題にしてはやや面倒
  • 解法自体にあまり自信が無いのでやや高めの評価

C問題

難易度

15

EASY

  • 体感 B より不安感が無いので逆ではと思っていた

D問題

難易度

20

EASY

  • 差は嫌なので和か積に変換したくなり、因数分解して d を置くことを思いつくのは割と自然だと思っているのでこのくらい
  • 二分探索が難しいというわけでもない

E問題

解けていないので主観難易度は設定しません

F問題

解けていないので主観難易度は設定しません

G問題

解けていないので主観難易度は設定しません

OMCB038 参加記 (という名の解法記事)

OMC という名の解法記事

***
Firmiana です。OMCB038に出たので (結果は散々でしたが) また解法記事を錬成します。

今回の戦略

  • 潜伏 : 全問題答えを出せるまで提出せず、残り時間が少なくなるか全問解けるかし次第一気に提出する。

文字実況

  1. コンテスト開始 (0分)
  2. A 問題を解く (4分)
  3. B 問題を解く (7分)
  4. C 問題を沼りながら解く (16分)
  5. D 問題の方針が立たず飛ばす (20分)
  6. E 問題を解く (25分)
  7. F 問題を解く (38分)
  8. D 問題を解く (47分)
  9. G 問題を解く (58分)
  10. A-G を提出するが B,F が WA (60分)
  11. B の計算ミスに気づき修正 (61分)
  12. F の計算ミスに気づき修正 (61分)
  13. H 問題を解くが WA (71分)
  14. 間に合わず終了 (80分)
  15. H 問題のミスに気づき萎える (82分)

解法

A問題 (整数/100点)

onlinemathcontest.com

1の位か100の位を固定して書けば容易。 A=45, B=19 となるから、答えるべきは \mathbf{855} となる。

本番中のメモ (A問題)
B問題 (代数/100点)

onlinemathcontest.com

明らかに a_{65} が最小値を取るとき、 2\leq n\leq 64 に対して a_n は最小値を取る。取らないと仮定すると、最小値に対して同じ操作を行うことで a_{n+1} をより小さくできるので仮定は偽ゆえ示せる。

よって、 a_1 が固定であるから、各 1\leq n\leq 64 について a_{n+1}-a_n を最小化すればよいが、これは 14159 または a_n である。よって、 a_n<14159 かどうかで操作を変えればよく、実際 3\times 2^{12}<14159<3\times 2^{13} であるから a_{14} までは 2 番目の操作を、それ以降は 1 番目の操作を行えば最小値が得られる。よって答えは 3\times 2^{13} + 14159 \times (65-14) = \mathbf{746685} となる。

本番中のメモ (B問題) 65-14 は 41 ではない
C問題 (整数/200点)

onlinemathcontest.com

以下、進数表記の無い数はすべて十進法とする。

314_{(n)}=3n^2+n+4, 15_{(n)}=n+5 であるから、 \dfrac{3n^2+n+4}{n+5} が整数になればよく、これは \mathrm{gcd}(a,b) で a,b の最大公約数を表すことにすれば、明らかに 3n^2+n+4\geq n+5 > 0 ゆえ \mathrm{gcd}(3n^2+n+4, n+5)=n+5 であることと同値。このときユークリッドの互除法より、

\displaystyle \mathrm{gcd}(3n^2+n+4, n+5) = \mathrm{gcd}(4-14n, n+5) = \mathrm{gcd}(14n-4, n+5) = n+5

が成り立つので、 k を正整数として 14n-4=k(n+5) を満たす組 (n,k) が存在するような n を求めればよい。

\displaystyle \begin{aligned} 14n-4 &= k(n+5) \\ nk-14n+5k &= -4 \\ (n+5)(k-14) &= -74 = -1\times 2\times 37 \end{aligned}

であって、 n\geq 6 より n+5\geq 11 であることに注意すれば、組 (n+5,k-14) は

\displaystyle (n+5, k-14) = (74, -1), (37, -2)

に限られる。このとき

\displaystyle (n, k) = (69, 13), (32, 12)

であるから、答えは 69+32=\mathbf{101} となる。

本番中のメモ (C問題)
D問題 (組み合わせ/200点)

onlinemathcontest.com

それぞれの分け方についてのスコアの総和は、それぞれの箱について 3 個のボールが入る場合の数の総和に等しい。注目する箱の選び方が 7 通り、その箱に入るボールの選び方が \binom{22}{3} 通り、残り 19 個のボールの場所が 6^{19} 通りゆえ、スコアの総和は


\displaystyle 7\times \dfrac{22\times 21\times 20}{6}\times 6^{19} = 2^{21}\times 3^{19}\times 5\times 7^2\times 11

であるから、この正の約数の個数は 22\times 20\times 2\times 3\times 2=\mathbf{5280} となる。

本番中のメモ (D問題) FPS的なものをしようとした痕跡がある
E問題 (整数/200点)

onlinemathcontest.com

541^2=292681<314159 であるから、エラトステネスの篩的なものを考えるといくつか合成数が残っていることが分かる。実際書き出すと、

\displaystyle 547^2, 547\times 557, 547\times 563, 547\times 569, 547\times 571, 557^2, 557\times 563

の 7 つの合成数が残っている。残っている素数は 27131-100=27031 個であるから、答えは 27031+7=\mathbf{27038} となる。

本番中のメモ (E問題)
F問題 (代数/200点)

onlinemathcontest.com

f(3)=1, f(4)=1, f(5)=9 を満たす整数係数多項式 f(x) は、0 次以上の整数係数多項式 g(x) を用いてすべて次の形に表される。

\displaystyle f(x)=g(x)(x-3)(x-4)(x-5) + 4x^2-28x+49

なお、末尾 3 項は適当な連立方程式により求まる。 x=265 を代入して、

\displaystyle f(265)=g(265)(265-3)(265-4)(265-5) + 4\cdot 265^2-28\cdot 265+49 = g(265)\cdot 17779320 + 273529

となる。ここで g(265) の値は任意なので、 0 とすれば |f(265)| は最小値 \mathbf{273529} を取る。

本番中のメモ (F問題) 間違えて 9 を代入している
G問題 (整数/300点)

onlinemathcontest.com

明らかに p\geq 3 ゆえ a^{ab} と cde のいずれか一方のみが奇数。よって c\lt d\lt e とすれば a,c のいずれか一方が 2 である。

(ア) a=2 のとき、 p^2=4^b+cde となる。 \mathrm{mod}.3 を考えると、左辺は 1、右辺は 1+cde と合同なので、 cde は 3 の倍数。よって c=3 となるから、 p^2=4^b+3de となる。これより b\geq 5 である。

4^b を左辺に移項して因数分解もどきをすると (p+2^b)(p-2^b)=3de となるから、 p>2^b\geq 2^5=32 であって、これより p\geq 37 である。小さい方から順に見ていくと、

1. p=37 のとき、 p-2^b=5 ゆえ不適。
2. p=41 のとき、 p-2^b=9=3^2 ゆえ不適。
3. p=43 のとき、 p+2^b=75=3\times 5^2 ゆえ不適。
4. p=47 のとき、 p-2^b=15=3\times 5 ゆえ不適。
5. p=53 のとき、 p+2^b=85=5\times 17 ゆえ不適。
6. p=59 のとき、 p-2^b=27=3^3 ゆえ不適。
7. p=61 のとき、 (p+2^b)(p-2^b)=3\times 29\times 31 より適する。
8. p=67 のとき、 p+2^b=99=3^2\times 11 ゆえ不適。
9. p=71 のとき、 (p+2^b)(p-2^b)=3\times 13\times 103 より適する。
10. p=73 のとき、 p+2^b=105=3\times 5\times 7 ゆえ不適。
11. p=79 のとき、 (p+2^b)(p-2^b)=3\times 37\times 47 より適する。

以上より、 3 番目に小さい p は 79 以下である。

(イ) c=2 のとき a\geq 3 であって、このとき

\displaystyle p=\sqrt{a^{ab}+2de}\geq \sqrt{3^{3\times 5}+2\times 7\times 11}=\sqrt{14349061}>3788>79

ゆえ今回の問題では考えなくてよい。

以上より、答えは 61\times 71\times 79=\mathbf{342149} となる。

本番中のメモ (G問題 1枚目)
本番中のメモ (G問題 2枚目)
H問題 (幾何/400点)

onlinemathcontest.com

一般に、ある長さの弦に対する円周角の大きさは、その円の半径が小さいほど大きくなる (正弦定理から分かる)。 3 点 A,B,P および C,D,P を通る円をそれぞれ E,F とし、それぞれの中心を Q,R とする。また、線分 AB,CD の中点をそれぞれ M,N とする。円 E,F の半径をそれぞれ a,b とすると、円 E,F は外接しているとしてよいので、 AB,CD に対する円周角が等しいことと合わせて以下の 2 式

\displaystyle (a-b)^2+\left(\dfrac{9}{2}\right)^2=\left(\sqrt{a^2+\left(\dfrac{3}{2}\right)^2}+\sqrt{b^2+2^2}\right)^2 \\ \tan{\theta} = \dfrac{3/2}{a} = \dfrac{2}{b}

が成り立つ。第 2 式を第 1 式に代入して整理すれば b^2=\dfrac{8}{3} が伴うので、求める \sin{\alpha} の値は \sin{\alpha} = \dfrac{2}{\sqrt{b^2+4}} = \sqrt{\dfrac{3}{5}} となるから、解答すべき値は \lfloor 1000\sqrt{0.6}\rfloor = \mathbf{774} となる。

本番中のメモ (H問題) 立式をミスっている
本番後に書いた修正版

感想

うーんくだらないミスが多すぎる

主観難易度

A問題

難易度

0

VERY EASY

  • 数えるだけなので

B問題

難易度

5

VERY EASY

  • ちょっと心配だが各 an を最小化すればいいので簡単

C問題

難易度

15

EASY

  • 互除法か括り出しをして n を1次に落とせるかがポイント

D問題

難易度

15

EASY

  • 典型的な主客転倒の問題

E問題

難易度

10

EASY

  • 書くだけなので楽に解ける

F問題

難易度

20

EASY

  • f(x)を構成できれば容易
  • 今回は関係ないが絶対値記号に注意

G問題

難易度

30

NORMAL

  • やや雑な絞り込みで攻略できる
  • 整数の基本的なテクをよく使うと感じた

H問題

難易度

25

NORMAL

  • 接すると思って文字を置けば解けるので青diffはないだろの気分

OMC244 参加記 (という名の解法記事)

OMC という名の解法記事

***
Firmiana です。今回はさっき終わった OMC244 の解法記事です。帰省中でスキャナが使えないので、計算用紙は3/11以降に追加されます。

3/13追記 計算用紙追加しました

今回の戦略

特になし

文字実況

  1. コンテスト開始 (0分)
  2. A問題で沼る (8分)
  3. A問題CA (10分)
  4. B問題CA (17分)
  5. C問題で沼る (40分)
  6. D問題に移るが何もわからない (60分)
  7. E問題愚直数え上げを実行 一発CA (84分)
  8. C問題 本質に気付き提出するが不等式評価ミスで1ペナ目 (92分)
  9. C問題CA (95分)
  10. コンテスト終了 (100分)

解法

A問題 (代数/100点)

onlinemathcontest.com

前から愚直に計算してみる。 a_1=3、 a_{n+1}=\dfrac{1-2|a_n|}{1+|a_n|^2} より、 a_2=-\dfrac{1}{2}、 a_3=0、 a_4=1、 a_5=-\dfrac{1}{2} であり、同じ値に戻ってきたので後は繰り返し。よって解答は

\displaystyle 3+33\left(-\dfrac{1}{2}+0+1\right)=3+\dfrac{33}{2}=\dfrac{39}{2}

であり、解答すべきは \mathbf{41}。

本番中のメモ (A問題) 計算ミスで迷走している様子が窺える
B問題 (整数/200点)

onlinemathcontest.com

p_i を素数として n=\displaystyle\prod_{i=1}^{m} p_i^{r_i} で表されるとき、

\displaystyle d(n) = \prod_{i=1}^{m} (1+r_i) \\ \varphi(n) = n\displaystyle\prod_{i=1}^{m} \left(1-\dfrac{1}{p_i}\right) = \displaystyle\prod_{i=1}^{m} \left(p_i^{r_i}-p_i^{r_i-1}\right)

である。 330=2\times 3\times 5\times 11 であるが、いい方法が分からないので d(n) の値を総当たりする。

1. d(n)=1 はない

2. d(n)=2 のとき n=p。よって \varphi(n)=p-1=165 であるが 166 は素数でないので不適。

3. d(n)=3 のとき n=p^2。よって \varphi(n)=p(p-1)=110 で、このとき p=11、すなわち n=121 が適する。

4. d(n)=6 のとき n=pq^2。よって \varphi(n)=(p-1)q(q-1)=55 で、このとき q=5,11 であるが、いずれも不適。

5. 上以外のとき、 r_i\geq 3 なる i が存在するが、 330 は冪乗数ではないので不適。

以上より、解答は \mathbf{121} となる。

本番中のメモ (B問題)
C問題 (整数/400点)

onlinemathcontest.com

\displaystyle \begin{aligned} f(n) &= \displaystyle\sum_{k=1}^{n} \dfrac{4^n+16^k}{2^n+4^k} \\ &= \displaystyle\sum_{k=1}^{n} \dfrac{(2^n+4^k)^2-2\cdot 2^n\cdot 4^k}{2^n+4^k} \\ &= \displaystyle\sum_{k=1}^{n} \left(2^n+4^k\right) - \displaystyle\sum_{k=1}^{n} \dfrac{2\cdot 2^n\cdot 4^k}{2^n+4^k} \\ &= n2^n + \dfrac{4}{3}(4^n-1) - \displaystyle\sum_{k=1}^{n} \dfrac{2\cdot 2^n\cdot 4^k}{2^n+4^k} \end{aligned}

となる。ここで残った総和部分について、 n=2025、 k=1,2,\cdots,1012 のとき \dfrac{2\cdot 2^n\cdot 4^k}{2^n+4^k}=\dfrac{2^{2026}}{2^{2025-2k}+1}、 k=1013,1014,\cdots,2025 のとき \dfrac{2\cdot 2^n\cdot 4^k}{2^n+4^k}=\dfrac{2^{1+2k}}{1+2^{2k-2025}} である。 p=1,2,\cdots,1012 に対して k=p および k=2025-p での和を取ると分母が等しいので、

\displaystyle \dfrac{2^{2026}}{2^{2025-2p}+1} + \dfrac{2^{1+4050-2p}}{1+2^{2025-2p}} = \dfrac{2^{2026}(1+2^{2025-2p})}{1+2^{2025-2p}} = 2^{2026}

となる。よって

\displaystyle \begin{aligned} f(2025) &= 2025\cdot 2^{2025} + \dfrac{4}{3}(4^{2025}-1) - \displaystyle\sum_{k=1}^{2025} \dfrac{2\cdot 2^{2025}\cdot 4^k}{2^{2025}+4^k} \\ &= 2025\cdot 2^{2025} + \dfrac{4}{3}(4^{2025}-1) - 1012\cdot 2^{2026} - \dfrac{2^{4051}}{1+2^{2025}} \\ &= 2^{2025} + \dfrac{4}{3}(4^{2025}-1) - \dfrac{2^{4051}}{1+2^{2025}} \end{aligned}

となる。ここで最終項について、

\displaystyle 2^{2026}-2 = \dfrac{2^{4051}+2^{2026}-2\cdot 2^{2025}-2}{1+2^{2025}} < \dfrac{2^{4051}}{1+2^{2025}} < \dfrac{2^{4051}+2^{2026}-2^{2025}-1}{1+2^{2025}} = 2^{2026}-1

であり、この項以外はすべて整数なので、

\displaystyle \begin{aligned} \lfloor f(n) \rfloor &= 2^{2025} + \dfrac{4}{3}(4^{2025}-1) - \left\lceil \dfrac{2^{4051}}{1+2^{2025}} \right\rceil \\ &= 2^{2025} + \dfrac{4}{3}(4^{2025}-1) - (2^{2026}-1) \\ &= \dfrac{4}{3}(4^{2025}-1) - 2^{2025} + 1 \end{aligned}

となる。以下、合同式の法を 2017 として、

\displaystyle \begin{aligned} \lfloor f(n) \rfloor &= \dfrac{4}{3}(4^{2025}-1) - 2^{2025} + 1 \\ &\equiv 4\cdot 3^{2015} (4^9-1) - 2^9 + 1 \\ &\equiv 4\cdot 3^{2016} \cdot 87381 - 2^9 + 1 \\ &\equiv 4\cdot 650 - 512 + 1 \\ &\equiv \mathbf{72} \end{aligned}

となる。

本番中のメモ (C問題 1枚目)
本番中のメモ (C問題 2枚目)
D問題 (幾何/400点)

onlinemathcontest.com

何も分からん

本番中のメモ (D問題)
E問題 (組み合わせ/500点)

onlinemathcontest.com

いい方法が分からないので愚直に数え上げる。とりあえず条件より、 f(x), g(x) として 1,2,3,4,5,6 が 2 回ずつ現れ、更に 1 は f(x) にのみ、 6 は g(x) のみに現れる。 y\in S について (f(y),g(y))\in S^2 を組として考えると、 (1,6) の個数で場合分けができる。

1. (1,6) が 2 個のとき、 S が \{1,2,3,4\} である場合に帰着できる。この場合は普通に書き出せて、

\displaystyle \begin{cases} (2,3),(2,3),(4,5),(4,5)\ のとき\ & 6\ 通り \\ (2,3),(2,4),(3,5),(4,5)\ のとき\ & 24\ 通り \\ (2,4),(2,4),(3,5),(3,5)\ のとき\ & 6\ 通り \\ (2,3),(2,5),(3,4),(4,5)\ のとき\ & 24\ 通り \\ (2,4),(2,5),(3,4),(3,5)\ のとき\ & 24\ 通り \\ (2,5),(2,5),(3,4),(3,4)\ のとき\ & 6\ 通り \end{cases}

の計 90 通りがある。 (1,6) の位置を考えて、 90\times \binom{6}{2} = 1350 通り。

2. (1,6) が 1 個のとき、さらに 1,6 と組になる数 2 つが一致するかで場合分けする。

2-1. 一致するとき、 S が \{1,2,3\} の場合に帰着でき、この場合は (1,2),(2,3),(1,3) と同じ順序のものしか適さないので 6 通り。 1,6 と組になす数 a の選び方が 4 通り、 (1,a),(1,6),(a,6) の位置と順序で \binom{6}{3}\times 3!=120 通りゆえ、合わせて 2880 通り。

2-2. 一致しないとき、詳しいことは省略するが各 15 通り考えられる。 1,6 と組になる数 a,b の選び方が \binom{4}{2}\times 2!=12 通り、 (1,a),(1,6),(b,6) の位置と順序で \binom{6}{3}\times 3!=120 通りゆえ、合わせて 21600 通り。

3. (1,6) が 0 個のとき、さらに 1,6 と組になる数 4 つのうちいくつが一致するかで場合分けする。

3-1. 4 つが一致するとき ( a,a,b,b)、 1,6 を含む部分は S=\{1,2,3,4\} の場合のうち前 3 つの場合に帰着できるから 36 通りある。残りの部分は 1 通りなので、これらの位置を選んで \binom{6}{2}=15 通り、一致するものの選び方が 6 通りあるから、合計 3240 通り。

3-2. 2 つが一致するとき ( a,a,b,c)、 1,6 を含む部分は 72 通り、 a,b,c の選び方が \binom{4}{3}\times 3\times 2=24 通り、残り 2 組の位置が \binom{6}{2}=15 通りゆえ、合計 25920 通り。

3-3. すべて相異なるとき、 1,6 を含む部分は 144 通り、残り 2 組の並べ方が 3 通り、位置が 30 通りあるので合計 12960 通り。

以上より、解答は \mathbf{67950} 通り。

本番中のメモ (E問題) 右上→左下→右下→中央上
F問題 (代数/600点)

onlinemathcontest.com

この記事を書くときに初めて見たので解いてません。

感想

C がギリギリ通ったので良かった……

主観難易度

A問題

難易度

10

EASY

  • 実験ですぐ見える

B問題

難易度

15

EASY

  • パターン数が少ないので、素因数の性質と素因数分解を使えば楽に絞り込み総当たりができる

C問題

難易度

30

NORMAL

  • 見えにくいが覚えておきたい性質ではある
  • とりあえず書き出してみるのは大切

D問題

解けていないので主観難易度は設定しません

E問題

難易度

40

HARD

  • 数え上げれば解けるがミスなく行うのは難しい

F問題

解けていないので主観難易度は設定しません