ラベル Trie木 の投稿を表示しています。 すべての投稿を表示
ラベル Trie木 の投稿を表示しています。 すべての投稿を表示

2025年11月25日火曜日

ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）

　Fまで六完。
　Gも考察の方向性は間違っていなかった模様。

コンテスト後のツイート

G - Sum of Min of XOR

　解説放送を見てAC。
　コンテスト中は、Binary Trieを使うことを思い付いていたらしいが、今考えていたときは思い付けなかった。

　しかし、Binary Trieを使うと思いつけたのなら、Binary Trieに区間を入れていくだけなのでそれほど難しくない気がするのだけれど、コンテスト時はどうして分からなかったのだろう？

　解説を見た今だと、考察も必要なアルゴリズムもそこまで難しくないため、解けなきゃいけない問題に見える。



時刻: 0 件のコメント:
ラベル: , ,

2025年4月29日火曜日

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）

　Fまで六完。

コンテスト後のツイート

G - Odd Position Sum Query

　解説放送を見てAC。

　この前のこたつがめさんの解説放送で、セグメント木≒Binary Trieだという話を聞いていた。知識はあったので解けなくてはいけない問題だった。

　ただ、そもそも、値が小さければ普通のセグメント木で解ける、ってこと自体思いついてなかったんだよね……。



時刻: 0 件のコメント:
ラベル: ,

2024年6月5日水曜日

Codeforces Round 950 (Div. 3)

　F1まで。

コンテスト後のツイート

F2. Field Division (hard version)

　自力AC。

　コンテスト中に考えていた方針であっていたが、実装が大変だった。Gに行かずF2に集中していたらギリギリ間に合っていたかなぁ……。


G. Yasya and the Mysterious Tree

　Binary Trieを使うということを参考にAC。

　ただし、コンテスト中は誤読しており、xorではなくorを計算するものと思っていた。これがなかったら解法を思い付いていた気がする。

　ただし実装には非常に苦戦した。
　自分のTrieだとTLEで通らず、Chat GPTによりC++へ書き換えると、エラーが起きてしまい、どこが間違っているか分かるまで一時間以上かかった。

　偶奇に分けて要素たちをBinary Trieに突っ込み、毎回自分の要素を減らした上で最適なものを探すのだが、要素数が0になっていたときの処理を怠っていた。
　Pythonのコードもバグっていたはずなのだけど、PythonだとLIST[-1]というのでエラーが出ないため、たまたま合ってしまっていたんですね……。

　修正してなんとかAC。
　ただ、C++でも制限時間ギリギリだったので、Trieの書き方に問題がありそう。Binary Trieをちゃんと書かないといけないのかな。

時刻: 0 件のコメント:
ラベル: ,

2022年10月14日金曜日

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)

 　ABCEFの五完。

コンテスト後のツイート



 G - Random Student ID

　解説放送を見てAC。

　あんまり自分で考察しなかったけど、考察ができてもTrie木を使うことを思い付けたかどうか。Trie木を使わなくても上手くソートすれば解けそうだけど、実装で苦戦してしまいそう。

Ex - Taboo

　解説放送を見てAC。

　Aho-Corasick法を勉強しました。
　もっと難しいかと思っていたけれど、結構理解しやすいアルゴリズムでした。
　


時刻: 0 件のコメント:
ラベル: , ,

2022年1月15日土曜日

Codeforces Round #765 (Div. 2)

　Cまで三完でした。Dは難しかった。


D. Binary Spiders

　いくつかの解法ツイートを見てAC。

　まず、上位bitから考えていき、kのx bit目が0か1かで場合分けする。
　0の場合は、「x bitが0の集合」「x bitが1の集合」という二つの問題に分割される。

　kのx bit目が1の場合が問題。
　x bit目が0のものと1のもの高々二つしか取れないが、全探索すると二乗になってしまう。

　そこで、x bitが0のものを全探索することにし、もう片方はTrie木を使って整理する。x bit目が0の要素aに対して、できるだけa^uが大きくなるようなuをTrie木を利用して探していく。そのxorがk以上ならばそれを採用、そういう組が一つもなければ、何か一要素を適当に採用する。

　Trie木を使い慣れていないこともあり、この解法は自力ではなかなか思いつけなかった気がする。自分のライブラリのTrie木が意外と使いやすかったのには驚いた。
時刻: 0 件のコメント:
ラベル: ,

2021年7月2日金曜日

東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)

　ABCEの四完で約半年ぶりにHighestを更新したものの、後でEが嘘だったことが発覚。まぁ、そんなものか。


D - XOR Game

　ちょっと考えて、トライ木を使うのでは？　と思ったところで手が止まってしまったのは良くない。トライ木の理解が不足していたのが敗因だと思うので、ちゃんと復習しておかないと。

　……と思ったが、トライ木を使わなくても再帰を使えばACできると目にし、そちらの方法でAC。（トライ木の復習はしていません）

　Aの全ての要素を二つずつペアにし、それらのxorの最大値を取る……という問題を考えたとき、それができるだけ小さくなるようなペアの取り方を考える問題だ、ということはすぐに気付けた。

　問題は、どう実装するか。
　上位bitから見て行って、立っているbitが偶数個なら、立っているもの同士、立っていないもの同士をペアにすれば良い。それは再帰で書ける。

　立っているbitが奇数個だったときは、bitが立っているもの（それらの集合をBとする）と立っていないもの（Cとする）とのxorを取らなければならない（ので、答えのそのbitは必ず立つことになる）。そのようなペアのうち、最小のものを探せば良い。
　……ということは分かるが、この実装が悩ましい。これをTrie木を使って処理するというのが公式解説の方法だった。

　だがこれも上位bitから見ていく方法でできる。

　奇数個立っていたbitの次のbitを考える。

　BとCの両方でそのbitが立っているものがある、もしくは、両方でそのbitが立っていないものがある、のなら、立っているもの同士、もしくは立っていないもの同士のペアを取った方が良い。そのいずれかの最小値が答えになる（ので、再帰が回る）。
　そういうものがなければ、答えにおいて今考えたbitも立っていることが分かる。そして、その次のbitを見ることになる。

E - Increasing LCMs

　前から素因数の要素数が少ない順に追加していけば良いと思いACしたけれど、嘘でした。

　本当の解法である「後ろから決定していく」というのも一応考えていたので、WAが出ていたら方針転換できた可能性はある。

　けれど、提出したときは結構自信を持っていた（証明できた気がしていた）ので、動揺したと思う。残り二十分ほど、そんな状態で方針転換してACまでいけたか、というと……。実際のところは分かりませんね。


（Fもいずれ解きたい）
時刻: 0 件のコメント:
ラベル: ,

2020年7月10日金曜日

Kick Start Round A 2020

　Dが解けず。
　コンテスト中もTrie木を使うのかな、とは思ったようですが……。

コンテストへのリンク
コンテスト後のツイート

Bundling

　（英語だけど）この動画解説を参考にした。……けど、Trieが頭に入っていればそれほど難しくないね。簡単な木DPで解けます。

　Trieについては、kami634さんの記事が詳しいし分かりやすい。上の動画でTrieの概要は理解できたのだけど、実装をどうすれば良いか分からなくなったときこの記事が参考になった。感謝。
　実装方針が分かってしてしまえば意外と書くのは簡単だったけれど、自分で最初実装を考えたときは、辞書を使って云々しなくてはいけない気がしてしまい困った。ノードが追加されるたびに、新しいidを割り当てるようにすれば良いですね。

　ACした提出を一応載せておきます。（見ての通り、Trieをclassにしたりはしてません）

import sys
input = sys.stdin.readline

T = int(input())
for testcases in range(T):
    N,K=map(int,input().split())

    # Trie木

    Next_node_id=[[-1]*26] # "A"～"Z"それぞれについて、対応する次のノードのid
    Parent_id=[-1] # 親ノード
    Depth=[0] # Trieのノードの深さ
    Count=[0] # Trieのノードの重複度

    Nodes_id=1 # 以下、標準入力で与えられたN個の文字列を追加する実装
    for i in range(N):
        S=input().strip()
        L=len(S)

        NOW=0
        for s in S:
            NEXT=ord(s)-65
            
            if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
                Next_node_id[NOW][NEXT]=Nodes_id

                Next_node_id.append([-1]*26)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)

                NOW=Nodes_id         
                Nodes_id+=1

            else: # 追加しない場合
                NOW=Next_node_id[NOW][NEXT]

        Count[NOW]+=1 # 終端に印を付ける

    TOP_SORT=sorted([(dep,id) for id,dep in enumerate(Depth)],reverse=True)

    Rest=[0]*len(TOP_SORT)
    ANS=0

    for dep,n in TOP_SORT:
        c=Count[n]+Rest[n]
        ANS+=Depth[n]*(c//K)
        Rest[Parent_id[n]]+=c%K

    print("Case #"+str(testcases+1)+": "+str(ANS))
時刻: 0 件のコメント:
ラベル:

2020年6月22日月曜日

Educational Codeforces Round 83 (Rated for Div. 2)

　Eが解けなかった上、CがHackされて悲惨な出来。

コンテストへのリンク

B. Bogosort

　大きい順（降順）にソートすればOK。

・まず極端な場合を考えてみる

　という意味でもソート状態を考えてみるのが良い。

　また、立式して考えるのも良い。
　$A_i-i=A_j=j$でi<jのとき、必ず$A_i<A_j$なので、そうならないようにする、という方針でも思いつけると思う。

C. Adding Powers

　$k\geq 2$のとき、$k^n$は$k^1, k^2, ... , k^{n-1}$の和より大きい、ということを利用する問題。
　これが成り立つので、kのベキ達の和である数を作るためには、できるだけ大きいベキを使わなくてはいけない。

D. Count the Arrays

・Combi(m, n-1) : m個の数から、互いに異なるn-1個を選ぶ。（一組の数字が一致しているので、互いに異なるのはn-1個）
・n-2 : 一致する数を選ぶ。増加列と減少列の間には最大の数が来るしかないので、それを除いたn-2個から選ぶ。
・$2^{n-3} : 最大値と、一致する数を除いた残りn-3個の数を増加列か、減少列かのいずれかに割り振る。

　これで題意の配列が定まるので、この積が答え。

E. Array Shrinking

　コンテスト中に区間DPだと思いつつも解けなかった。
　DP[i][j]で、区間[i, j]が一つの数字に縮約できたときの値、とすれば良い。

　この定義は今見ると自然に見えるけど、確かに、「縮約したときの最小の長さ」をDPの値に持ちたいと思ってしまうと、ハマってしまうか……。

　そのDPテーブルを利用して、長さの最小値も求められる。（あるいは、けんちょんさんの記事のように、同時に求めることもできる）
　また、かっつさんの記事にありますが、もっと計算量は速くなるらしいです。

F. Attack on Red Kingdom

　一応、自力AC。最近Grundy数を復習したのを覚えていたから解けただけで、コンテスト時に解くことは無理だったと思う。

　こういうタイプのゲームはGrundy数を考えるしかない。
　x, y, zが小さいので、それぞれについてGrundy数を前計算しておく。

　問題は、$a_i$が大きいことだけど……。
　まあ、Grundy数はどこからか周期的になっているはずで、大きくても2520（1~10の最大公約数）周期にはなっているだろう、と思い、$a_i\geq 5400$のとき、$a_i =a_i$ %2520+2520$としたらACした。

　公式解説を見たら、周期もちゃんと調べてますね。

G. Autocompletion

　アルメリアさんの解説記事、けんちょんさんの解説記事があったので解説ACしました。アルメリアさんの記事はかなり詳しく書いてあり、ありがたかった。

　Trie木について理解していなかったこともあって、問題文の読解から苦労してしまったのですが、やること自体はそこまで難しくないですね。
　ただ、「ある点から子孫の点へワープするときのコストの減少幅」がどの子孫へ行くときも一定というのは、意外な気がしてしまいました。これが直感的に正しいと思えれば解くのは難しくなさそう。

　Trie木の勉強にもなったので良かったです。これを機に、Trie木を使う問題を一つくらい解くべきかなぁ……。




時刻: 0 件のコメント:
ラベル: , ,
登録: 投稿 (Atom)