【競技プログラミング】AtCoder Beginner Contest 360_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

右向きの蟻は位置を固定し、左向きの蟻のみ2Tだけ動くと読み直して解く

1. 入力を受け取り、蟻の数N、時間T、蟻の向きを示す文字列S、蟻の初期位置Xを取得する。

2. 蟻を左向き（S[i]が'0'）と右向き（S[i]が'1'）に分類し、それぞれのリストlとrに格納する。

3. リストlとrをソートする。これにより、効率的な二分探索が可能になる。

4. 左向きの蟻それぞれについて、以下の計算を行う：
   a. その蟻がT時間後に到達する位置を計算する（L-T）。
   b. その位置より右にいて、かつ2T以内の距離にある右向きの蟻の数を二分探索で求める。
   c. これがその左向きの蟻とすれ違う右向きの蟻の数となる。

5. 全ての左向きの蟻について4の計算を行い、結果を合計する。

6. 合計値を出力する。

ACコード1

ac.py

import bisect
import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:  # ハンドラが存在しない場合のみ追加
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    return logger

def io_func():
    # 入力を受け取る
    n, t = map(int, input().split())  # 蟻の数Nと時間Tを取得
    s = input()  # 蟻の向きを示す文字列Sを取得
    x = list(map(int, input().split()))  # 蟻の初期位置Xを取得
    return n, t, s, x

def solve(n, t, s, x):
    logger = setup_logger(True)
    
    logger.debug("蟻を左向きと右向きに分類します")
    l = []  # 左向きの蟻のリスト
    r = []  # 右向きの蟻のリスト
    for i in range(n):
        if s[i] == "0":
            l.append(x[i])
        else:
            r.append(x[i])
    
    logger.debug("左向きと右向きの蟻のリストをソートします")
    l.sort()
    r.sort()
    logger.debug(f"左向き: {l}")
    logger.debug(f"右向き: {r}")
    
    logger.debug("すれ違いの回数を計算します")
    ans = 0
    for L in l:
        # 左向きの蟻がT時間後に到達する位置より右にいて、かつ2T以内の距離にある右向きの蟻の数を計算
        logger.debug(f"bisect.bisect_left({r}, {L}) - bisect.bisect_left({r}, {L - 2*t})")
        ans += bisect.bisect_left(r, L) - bisect.bisect_left(r, L - 2*t)
    
    logger.debug(f"計算結果: {ans}")
    return ans

def main():
    n, t, s, x = io_func()
    result = solve(n, t, s, x)
    print(result)

if __name__ == "__main__":
    main()

###
# n: 蟻の数
# t: 時間
# s: 蟻の向きを示す文字列（'0'が左向き、'1'が右向き）
# x: 蟻の初期位置のリスト
# l: 左向きの蟻の位置のリスト
# r: 右向きの蟻の位置のリスト
# ans: すれ違いの回数の合計

# 1. io_func関数:
#    - 標準入力から蟻の数、時間、蟻の向き、初期位置を読み取る
#    - 読み取ったデータを返す
# 2. solve関数:
#    - 蟻を左向きと右向きに分類し、それぞれのリストを作成
#    - 左向きと右向きの蟻のリストをソート
#    - 左向きの蟻それぞれについて、すれ違う右向きの蟻の数を計算
#    - 二分探索を使用して効率的に計算
#    - すれ違いの総数を返す
# 3. main関数:
#    - io_func関数を呼び出してデータを取得
#    - solve関数を呼び出して結果を計算
#    - 結果を出力