37.50.48

%20 の ブログ

yukicoder No.1852 Divide or Reduce

この記事は yukicoder No.1852 Divide or Reduce の解説です。 操作 Y が行えない状況の場合、山同士は互いに影響を与えない、独立したゲームです。独立したゲーム(二人で交互に操作する手番が来るようなゲーム)が複数ある場合、その状況に対する Grundy …

TSG LIVE! 5 2日目のコードゴルフの問題をStarryで解いた

うらさんの記事 を参考にしました。 Starryの標準入力の仕様について詳しくなかったので調べた。 この言語のインタプリタはRubyで実装されていて、入力に関する部分は次のようになっている。 when :char_in push($stdin.getc.ord) when :num_in push($stdin.…

五月祭2020 Live CodeGolf Contest Day2 参加記

TSG LIVE! 5(2日目)のライブコードゴルフ大会に、こたつがめさんとともに外部ゲストプレイヤーとして参加させてもらいました。 TSG LIVE! でコードゴルフ大会が行われていることは以前から知っていて、参加したいと思っていたので、参加できる機会を与えて…

yukicoder No.731 等差数列がだいすき

この記事は、yukicoder No.731 等差数列がだいすき の解説です。 \(0\)-indexed とする。\(\sum\) はすべて \(\displaystyle\sum_{i=0}^{N-1}\) の略として用いる。 最小二乗法は分からないので次のように式変形する。 \(\sum(a_i-b_i)^2\\ =\sum(a_i-(b_0+d…

yukicoder No.680 作れる数

この記事は yukicoder No.680 作れる数 の解説です。 問題文を読解すると、 \(29\) 要素からなる数列 \(A=(2^1-1,2^2-1,\cdots,2^{29}-1)\) が与えられる。 \(A\) の中からいくつかの要素を選び、それらの総和をちょうど \(N\) にする方法は存在するか? と…

yukicoder No.515 典型LCP

この記事は、yukicoder No.515 典型LCP の解説です。 遅い解法だが、C++で実装した場合、実行時間制限には間に合う。 ローリングハッシュを使ったいくつかの解法がチャレンジケースで落ちたらしいが、Trie を使えば同様のことがローリングハッシュよりは高速…

yukicoder No.832 麻雀修行中

この記事は、yukicoder No.832 麻雀修行中 の解説です。 \(H[i]=\)「牌 \(i\) の枚数」とする。 各牌がアガリ牌かどうかを判定するために、以下のようにする。 その牌が元々 \(4\) 枚ある牌の場合、(この問題の定義では)アガリ牌ではないので判定対象から…

L ≤ x ≤ y ≤ R

「\(L,R\) が入力として与えられ、整数の組 \((x,y)\) \((L\le x\le R,L\le y\le R)\) であって、指定された条件を満たすものの個数を求める問題」を割と短期間で \(2\) 問見たのでなんか書く。 この記事では、以下のような記法を使う。 \(x_i\):非負整数 \…

CODE FESTIVAL 2016 Final E - Cookies

この記事は、CODE FESTIVAL 2016 Final E - Cookies の解説です。 クッキーを食べない場合、クッキーを焼く速度は常に \(1\) 枚/秒であるので、\(N\) 枚以上のクッキーを作るには \(N\) 秒かかる。 クッキーをちょうど \(1\) 回食べる場合、\(x\) 秒間で \(x…

KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing)

この記事は KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing) の解説です。 いくつかの解法があるらしいがこの解法で fastest(33ms)になった(出題されてからジャッジ環境が変化しているのであまりフェア…

区間に関するやつ

1 次元の区間に関するやつのまとめ。誰向けか分からない。 以下で言っている「演算」は、可換でなくてもよいが結合則が成り立つ必要がある(行列同士の掛け算などはこれに該当する)。 累積和 言わずと知れたやつ。 区間和をクエリ毎に \({\rm O}(1)\) で求…

√1+√2+...+√n

\(\displaystyle\lim_{n\to\infty}\left\{\left(\sum_{k=0}^n\sqrt k\right)-\left(\dfrac23n\sqrt n+\dfrac12\sqrt n\right)\right\}=-\dfrac1{\sqrt{e^\pi}}\) の真偽とその証明について知ってる人がいたら教えてほしい。 偽で、\(\zeta\left(-\dfrac12\ri…

CODE FESTIVAL 2018 の参加記じゃないやつ

これはたぶん CODE FESTIVAL 2018 の参加記ではないので読まなくていいです。 予選 A 4:58 で 2 完( AB )。C が分からなかったが(本戦ボーダーは ABD だったらしいので)C が解けていたとしても本戦には行けていない。 一方で、ネット上で交流があり会い…

yukicoder No.673 カブトムシ

この記事は yukicoder No.673 カブトムシ の解説です。 \(n\) 年目の大晦日のカブトムシの匹数を \(X_n\)(ただし \(X_0=0\))とすると、$$\begin{eqnarray}X_n&=&(X_{n-1}+B)×C\\&=&C\cdot X_{n-1}+BC\cdot 1\end{eqnarray}$$となる。この遷移を行列で表す…

yukicoder No.638 Sum of "not power of 2"

この記事は yukicoder No.638 Sum of "not power of 2" の解説です。 a をなるべく小さくしたいので、可能なら a=3 にしたい。 b のとりうる最小値も a と同じく 3 なので、6=3+3 よりも小さい N は N=a+b で表せない。 以下、N≧6 について考える。 a=3 とし…

yukicoder No.619 CardShuffle

この記事は yukicoder No.619 CardShuffle の解説です。 考え方 問題を見ればセグ木を使えば解けることは予想できる。 セグ木に載せるべき「部分的な計算結果」どうしをつなげて掛け算をしたときの掛け算の影響範囲を考えると、「部分的な計算結果」は a+b+c…

3の倍数を正規表現で

leading zero を許容しない十進非負整数は、 /^(0|[1-9][0-9]*)$/ と表現できる。これは、 /^(0|([1-9]0*)+)$/ と表現することもできる。 以下では、「数」は「 leading zero を許容しない十進非負整数」と同じ意味で扱う。 「 x が 3 の倍数である」と「 x …

yukicoder No.502 階乗を計算するだけ

この記事は、yukicoder No.502 階乗を計算するだけ の解説というより、自分が書いたコードの解説です。 作問者による解説にもある通り、この問題は、予め一部の値を計算しておいて、それを埋め込むことで解ける。作問者は「例えば1000個を埋め込む」と解説し…

yukicoder No.491 10^9+1と回文

この記事は、yukicoder No.491 10^9+1と回文 の解説です。 N の桁数を L とする。10^9+1 の倍数かつ回文数であるような 1 以上 N 以下の整数のうち最大のものを M とする。M が求まれば、最終的な答えは簡単に求まる。 例えば、M=543212345543212345 (これを…

正規表現の積

誰か解いて 追記ここから (長さの制約は適当なのでもっと大きくしても解けるなら大きくしてもらって構わない。)— %20(物理的身近に人がいない) (@henkoudekimasu) 2017年3月5日 一応言っておくと、自力で解けないから「誰か解いて」と言ったのであって、…

Perl でコードゴルフをする時に空白が必要なのはどういう場合か

普通にプログラミングをする上では、空白文字(スペース・タブ・改行)というものは多用されるが、文法上必須であるものは少ない。コードゴルフにおいては、最終的に出来上がるコードには、文法上必須であるような空白以外は不要である。Perl で空白が必要に…

yukicoder No.81 すべて足すだけの簡単なお仕事です。

この記事は、yukicoder No.81 すべて足すだけの簡単なお仕事です。 の解説かもしれない(し、解説でないかもしれない)。この問題のコードゴルフがとても楽しかったので、何があったのかを時系列順に書いてみた次第。 2016-05-25 14:59:37 84B #93995 Matcha…

コードゴルフをする場について

誰向けの記事なのかよくわからない。 Anarchy Golf ゴルフ場 111言語 esolang 多め テストケースは最大3件で全て可視 出題期間は2週間が基本だが、1時間から4週間、無期限もある 出題頻度は時によりばらばら 誰でも作問・出題できる 単に解くだけなら簡単な…

1種類の括弧対で非負整数を表現する記法を思いついた

1種類の括弧の対だけで非負整数を一意に表現するよくわからない記法を思いついた。 この記法で 0 から 32 までを列挙すると以下の通り。 0 () 1 (()) 2 ((())) 3 ((())()) 4 (((()))) 5 (((()))()) 6 (((())())) 7 (((())())()) 8 ((((())))) 9 ((((())))())…

ferNANDo という言語で足し算をした。

ferNANDo という esolang(難解プログラミング言語)で A plus B problem という問題を解いた。endless 問題のネタバレなので、自力で解きたい人は引き返して下さい(いないと思うけど)。 ferNANDo の命令は「入力を1文字読む」「1文字出力する」「2変数を …

Perl では「偽⇒0」は真だが「0⇒偽」は必ずしも真でない

Perl では、真偽値として解釈した値が偽であるならば、数値として解釈した値は 0 である。しかし、数値として解釈した値が 0 であっても、真偽値として解釈した値が偽になるとは限らない。 項 真偽 +0 .'' 備考 0 偽 0 '0' 0b0 偽 0 '0' 0x0 偽 0 '0' 0e5 偽…

AtCoder での Perl golf に関するメモ

最近、AtCoder の問題を(ゴルフで)解き始めた。それに関するメモ。気が向いたら追記する。 N $_**=3,print$_,$/for<> $_=<>;print$_**3,$/ print+($_=<>)**3,$/ $_=<>**3;print$_,$/ print$_**3,$/for<> print<>**3,$/ S $_=<>;print s/abc/xyz/r $_=<>;s/…

ブログを始めるよりも前にあなごるで出題した問題

Anarchy Golf で自分が出題した問題について、ブログを始めたら何かしら書こうと以前から思っていたので書く。 850. A045718 素数±1 の数を 1 から 252 まで出力する問題。初めての出題だったので、簡単だし出題期間は1週間でいいよね・・・とか思って1週間…

ブログを開設した。

とりあえずブログ作った。