ブログ

Blitz Round #25 C - Root Value

2026年10月4日

問題の概要

正の整数 $x$ に対して、$\sqrt[m]{x}$ が自然数になるような最大の $m$ を $f(x)$ とします。

長さ $n$ の数列 $a_1, \ldots, a_n$ ($2 \le a_i \le 200$) と $q$ 個のクエリ $(l, r)$ が与えられるので、各クエリについて

$$f\left(\prod_{i=l}^{r} a_i\right)$$

を求める問題です。

• $1 \le n, q \le 2 \cdot 10^5$、テストケースの $n$ の総和と $q$ の総和はそれぞれ $2 \cdot 10^5$ 以下

正確な問題文は元の問題ページを見てください。

解法

$x$ を素因数分解して $x = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ とすると、$\sqrt[m]{x}$ が整数になるのは、すべての指数 $e_j$ が $m$ の倍数のときです。したがって

$$f(x) = \gcd(e_1, e_2, \ldots, e_k)$$

です。$a_i \ge 2$ なので、積は $2$ 以上になり、指数のどれかは正になります。

積をそのまま計算すると巨大になりますが、指数だけを見れば足し算になります。$a_i \le 200$ なので、現れる素数は $200$ 以下の $46$ 個だけです。各素数について指数の累積和を持っておけば、区間 $[l, r]$ での各素数の指数は差を取るだけで求まり、その $\gcd$ が答えです。

$a_i$ の上限を $A$ ($= 200$)、$A$ 以下の素数の個数を $\pi(A)$ ($= 46$) とすると、計算量は $O((n + q)\,\pi(A))$ です。

解答コード

Python

from math import gcd
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

for _ in range(int(input())):
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    acc = [[0] * len(prime)]
    for a in A:
        t = acc[-1].copy()
        for i, p in enumerate(prime):
            while a % p == 0:
                t[i] += 1
                a //= p
        acc.append(t)
    for _ in range(Q):
        l, r = map(int, input().split())
        l -= 1
        ans = 0
        for i in range(len(prime)):
            ans = gcd(ans, acc[r][i] - acc[l][i])
        print(ans)

タグ:

• 素因数分解
• 累積和
• GCD

Blitz Round #25 B - Jump Trip Score

2026年10月4日

問題の概要

長さ $n$ の整数列 $a_1, \ldots, a_n$ があり、位置 $i = 1$ から出発して $i = n + 1$ に着いたら終わりです。スコアは $0$ から始まり、各位置で次のどちらかを行います。

• $a_i$ をスコアに足して $i + 1$ に進む
• 正の整数 $d$ ($i + d \le n + 1$) を選んで $i + d$ に跳ぶ(スコアは変わらない)

跳ぶ操作は高々 1 回まで使えるとき、最終スコアの最大値を求める問題です。

• $1 \le n \le 4 \cdot 10^5$、$-10^9 \le a_i \le 10^9$、テストケースの $n$ の総和は $4 \cdot 10^5$ 以下

正確な問題文は元の問題ページを見てください。

解法

$i$ から $i + d$ に跳ぶと、$a_i, \ldots, a_{i+d-1}$ を飛ばすことになります。跳ぶのは高々 1 回なので、得られるスコアは

$$(\text{先頭からの連続部分の和}) + (\text{末尾までの連続部分の和})$$

で、間の 1 区間を飛ばした形になります(跳ばなければ全部の和)。

そこで

• $L_k$ = 長さ $k$ 以下の接頭辞の和の最大値(空も含むので $0$ 以上)
• $R_k$ = 位置 $k + 1$ 以降から始まる接尾辞の和の最大値(空も含む)

を累積和で求めておけば、答えは

$$\max_{0 \le k \le n} (L_k + R_k)$$

です。接頭辞と接尾辞が重ならないように、境目 $k$ を全通り試しています。計算量は $O(n)$ です。

別の見方

飛ばす区間の和を $S$ とすると、スコアは $(\text{全体の和}) - S$ です。つまり答えは

$$\sum_{i=1}^{n} a_i - \min(0, \text{連続部分列の和の最小値})$$

で、空を許す最大部分配列問題の最小版そのものです。Kadane のアルゴリズムで最小部分配列和を求めても解けます。解いたあとで気づきました。

解答コード

Python

for _ in range(int(input())):
    N = int(input())
    A = list(map(int,input().split()))
    dp0 = [0]
    x = 0
    for a in A:
        x += a
        dp0.append(max(x, dp0[-1]))
    dp1 = [0]
    x = 0
    for a in reversed(A):
        x += a
        dp1.append(max(x, dp1[-1]))
    dp1.reverse()
    print(max(x+y for x,y in zip(dp0,dp1)))

dp0 が $L$、dp1 が $R$ にあたります。

タグ:

• 累積和
• 最大部分配列問題

Blitz Round #25 A - Sum vs MEX

2026年10月4日

問題の概要

$1$ から $n$ の順列 $p$ のうち、すべての $i$ ($1 \le i \le n$) について

$$\sum_{j=1}^{i} p_j \text{ が } \mathrm{MEX}(p_1, \ldots, p_i) \text{ で割り切れる}$$

を満たすものを 1 つ構築するか、存在しないことを判定する問題です。ここでの $\mathrm{MEX}$ は「含まれない最小の正の整数」です。

• $1 \le n \le 2 \cdot 10^5$、テストケースの $n$ の総和は $2 \cdot 10^5$ 以下

正確な問題文は元の問題ページを見てください。

解法

$n$ が奇数のとき：存在しない

$i = n$ のとき、$p_1, \ldots, p_n$ には $1$ から $n$ がすべて含まれるので $\mathrm{MEX} = n + 1$、総和は $\frac{n(n+1)}{2}$ です。

$$\frac{n(n+1)}{2} \div (n + 1) = \frac{n}{2}$$

なので、割り切れるのは $n$ が偶数のときだけです。よって $n$ が奇数なら答えは NO です。

$n$ が偶数のとき：$1$ を最後に置く

$1$ を最後に置くと、$i < n$ では $p_1, \ldots, p_i$ に $1$ が含まれないので $\mathrm{MEX} = 1$ となり、条件は常に満たされます。

$i = n$ のときは上で見たとおり、$n$ が偶数なら割り切れます。

したがって、たとえば $p = (2, 3, \ldots, n, 1)$ が条件を満たします。

ポイント

「最後の 1 項だけは必ず $\mathrm{MEX} = n + 1$ になる」ことから必要条件を出し、残りは $1$ を後ろに回して $\mathrm{MEX} = 1$ に固定することで条件を自明にする、という構成です。

解答コード

Python

for _ in range(int(input())):
    N = int(input())
    if N & 1:
        print("NO")
    else:
        ans = list(range(2, N + 1)) + [1]
        print("YES")
        print(*ans)

タグ:

• 構築
• MEX
• 偶奇

ICPC 2024 Asia Taichung Regional 参加記

2025年3月1日

ノート

この記事は 2025年3月1日 にはてなブログで公開した記事の転載です。

注意：海外Regionalに参加するための有益情報は特にないです。ほとんど全てをコーチのkotamanegiさんがやってくれました。

他の人の参加記

• amesyu - 会津大
• nyuminyusupe - 会津大
• noshinn - 会津大
• E869120 - 東大
• tokusakurai - 東大コーチ
• littlegirl112 - 阪大
• kotamanegi - 阪大コーチ

出場経緯

前回のあらすじ ICPC2024 国内予選 参加記

Yokohama Regionalに進出することはできませんでしたが、海外Regionalに出ることでAsia Pacific Championshipに進出することが可能であると話題になりました。特に台湾リージョナルでは現実的だろうという予想で、出場に前向きになりました。 kotamanegiさんに実際行くことになるとどのくらいの費用になるのか試算してもらい、結局出場を決めた日は申し込みの最終日でした。

練習

出場を決めてからは毎週土曜日に3人で集まってUCup に出ました。自分のNAISTの院試(院試に関する記事)直前の週以外は全て参加しました。（その週は2人で参加したみたいです）

作戦

明文化したりはあまりしておらず、練習を繰り返す中で動き方を共有していました。3人の特徴としては

• shogo314: 簡単な問題の速解きと典型が得意（ARCが苦手の言い換え）。PythonとC++が使える。
• littlegirl112: 上と似たような感じだが、知識は一番多そう。国内予選の頃から特に訓練を積んでおり、チーム唯一の黄色コーダーになっていた。
• besukohu: 最年少。ARCが強い。AHCがすごく強い。

こんな感じです。英弱過ぎる、Pythonが唯一使える、コードを書くのがある程度速い、考察が弱いなどの理由で基本的に僕がコード書き、たまにlittlegirl112が書くという感じでした。besukohuは練習でも本番でも、一度もパソコンを触りませんでした。

大抵序盤は解けた問題から2人のどちらかが僕に内容を伝えて、数問解いてバグや実装のつまりなどがあるとlittlegirl112と交代しながらコーディングを進めるような形でした。

台湾

スケジュールを決めたり、支払ったりなどは全てkotamanegiさんがやってくれました。いろいろ調べてなるべく安い旅程にしていただいたようで、感謝しています。本当にありがとうございました。

準備

パスポートは実家にあったので送ってもらいました。 kotamanegiさんが台湾ドルの両替を代わりにしてくれると申し出てくれましたが、現金がなくてもそんなに困らなそうだったので断りました。実際困りませんでしたが、流石に多少は持って行った方がいいように思います。 前日に悠遊カードが現金でしか買えないということに気づきました。klookのサイトから事前に決済して空港で受け取れるものがあったので、それを利用することにしました。ついでにsimカードを用意できて満足。それまで通信に関して何も考えていなかったので間一髪です。

こたまねぎさんが有能過ぎて、海外行くのになにも調べてない
今関空が思ったよりも遠くて驚いてる

— shogo314 (@shogo3142) 2024年11月14日

台風が来てオンラインに変わる可能性があるという話が出ていました。日程的に台湾からオンラインで参加することになるので、本当に勘弁してほしい気持ちです。結局、雨が少し降った程度でよかったです。

1日目

関空までは距離があるので徹夜して始発に乗りました。

12:00 関空 ~ 14:15(現地時間) 台北桃園 の飛行機に乗りました。入国審査はあっという間でした。何も話すことなく指紋と目の写真をとっただけで終わりました。ただ、審査の列はかなり長かったです。

空港近くのショッピングモールのフードコートで夕食を食べました。炒飯みたいなのを食べましたが、付いてきたお茶がかなり甘いアッサムティーでした。台湾ではこのお茶が普通みたいです。

新幹線で台中に移動します。新幹線はかなり安いです。ホテル代も安くてそれ以外の物価は普通でした。

夜はホテル近くにある宮原眼科というアイス屋に行きました。知りませんでしたが有名みたいです。アイスを売っているところのとなりは綺麗な感じの建物でお菓子などが売っていました。

2日目

プラクティスの日です。

夕食はホテル近くのショッピングモールのフードコートに行きました。

台中のフードコートに来ました https://t.co/AG86GfjILa pic.twitter.com/WR1rjTphVR

— shogo314 (@shogo3142) 2024年11月16日

この日のABCは爆死しました。悲しい

3日目

本番の日です。 朝は会場行きのバスが来る駅でモスバーガーを食べました。ところで駅の中は八角の匂いがします。コンビニのおでんの位置で八角で味付けした卵が売っています。台湾名物みたいですね。

コンテスト

A

考: besukohu, 実: shogo314

1~5の数のうち4つ与えられるのでない数を答えます。簡単ですね。0完阻止でしょう。

E

考: besukohu, 実: shogo314 少し考えればわかるくらいのやつ。これも結局全チーム解いてました。

B

考: besukohu, 実: littlegirl112 僕がEを書いている間に解けたみたい。

Dがやるだけなのでbesukohuに聞いて書きます。実装につまってしまったのでlittlegirl112に交代します。

C

考: besukohu, littlegirl112, 実: littlegirl112

関わっていません。

この間にMを見てみると簡単に解けたのでそのことを2人に伝えました。

D

考: besukohu 実: shogo314

AC

M

考: shogo314,besukohu,実: shogo314

詳細を詰めていなかったので時間がかかります。 besukohuと相談しながらなんとか提出するもTLE。 setをheap2つにしたり（削除可能にするあれ）いろいろして漸くACしました。

H

考: 全,実: littlegirl112

<>> みたいな文字列が与えられて、2 8 3 1 にみたいな数列がいくつあるかを答える問題です。 besukohuは±1していくイメージでイラストを描いていたのでlittlegirl112が問題を勘違いしていました。 ランレングス圧縮して考えるとうまくいくことに気づきましたが、分割数の求め方を知らなかったので実装はlittlegirl112に任せました。

残った時間はIの激重Trieやるだけをlittlegirl112が書きながら、いい方針がないか考えたり他の問題を見てみたりして過ごしました。

コンテスト終了

27位でした。盾をもらいました。銀賞みたいです。 豪華ですね。

4日目

観光の日です。

お茶を作ってるところに行ったりしました。

台湾の家庭料理の店に案内されましたが、全ての料理に八角が入っていて、みんないやになってました。白米がおいしかったです。

夜はkotamanegiさんのお金で鍋の食べ放題に行きました。

5日目

新幹線で台中を出て、桃園から飛行機で大阪に帰ります。

後日

playoffに行けることになり、びっくり。

内容が薄いのはplayoffの閉会式中に書いているからです。

タグ:

• 参加記
• ICPC

NAIST受験記（2025年春入学・第2回）

2025年1月11日

ノート

この記事は 2025年1月12日 にはてなブログで公開した記事の転載です。

TL;DR

• TOEIC：525
• 数学：2完
• 面接：ぼちぼち
• 169点

自己紹介

大阪大学の学部生です。大阪大学大学院情報科学研究科を受験しましたが、不合格だったので、浪人するか迷いましたがNAISTを専願で受けることにしました。ちなみに阪大はTOEICが低すぎて落ちました。

GPAは2.85です。NAISTに提出した成績証明書には落単したものの成績は出ないので、もう少し高く見えたはずです。

準備

現在行っている研究をそのまま行えるような研究室はNAISTになかったのと、もともと興味があった分野について挑戦してみたい気持ちがあったので、選んだ研究室は現在所属している研究室とはかなり研究内容が違うところになりました。 9月初旬に研究室見学に行きました。時期としては遅いと思います。教授にどういう分野に興味があるという話と、現在の専門は学科レベルなら近いが分野はかなり違う旨を伝えました。教授からその研究室で行っている研究室について話を聞き、小論文で書くジャンルについて相談しました。私が興味を持ったものは日本語の情報が少ないため（英語もそんなに多くないが）そのジャンルについての日本語の解説記事を紹介していただきました。その後、自分は小論文にあまり関われないからと（教授は採点する側の人なので）、他の研究室のメンバーと話す場を設けていただきました。これから勉強するなら、小論文は卒論とこれからやりたい研究で半々くらいにするとよいだろうとアドバイスをいただき実際そのようにしました。

小論文

1週間ほどかけてそのジャンルの論文を列挙し、その中から深めがいのありそうなテーマを選びました。その研究室の人が書いた博論のテーマを別角度からやるみたいな感じです。それから小論文を書くわけですが、とりあえず私が行っている卒論について書きました。9月頭に研究部会で構想発表をしたところだったので、それを半分ほど流用し、別ジャンルの人でもある程度理解できるための情報を追加しました。NAISTでやりたい研究については、表現が適切か、本当に前例がないのか不安になりながら数日かけて書きました。小論文は自分の研究室の教授、先輩、志望している研究室の先輩、所属しているサークルの顧問（NAISTでやりたい研究として書いた分野について研究している）に見てもらいました。特に志望している研究室の先輩方には本当に丁寧に見てもらえました。その先輩にテーマとして書いた内容とかなり近い論文が今年の3月に出ていることを指摘されましが、無料で読めないし（顧問に頼めばよかったかも）、今更大幅な変更もできないと思い、見なかったことにしました。結局面接でも指摘されなかったので、助かりました（その論文のことを教授が知らなかったとかはありえないです。著者のひとりなので）。

数学

1週間前に始めました。解析については大阪大学の院試で勉強していたので、1日くらいかけて復習したくらいです。そもそも高3の範囲から出ることが多そうです。代数については1年くらい触れていなかったので、数日かけて理解しなおしました。固有ベクトルをもとめて、 ${A}^{n}$ を計算するみたいなのが頻出のようなので、実際に説明しながら解く練習をしたりしました。

適当に過去問をググって、解いたりしました。調べると以下のものが出てきます。

• gotutiyan’s blog NAIST受験記2020（2021年春入学・1回目）
• GitHub - tubutubucorn/naist-exam
• うしのおちちの備忘録 2019年NAIST受験記（情報科学専攻）
• Sumansonian NAIST受験をした話
• 気の赴くままに NAIST受験記（2023年度春入学第2回）

面接

対策は何もしませんでした。流石に何かした方が良かったように思います。 2020年入学学生募集要項 に「3分以内でプレゼンテーションをしていただきますので、事前に準備しておいてください。」という記述がありましたが、これ以降の募集要項には書いていなかったので、聞かれないだろうと思って用意していませんでした。実際は聞かれて焦りました。

事前接続確認

部屋を映してもらう可能性があると書かれていることに直前に気付き、あわてて散らかってたのを隠しました。 事前接続確認は受験番号と氏名を確認した後、スケッチブックに文字を書いてみて読めるかの確認がありました。 結局汚い部屋を映すタイミングはありませんでした。

本番

口頭試問

代数

${A}$ と $A '$ および ${A}^{\top}$ と ${A '}^{\top}$ について、消去法を用いて階数を求めよ。

$$A = {\begin{bmatrix}1 & 4 & 0 \\ 2 & 11 & 5 \\ -1 & 2 & 10 \end{bmatrix}}$$ $$A ' = {\begin{bmatrix}1 & 0 & 1 \\ 1 & 1 & 2 \\ 1 & 1 & q \end{bmatrix}}$$

解析

$$\int_{0}^{7 \pi} \left| \cos x \right| dx$$

感想

簡単すぎませんか？日程の初日は簡単という話があったり、オンラインで事前に問題をみる時間がないなどの理由はあるとして、それにしてもです。面接時間は12分ありますが、7分程で解き終わりました。まだ時間はあるが、解けてるので終わる旨を面接官に伝えられ終了しました。掘り下げて質問してくるとかがなかったので、正解してるかが重要なのでしょうか？

面接

• 小論文の内容を1~2分で説明して
  • アドリブでやりましたが、ちょっと短くなってしまいました。準備していないと思われて（実際そう）、印象はよくなさそう。
• 小論文に書いた内容に関する質問
  • 卒論関連は普通に答えました。狭い分野なので、この中で自分が一番詳しいだろうという気持ちでどうどうと答えました。
  • NAISTでやりたい研究について、こういうところがおもしろそうだけど、なにか案はある？と聞かれましたが、あまり考えずに書き足した部分だったので、困りました。
• プログラミング得意？
  • 我、競プロerぞ？
• プログラミング技法Ⅰの成績は低いみたいだけど
  • どんな成績だったか全く覚えておらず、うまく答えられませんでした。せめて、成績については覚えていないがこんな感じの授業内容だった～みたいな返答が出来たら良かったように思います

結果

合格でした。169点でした。配点は書類審査50点、英語30点、数学30点、小論文（面接含む）90点なので、英語以外がほぼ満点だったんだと思います。書類審査がどういうものか全くわかりませんが、まともな大学でまともな成績をとっていたら十分な点がもらえるんだと思います。

タグ:

• 受験記
• NAIST

古い記事