競技プログラミング

AtCoder Beginner Contest 170 E - Smart Infants

実装がかなり重かった上に定数倍がきつそうな感じがしたけど、よく見ると制限3.5secだったのでギリギリ間に合った。 実装 こういう問題はまず与えられた情報をとりあえず書いてみると思い浮かんだりする。とりあえずこの2つはすぐわかる。 幼児からレートを…

AtCoder Beginner Contest 170 D - Not Divisible

考え方 エラトステネスの篩が思い浮かべばほぼ勝ち。こういうときはAiから考えがちではあるが、Ajから考えるとよい。 (1 <= j <= N)について、Ajを除くAjの倍数はダメ それぞれの数について、2個以上含まれている場合はダメ これらを、与えられた数列の各要…

java/kotlinでAtcoderの解答を縦に出力する場合の注意点

java/kotlinのSystem.out.println()/println()は早くないので、改行してN個の答えを出力する場合は注意。まとめてprintlnしたほうがよい。 例 - ABC113_C - ID 処理部分の計算量はO(NlogN)なので本来は間に合うはず 普通に出した場合 提出 TLEでダメ まとめ…

2値配列における転倒数の求め方(計算量O(n))

AGC034_Bのような問題で、2値配列の転倒数を求めることがあったが、大抵解説では流されていることが多いためメモ。 転倒数とはなにかはここ)。ここでは後の説明のために「バブルソートを行うときにswapを行う回数」としておく。 転倒数を求める場合、多値配…

第三回 アルゴリズム実技検定(PAST)

76点で中級。茶色にしてはできたと思った。途中で飯食ったの今思うと完全に余計。80点惜しかったなぁと思う。 コンテストページ ソースコード A - ケース・センシティブ String.lowerCase()で一発、やるだけ。 B - ダイナミック・スコアリング ある人が解け…